class Containers::RubyRBTreeMap
rdoc
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. MIT License Copyright (c) 2009 Kanwei Li Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
Attributes
Public Class Methods
Create and initialize a new empty TreeMap.
# File lib/containers/rb_tree_map.rb, line 48 def initialize @root = nil @height_black = 0 end
Public Instance Methods
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"
# File lib/containers/rb_tree_map.rb, line 152 def delete(key) result = nil if @root @root, result = delete_recursive(@root, key) @root.color = :black if @root end result end
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
# File lib/containers/rb_tree_map.rb, line 195 def delete_max result = nil if @root @root, result = delete_max_recursive(@root) @root.color = :black if @root end result end
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
# File lib/containers/rb_tree_map.rb, line 176 def delete_min result = nil if @root @root, result = delete_min_recursive(@root) @root.color = :black if @root end result end
Iterates over the TreeMap from smallest to largest element. Iterative approach.
# File lib/containers/rb_tree_map.rb, line 205 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
Returns true if the tree is empty, false otherwise
# File lib/containers/rb_tree_map.rb, line 162 def empty? @root.nil? end
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"
# File lib/containers/rb_tree_map.rb, line 111 def get(key) get_recursive(@root, key) end
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
# File lib/containers/rb_tree_map.rb, line 99 def has_key?(key) !get(key).nil? end
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
# File lib/containers/rb_tree_map.rb, line 86 def height @root and @root.height or 0 end
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"
# File lib/containers/rb_tree_map.rb, line 136 def max_key @root.nil? ? nil : max_recursive(@root) end
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"
# File lib/containers/rb_tree_map.rb, line 124 def min_key @root.nil? ? nil : min_recursive(@root) end
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”
# File lib/containers/rb_tree_map.rb, line 60 def push(key, value) @root = insert(@root, key, value) @height_black += 1 if isred(@root) @root.color = :black value end
Return the number of items in the TreeMap.
map = Containers::TreeMap.new map.push("MA", "Massachusetts") map.push("GA", "Georgia") map.size #=> 2
# File lib/containers/rb_tree_map.rb, line 74 def size @root and @root.size or 0 end
Private Instance Methods
# File lib/containers/rb_tree_map.rb, line 353 def delete_max_recursive(node) if (isred(node.left)) node = node.rotate_right end return nil, node.value if node.right.nil? if ( !isred(node.right) && !isred(node.right.left) ) node.move_red_right end node.right, result = delete_max_recursive(node.right) return node.fixup, result end
# File lib/containers/rb_tree_map.rb, line 340 def delete_min_recursive(node) if node.left.nil? return nil, node.value end if ( !isred(node.left) && !isred(node.left.left) ) node.move_red_left end node.left, result = delete_min_recursive(node.left) return node.fixup, result end
# File lib/containers/rb_tree_map.rb, line 315 def delete_recursive(node, key) if (key <=> node.key) == -1 node.move_red_left if ( !isred(node.left) && !isred(node.left.left) ) node.left, result = delete_recursive(node.left, key) else node.rotate_right if isred(node.left) if ( ( (key <=> node.key) == 0) && node.right.nil? ) return nil, node.value end if ( !isred(node.right) && !isred(node.right.left) ) node.move_red_right end if (key <=> node.key) == 0 result = node.value node.value = get_recursive(node.right, min_recursive(node.right)) node.key = min_recursive(node.right) node.right = delete_min_recursive(node.right).first else node.right, result = delete_recursive(node.right, key) end end return node.fixup, result end
# File lib/containers/rb_tree_map.rb, line 367 def get_recursive(node, key) return nil if node.nil? case key <=> node.key when 0 then return node.value when -1 then return get_recursive(node.left, key) when 1 then return get_recursive(node.right, key) end end
# File lib/containers/rb_tree_map.rb, line 391 def insert(node, key, value) return Node.new(key, value) unless node case key <=> node.key when 0 then node.value = value when -1 then node.left = insert(node.left, key, value) when 1 then node.right = insert(node.right, key, value) end node.rotate_left if (node.right && node.right.red?) node.rotate_right if (node.left && node.left.red? && node.left.left && node.left.left.red?) node.colorflip if (node.left && node.left.red? && node.right && node.right.red?) node.update_size end
# File lib/containers/rb_tree_map.rb, line 407 def isred(node) return false if node.nil? node.color == :red end
# File lib/containers/rb_tree_map.rb, line 384 def max_recursive(node) return node.key if node.right.nil? max_recursive(node.right) end
# File lib/containers/rb_tree_map.rb, line 377 def min_recursive(node) return node.key if node.left.nil? min_recursive(node.left) end