Class: Algorithms::Containers::RubyRBTreeMap

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

Defined Under Namespace

Classes: Node

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ RubyRBTreeMap

Create and initialize a new empty TreeMap.



28
29
30
31
 
# File 'lib/containers/rb_tree_map.rb', line 28

def initialize
  @root = nil
  @height_black = 0
end

Instance Attribute Details

#height_black ⇒ Object

Returns the value of attribute height_black.



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

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 = Algorithms::Containers::TreeMap.new
map.push("MA", "Massachusetts")
map.push("GA", "Georgia")
map.min_key #=> "GA"



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

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 = Algorithms::Containers::TreeMap.new
map.push("MA", "Massachusetts")
map.push("GA", "Georgia")
map.delete_max #=> "Georgia"
map.size #=> 1



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

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 = Algorithms::Containers::TreeMap.new
map.push("MA", "Massachusetts")
map.push("GA", "Georgia")
map.delete_min #=> "Massachusetts"
map.size #=> 1



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

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.



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

def each
  return nil unless @root
  stack = 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) 


142
143
144
 
# File 'lib/containers/rb_tree_map.rb', line 142

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 = Algorithms::Containers::TreeMap.new
map.push("MA", "Massachusetts")
map.push("GA", "Georgia")
map.get("GA") #=> "Georgia"



91
92
93
 
# File 'lib/containers/rb_tree_map.rb', line 91

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 = Algorithms::Containers::TreeMap.new
map.push("MA", "Massachusetts")
map.push("GA", "Georgia")
map.has_key?("GA") #=> true
map.has_key?("DE") #=> false

Returns:

  • (Boolean) 


79
80
81
 
# File 'lib/containers/rb_tree_map.rb', line 79

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

#height ⇒ Object

Return the height of the tree structure in the TreeMap.

Complexity: O(1)

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



66
67
68
 
# File 'lib/containers/rb_tree_map.rb', line 66

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

#max_key ⇒ Object

Return the largest key in the map.

Complexity: O(log n)

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



116
117
118
 
# File 'lib/containers/rb_tree_map.rb', line 116

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 = Algorithms::Containers::TreeMap.new
map.push("MA", "Massachusetts")
map.push("GA", "Georgia")
map.min_key #=> "GA"



104
105
106
 
# File 'lib/containers/rb_tree_map.rb', line 104

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 = Algorithms::Containers::TreeMap.new map.push(“MA”, “Massachusetts”) #=> “Massachusetts” map.get(“MA”) #=> “Massachusetts”



40
41
42
43
44
45
 
# File 'lib/containers/rb_tree_map.rb', line 40

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 = Algorithms::Containers::TreeMap.new
map.push("MA", "Massachusetts")
map.push("GA", "Georgia")
map.size #=> 2



54
55
56
 
# File 'lib/containers/rb_tree_map.rb', line 54

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