class Containers::RubyRBTreeMap

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

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

Public Instance Aliases

[] -> get
[]= -> push

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
def initialize
  @root = nil
  @height_black = 0
end

Public Instance methods

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
def delete(key)
  result = nil
  if @root
    @root, result = delete_recursive(@root, key)
    @root.color = :black if @root
  end
  result
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
def delete_max
  result = nil
  if @root
    @root, result = delete_max_recursive(@root)
    @root.color = :black if @root
  end
  result
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
def delete_min
  result = nil
  if @root
    @root, result = delete_min_recursive(@root)
    @root.color = :black if @root
  end
  result
end
each ()

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

[show source] 
# 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? ()

Returns true if the tree is empty, false otherwise

[show source] 
# File lib/containers/rb_tree_map.rb, line 140
def empty?
  @root.nil?
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
def get(key)
  get_recursive(@root, key)
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
def has_key?(key)
  !get(key).nil?
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
def height
  @root and @root.height or 0
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
def max_key
  @root.nil? ? nil : max_recursive(@root)
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
def min_key
  @root.nil? ? nil : min_recursive(@root)
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
def push(key, value)
  @root = insert(@root, key, value)
  @height_black += 1 if isred(@root)
  @root.color = :black
  value
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
def size
  @root and @root.size or 0
end