Skip to content
A fork of unmaintained https://github.com/skade/rbtree released as rbtree3 (because the name "rbtree2" is already occupied...)
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
.circleci
ChangeLog
LICENSE
MANIFEST
README
depend
dict.c
dict.h
extconf.rb
rbtree.c
rbtree3.gemspec
test.rb

README

=begin

= Ruby/RBTree

RBTree is a sorted associative collection that is implemented with
Red-Black Tree. The elements of RBTree are ordered and its interface
is the almost same as Hash, so simply you can consider RBTree sorted
Hash.

Red-Black Tree is a kind of binary tree that automatically balances
by itself when a node is inserted or deleted. Thus the complexity
for insert, search and delete is O(log N) in expected and worst
case. On the other hand the complexity of Hash is O(1). Because
Hash is unordered the data structure is more effective than
Red-Black Tree as an associative collection.

The elements of RBTree are sorted with natural ordering (by <=>
method) of its keys or by a comparator(Proc) set by readjust
method. It means all keys in RBTree should be comparable with each
other. Or a comparator that takes two arguments of a key should return
negative, 0, or positive depending on the first argument is less than,
equal to, or greater than the second one.

The interface of RBTree is the almost same as Hash and there are a
few methods to take advantage of the ordering:

  * lower_bound, upper_bound, bound
  * first, last
  * shift, pop
  * reverse_each

Note: while iterating RBTree (e.g. in a block of each method), it is
not modifiable, or TypeError is thrown.

RBTree supoorts pretty printing using pp.

This library contains two classes. One is RBTree and the other is
MultiRBTree that is a parent class of RBTree. RBTree does not allow
duplications of keys but MultiRBTree does.

  require "rbtree"
  
  rbtree = RBTree["c", 10, "a", 20]
  rbtree["b"] = 30
  p rbtree["b"]              # => 30
  rbtree.each do |k, v|
    p [k, v]
  end                        # => ["a", 20] ["b", 30] ["c", 10]
    
  mrbtree = MultiRBTree["c", 10, "a", 20, "e", 30, "a", 40]
  p mrbtree.lower_bound("b") # => ["c", 10]
  mrbtree.bound("a", "d") do |k, v|
    p [k, v]
  end                        # => ["a", 20] ["a", 40] ["c", 10]

== Requirement

  * Ruby 1.8.x

== Install

  $ sudo gem install rbtree

or download a tarball from the link below

  * ((<"Ruby/RBTree 0.2.1"|URL:rbtree-0.2.1.tar.gz>))

and then

  $ tar xzf rbtree-x.x.x.tar.gz
  $ cd rbtree-x.x.x.tar.gz
  $ ruby extconf.rb
  $ make
  $ sudo make site-install

== Test

  $ ruby test.rb

== Incomplete Documents

  $ rdoc rbtree.c

or online documents at ((<URL:http://rbtree.rubyforge.org/>)).

== License

MIT License. Copyright (c) 2002-2004, 2007, 2009 OZAWA Takuma.

dict.c and dict.h are modified copies that are originally in Kazlib
written by Kaz Kylheku. Copyright is held by Kaz Kylheku, see dict.c
and dict.h for the license. The web page of Kazlib is at
((<URL:http://users.footprints.net/~kaz/kazlib.html>)).

== Support

Bug fixes, suggestions and other feedbacks are welcomed. Please mail
me at burningdowntheopera at yahoo dot co dot jp.

== Links

  * ((<RAA - ruby-rbtree|URL:http://raa.ruby-lang.org/project/ruby-rbtree/>))
  * ((<RubyForge: rbtree: Project Info|URL:http://rubyforge.org/projects/rbtree/>))
  * ((<URL:http://www.geocities.co.jp/SiliconValley-PaloAlto/3388/rbtree/README.html>))

=end
You can’t perform that action at this time.