binary_search_tree

Installation: gem install binary_search_tree

Info: This gem implements the two classes BinarySearchTree and BinarySearchTreeHash. BinarySearchTree is a self balancing avl tree.

Most people will only need to be concerned with BinarySearchTreeHash as it is a wrapper over BinarySearchTree that provides the same interface as the native Ruby hash. This class is useful when you want a container that provides fast lookups with minimal memory footprint. Since it is self balancing, it will reorganize itself on every new insert to make subsequent lookups optimal.

--Example usage of BinarySearchTreeHash--

ruby-1.9.2> h = BinarySearchTreeHash.new logger (note: passing a logger is optional) => {} ruby-1.9.2> (1..100).each{|i| h[i] = i*1000} ruby-1.9.2> h[45] DEBUG - [03/May/2011 15:02:07] "find operation completed in 7 lookups..." => 45000 ruby-1.9.2> h[77] DEBUG - [03/May/2011 15:02:14] "find operation completed in 6 lookups..." => 77000 ruby-1.9.2> h[32] DEBUG - [03/May/2011 15:02:18] "find operation completed in 2 lookups..." => 32000 ruby-1.9.2> h.delete 32 DEBUG - [03/May/2011 15:02:29] "find operation completed in 2 lookups..." ruby-1.9.2> h[32] DEBUG - [03/May/2011 15:02:58] "find operation completed in 8 lookups..." => nil ruby-1.9.2> h[5000] = 7777 => 7777 ruby-1.9.2> h[5000] DEBUG - [03/May/2011 15:03:33] "find operation completed in 7 lookups..." => 7777 ruby-1.9.2> h.size => 100 ruby-1.9.2> h.delete 50 DEBUG - [03/May/2011 15:03:48] "find operation completed in 6 lookups..." ruby-1.9.2> h.size => 99

--Example usage of BinarySearchTree (only use this if you want something lower level)--

ruby-1.9.2> b = BinarySearchTree.new logger (note: passing a logger is optional) ruby-1.9.2> b.insert 45, 78 ruby-1.9.2> b.insert 23, 5 ruby-1.9.2> b.insert 77, 999 ruby-1.9.2> b.insert 43, 999 ruby-1.9.2> b.find(23).value DEBUG - [03/May/2011 15:23:15] "find operation completed in 2 lookups..." => 5 ruby-1.9.2> b.find(24) DEBUG - [03/May/2011 15:23:32] "find operation completed in 4 lookups..." => nil ruby-1.9.2> b.find(43).value DEBUG - [03/May/2011 15:23:40] "find operation completed in 3 lookups..." => 999 ruby-1.9.2> b.max.value => 999 ruby-1.9.2> b.min.value => 5 ruby-1.9.2> b.size => 4 ruby-1.9.2> b.remove 23 DEBUG - [03/May/2011 15:24:41] "find operation completed in 2 lookups..." ruby-1.9.2> b.size => 3 ruby-1.9.2> b.clear => 0 ruby-1.9.2> b.size => 0