SplayTree

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

Features

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

  1. Fork it ( github.com/piotrmurach/splay_tree/fork )

  2. Create your feature branch (git checkout -b my-new-feature)

  3. Commit your changes (git commit -am 'Add some feature')

  4. Push to the branch (git push origin my-new-feature)

  5. 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 © 2014 Piotr Murach. See LICENSE for further details.