SplayTree
¶ ↑
A self-balancing binary tree optimised for fast access to frequently used nodes. Useful for implementing caches and garbage collection algorithms.
Features¶ ↑
-
Familiar
Hash
like access -
Easy instantiation with default value
Installation¶ ↑
Add this line to your application's Gemfile:
gem "splay_tree"
And then execute:
$ bundle
Or install it yourself as:
$ gem install splay_tree
Contents¶ ↑
1. Usage¶ ↑
SplayTree operations are similar to that of Hash
:
tree = SplayTree.new tree[:foo] = :bar tree[:foo] # => :bar tree.size # => 1
1.1 insert¶ ↑
To assign a value to a given key do the following:
tree = SplayTree.new tree[:foo] = 1 tree[:bar] = 2
Note: The inserted key will be subjected to splaying, which means the tree will be rearranged to help with quicker access on subsequent calls.
1.2 fetch¶ ↑
To retrieve a value at a given key do:
tree = SplayTree.new tree[:foo] # => nil tree[:foo] = 1 tree[:foo] # => 1
Note: Frequently accessed keys will move nearer to the root where they can be accessed more quickly.
1.3 default¶ ↑
You can set a default value for a missing key. This can be done during initialization:
tree = SplayTree.new tree.default # => UndefinedValue tree = SplayTree.new(1) tree.default # => 1 tree[:foo] # => 1
Or using default
method:
tree = SplayTree.new tree.default = 1 tree[:foo] # => 1
You can also use a block to set the default value:
tree = SplayTree.new tree.default_proc # => nil tree = SplayTree.new { 1 } tree.default_proc # => #<Proc...> tree[:foo] # => 1
1.4 delete¶ ↑
In order to remove an entry from a splay tree use delete
method. If a key is not found, the default value is returned, otherwise nil
.
tree = SplayTree.new tree[:foo] = 1 tree.delete(:foo) # => 1 tree.delete(:bar) # => nil
1.5 empty?¶ ↑
Use empty?
to check if a tree contains any elements:
tree = SplayTree.new tree.empty? # => true tree[:foo] = 1 tree.empty? # => false
1.6 each¶ ↑
Use each
method to iterate over all tree nodes like so:
tree = SplayTree.new tree[:foo] = 1 tree[:bar] = 2 tree.each { |key, value| puts "#{key}: #{value}" } # => # bar: 2 # foo: 1
You can also use each_key
and each_value
to enumerate only keys or values:
tree.each_key { |key| ... } tree.each_value { |value| ... }
If no block is given, an enumerator is returned instead.
Contributing¶ ↑
-
Fork it ( github.com/piotrmurach/splay_tree/fork )
-
Create your feature branch (
git checkout -b my-new-feature
) -
Commit your changes (
git commit -am 'Add some feature'
) -
Push to the branch (
git push origin my-new-feature
) -
Create a new Pull Request
Code of Conduct¶ ↑
Everyone interacting in the SplayTree
project’s codebases, issue trackers, chat rooms and mailing lists is expected to follow the code of conduct.
Copyright¶ ↑
Copyright © 2014 Piotr Murach. See LICENSE for further details.