Class: Containers::RubyRBTreeMap
- Inherits:
-
Object
- Object
- Containers::RubyRBTreeMap
- 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
-
#height_black ⇒ Object
Returns the value of attribute height_black.
Instance Method Summary collapse
-
#delete(key) ⇒ Object
Deletes the item and key if it’s found, and returns the item.
-
#delete_max ⇒ Object
Deletes the item with the largest key and returns the item.
-
#delete_min ⇒ Object
Deletes the item with the smallest key and returns the item.
-
#each ⇒ Object
Iterates over the TreeMap from smallest to largest element.
-
#empty? ⇒ Boolean
Returns true if the tree is empty, false otherwise.
-
#get(key) ⇒ Object
(also: #[])
Return the item associated with the key, or nil if none found.
-
#has_key?(key) ⇒ Boolean
Return true if key is found in the TreeMap, false otherwise.
-
#height ⇒ Object
Return the height of the tree structure in the TreeMap.
-
#initialize ⇒ RubyRBTreeMap
constructor
Create and initialize a new empty TreeMap.
-
#max_key ⇒ Object
Return the largest key in the map.
-
#min_key ⇒ Object
Return the smallest key in the map.
-
#push(key, value) ⇒ Object
(also: #[]=)
Insert an item with an associated key into the TreeMap, and returns the item inserted.
-
#size ⇒ Object
Return the number of items in the TreeMap.
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 largest 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
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
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 |