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*1000} ruby-1.9.2> h

 DEBUG - [03/May/2011 15:02:07] "find operation completed in 7 lookups..."
=> 45000

ruby-1.9.2> h

 DEBUG - [03/May/2011 15:02:14] "find operation completed in 6 lookups..."
=> 77000

ruby-1.9.2> h

 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

 DEBUG - [03/May/2011 15:02:58] "find operation completed in 8 lookups..."
=> nil

ruby-1.9.2> h = 7777

=> 7777

ruby-1.9.2> h

 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