SplayTree

A self-balancing binary tree optimised for fast access to frequently used nodes. Useful for implementing caches and garbage collection algorithms.

Features

Add this line to your application's Gemfile:

gem "splay_tree"

And then execute:

$ bundle

Or install it yourself as:

$ gem install splay_tree

SplayTree operations are similar to that of Hash:

tree = SplayTree.new
tree[:foo] = :bar

tree[:foo]  # => :bar
tree.size   # => 1

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.

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.

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

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

Use empty? to check if a tree contains any elements:

tree = SplayTree.new
tree.empty?  # => true

tree[:foo] = 1
tree.empty?  # => false

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.

Everyone interacting in the SplayTree project’s codebases, issue trackers, chat rooms and mailing lists is expected to follow the code of conduct.