Class: Containers::RubyRBTreeMap

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/containers/rb_tree_map.rb

Overview

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 http://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.

Defined Under Namespace

Classes: Node

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ RubyRBTreeMap

Create and initialize a new empty TreeMap.



26
27
28
29
 
# File 'lib/containers/rb_tree_map.rb', line 26

def initialize
  @root = nil
  @height_black = 0
end

Instance Attribute Details

#height_black ⇒ Object

Returns the value of attribute height_black.



23
24
25
 
# File 'lib/containers/rb_tree_map.rb', line 23

def height_black
  @height_black
end

Instance Method Details

#delete(key) ⇒ Object

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"



130
131
132
133
134
135
136
137
 
# File 'lib/containers/rb_tree_map.rb', line 130

def delete(key)
  result = nil
  if @root
    @root, result = delete_recursive(@root, key)
    @root.color = :black if @root
  end
  result
end

#delete_max ⇒ Object

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



173
174
175
176
177
178
179
180
 
# File 'lib/containers/rb_tree_map.rb', line 173

def delete_max
  result = nil
  if @root
    @root, result = delete_max_recursive(@root)
    @root.color = :black if @root
  end
  result
end

#delete_min ⇒ Object

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



154
155
156
157
158
159
160
161
 
# File 'lib/containers/rb_tree_map.rb', line 154

def delete_min
  result = nil
  if @root
    @root, result = delete_min_recursive(@root)
    @root.color = :black if @root
  end
  result
end

#each ⇒ Object

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



183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
 
# File 'lib/containers/rb_tree_map.rb', line 183

def each
  return nil unless @root
  stack = Containers::Stack.new
  cursor = @root
  loop do
    if cursor
      stack.push(cursor)
      cursor = cursor.left
    else
      unless stack.empty?
        cursor = stack.pop
        yield(cursor.key, cursor.value)
        cursor = cursor.right
      else
        break
      end
    end
  end
end

#empty? ⇒ Boolean

Returns true if the tree is empty, false otherwise

Returns:

  • (Boolean) 


140
141
142
 
# File 'lib/containers/rb_tree_map.rb', line 140

def empty?
  @root.nil?
end

#get(key) ⇒ Object Also known as: []

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"



89
90
91
 
# File 'lib/containers/rb_tree_map.rb', line 89

def get(key)
  get_recursive(@root, key)
end

#has_key?(key) ⇒ Boolean

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

Returns:

  • (Boolean) 


77
78
79
 
# File 'lib/containers/rb_tree_map.rb', line 77

def has_key?(key)
  !get(key).nil?
end

#height ⇒ Object

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



64
65
66
 
# File 'lib/containers/rb_tree_map.rb', line 64

def height
  @root and @root.height or 0
end

#max_key ⇒ Object

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"



114
115
116
 
# File 'lib/containers/rb_tree_map.rb', line 114

def max_key
  @root.nil? ? nil : max_recursive(@root)
end

#min_key ⇒ Object

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"



102
103
104
 
# File 'lib/containers/rb_tree_map.rb', line 102

def min_key
  @root.nil? ? nil : min_recursive(@root)
end

#push(key, value) ⇒ Object Also known as: []=

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”



38
39
40
41
42
43
 
# File 'lib/containers/rb_tree_map.rb', line 38

def push(key, value)
  @root = insert(@root, key, value)
  @height_black += 1 if isred(@root)
  @root.color = :black
  value
end

#size ⇒ Object

Return the number of items in the TreeMap.

map = Containers::TreeMap.new
map.push("MA", "Massachusetts")
map.push("GA", "Georgia")
map.size #=> 2



52
53
54
 
# File 'lib/containers/rb_tree_map.rb', line 52

def size
  @root and @root.size or 0
end