Class Containers::RubyRBTreeMap

  1. lib/containers/rb_tree_map.rb
Parent: Object

A RBTreeMap is a map that is stored in sorted order based on the order of its keys. This ordering is determined by applying the function <=> to compare the keys. No duplicate values for keys are allowed, so duplicate values are overwritten.

A major advantage of RBTreeMap over a Hash is the fact that keys are stored in order and can thus be iterated over in order. This is useful for many datasets.

The implementation is adapted from Robert Sedgewick’s Left Leaning Red-Black Tree implementation, which can be found at www.cs.princeton.edu/~rs/talks/LLRB/Java/RedBlackBST.java

Containers::RBTreeMap automatically uses the faster C implementation if it was built when the gem was installed. Alternatively, Containers::RubyRBTreeMap and Containers::CRBTreeMap can be explicitly used as well; their functionality is identical.

Most methods have O(log n) complexity.

Included modules

  1. Enumerable

Attributes

height_black [RW]

Public class methods

new ()

Create and initialize a new empty TreeMap.

[show source]
    # File lib/containers/rb_tree_map.rb, line 26
26:   def initialize
27:     @root = nil
28:     @height_black = 0
29:   end

Public instance methods

[] (key)

Alias for get

[]= (key, value)

Alias for push

delete (key)

Deletes the item and key if it’s found, and returns the item. Returns nil if key is not present.

!!! Warning !!! There is a currently a bug in the delete method that occurs rarely but often enough, especially in large datasets. It is currently under investigation.

Complexity: O(log n)

map = Containers::TreeMap.new
map.push("MA", "Massachusetts")
map.push("GA", "Georgia")
map.min_key #=> "GA"
[show source]
     # File lib/containers/rb_tree_map.rb, line 130
130:   def delete(key)
131:     result = nil
132:     if @root
133:       @root, result = delete_recursive(@root, key)
134:       @root.color = :black if @root
135:     end
136:     result
137:   end
delete_max ()

Deletes the item with the smallest key and returns the item. Returns nil if key is not present.

Complexity: O(log n)

map = Containers::TreeMap.new
map.push("MA", "Massachusetts")
map.push("GA", "Georgia")
map.delete_max #=> "Georgia"
map.size #=> 1
[show source]
     # File lib/containers/rb_tree_map.rb, line 173
173:   def delete_max
174:     result = nil
175:     if @root
176:       @root, result = delete_max_recursive(@root)
177:       @root.color = :black if @root
178:     end
179:     result
180:   end
delete_min ()

Deletes the item with the smallest key and returns the item. Returns nil if key is not present.

Complexity: O(log n)

map = Containers::TreeMap.new
map.push("MA", "Massachusetts")
map.push("GA", "Georgia")
map.delete_min #=> "Massachusetts"
map.size #=> 1
[show source]
     # File lib/containers/rb_tree_map.rb, line 154
154:   def delete_min
155:     result = nil
156:     if @root
157:       @root, result = delete_min_recursive(@root)
158:       @root.color = :black if @root
159:     end
160:     result
161:   end
each () {|cursor.key, cursor.value| ...}

Iterates over the TreeMap from smallest to largest element. Iterative approach.

[show source]
     # File lib/containers/rb_tree_map.rb, line 183
183:   def each
184:     return nil unless @root
185:     stack = Containers::Stack.new
186:     cursor = @root
187:     loop do
188:       if cursor
189:         stack.push(cursor)
190:         cursor = cursor.left
191:       else
192:         unless stack.empty?
193:           cursor = stack.pop
194:           yield(cursor.key, cursor.value)
195:           cursor = cursor.right
196:         else
197:           break
198:         end
199:       end
200:     end
201:   end
empty? ()

Returns true if the tree is empty, false otherwise

[show source]
     # File lib/containers/rb_tree_map.rb, line 140
140:   def empty?
141:     @root.nil?
142:   end
get (key)

Return the item associated with the key, or nil if none found.

Complexity: O(log n)

map = Containers::TreeMap.new
map.push("MA", "Massachusetts")
map.push("GA", "Georgia")
map.get("GA") #=> "Georgia"
[show source]
    # File lib/containers/rb_tree_map.rb, line 89
89:   def get(key)
90:     get_recursive(@root, key)
91:   end
has_key? (key)

Return true if key is found in the TreeMap, false otherwise

Complexity: O(log n)

map = Containers::TreeMap.new
map.push("MA", "Massachusetts")
map.push("GA", "Georgia")
map.has_key?("GA") #=> true
map.has_key?("DE") #=> false
[show source]
    # File lib/containers/rb_tree_map.rb, line 77
77:   def has_key?(key)
78:     !get(key).nil?
79:   end
height ()

Return the height of the tree structure in the TreeMap.

Complexity: O(1)

map = Containers::TreeMap.new
map.push("MA", "Massachusetts")
map.push("GA", "Georgia")
map.height #=> 2
[show source]
    # File lib/containers/rb_tree_map.rb, line 64
64:   def height
65:     @root and @root.height or 0
66:   end
max_key ()

Return the largest key in the map.

Complexity: O(log n)

map = Containers::TreeMap.new
map.push("MA", "Massachusetts")
map.push("GA", "Georgia")
map.max_key #=> "MA"
[show source]
     # File lib/containers/rb_tree_map.rb, line 114
114:   def max_key
115:     @root.nil? ? nil : max_recursive(@root)
116:   end
min_key ()

Return the smallest key in the map.

Complexity: O(log n)

map = Containers::TreeMap.new
map.push("MA", "Massachusetts")
map.push("GA", "Georgia")
map.min_key #=> "GA"
[show source]
     # File lib/containers/rb_tree_map.rb, line 102
102:   def min_key
103:     @root.nil? ? nil : min_recursive(@root)
104:   end
push (key, value)

Insert an item with an associated key into the TreeMap, and returns the item inserted

Complexity: O(log n)

map = Containers::TreeMap.new map.push(“MA”, “Massachusetts”) #=> “Massachusetts” map.get(“MA”) #=> “Massachusetts“

[show source]
    # File lib/containers/rb_tree_map.rb, line 38
38:   def push(key, value)
39:     @root = insert(@root, key, value)
40:     @height_black += 1 if isred(@root)
41:     @root.color = :black
42:     value
43:   end
size ()

Return the number of items in the TreeMap.

map = Containers::TreeMap.new
map.push("MA", "Massachusetts")
map.push("GA", "Georgia")
map.size #=> 2
[show source]
    # File lib/containers/rb_tree_map.rb, line 52
52:   def size
53:     @root and @root.size or 0
54:   end