class Containers::RubySplayTreeMap
rdoc
A SplayTreeMap is a map that is stored in ascending order of its keys, determined by applying the function <=> to compare keys. No duplicate values for keys are allowed, so new values of a key overwrites the old value of the key. A major advantage of SplayTreeMap over a Hash is the fact that keys are stored in order and can thus be iterated over in order. Also, Splay Trees are self-optimizing as recently accessed nodes stay near the root and are easily re-accessed later. Splay Trees are also more simply implemented than Red-Black trees. Splay trees have amortized O(log n) performance for most methods, but are O(n) worst case. This happens when keys are added in sorted order, causing the tree to have a height of the number of items added. 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.
Constants
- Node
Public Class Methods
Create and initialize a new empty SplayTreeMap.
# File lib/containers/splay_tree_map.rb, line 43 def initialize @size = 0 clear end
Public Instance Methods
Remove all elements from the SplayTreeMap
Complexity: O(1)
# File lib/containers/splay_tree_map.rb, line 98 def clear @root = nil @size = 0 @header = Node.new(nil, nil, nil, nil) end
Deletes the item and key if it's found, and returns the item. Returns nil if key is not present.
Complexity: amortized O(log n)
map = Containers::SplayTreeMap.new map["MA"] = "Massachusetts" map["GA"] = "Georgia" map.delete("GA") #=> "Georgia" map.delete("DE") #=> nil
# File lib/containers/splay_tree_map.rb, line 191 def delete(key) return nil if @root.nil? deleted = nil splay(key) if (key <=> @root.key) == 0 # The key exists deleted = @root.value if @root.left.nil? @root = @root.right else x = @root.right @root = @root.left splay(key) @root.right = x end end deleted end
Iterates over the SplayTreeMap in ascending order. Uses an iterative, not recursive, approach.
# File lib/containers/splay_tree_map.rb, line 210 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
Return the item associated with the key, or nil if none found.
Complexity: amortized O(log n)
map = Containers::SplayTreeMap.new map.push("MA", "Massachusetts") map.push("GA", "Georgia") map.get("GA") #=> "Georgia"
# File lib/containers/splay_tree_map.rb, line 137 def get(key) return nil if @root.nil? splay(key) (@root.key <=> key) == 0 ? @root.value : nil end
Return true if key is found in the SplayTreeMap, false otherwise.
Complexity: amortized O(log n)
map = Containers::SplayTreeMap.new map["MA"] = "Massachusetts" map["GA"] = "Georgia" map.has_key?("GA") #=> true map.has_key?("DE") #=> false
# File lib/containers/splay_tree_map.rb, line 125 def has_key?(key) !get(key).nil? end
Return the height of the tree structure in the SplayTreeMap.
Complexity: O(log n)
map = Containers::SplayTreeMap.new map.push("MA", "Massachusetts") map.push("GA", "Georgia") map.height #=> 2
# File lib/containers/splay_tree_map.rb, line 112 def height height_recursive(@root) end
Return the largest [key, value] pair in the SplayTreeMap, or nil if the tree is empty.
Complexity: amortized O(log n)
map = Containers::SplayTreeMap.new map["MA"] = "Massachusetts" map["GA"] = "Georgia" map.max #=> ["MA", "Massachusetts"]
# File lib/containers/splay_tree_map.rb, line 171 def max return nil if @root.nil? n = @root while n.right n = n.right end splay(n.key) return [n.key, n.value] end
Return the smallest [key, value] pair in the SplayTreeMap, or nil if the tree is empty.
Complexity: amortized O(log n)
map = Containers::SplayTreeMap.new map["MA"] = "Massachusetts" map["GA"] = "Georgia" map.min #=> ["GA", "Georgia"]
# File lib/containers/splay_tree_map.rb, line 153 def min return nil if @root.nil? n = @root while n.left n = n.left end splay(n.key) return [n.key, n.value] end
Insert an item with an associated key into the SplayTreeMap, and returns the item inserted
Complexity: amortized O(log n)
map = Containers::SplayTreeMap.new map.push("MA", "Massachusetts") #=> "Massachusetts" map.get("MA") #=> "Massachusetts"
# File lib/containers/splay_tree_map.rb, line 55 def push(key, value) if @root.nil? @root = Node.new(key, value, nil, nil) @size = 1 return value end splay(key) cmp = (key <=> @root.key) if cmp == 0 @root.value = value return value end node = Node.new(key, value, nil, nil) if cmp < 1 node.left = @root.left node.right = @root @root.left = nil else node.right = @root.right node.left = @root @root.right = nil end @root = node @size += 1 value end
Return the number of items in the SplayTreeMap.
map = Containers::SplayTreeMap.new map.push("MA", "Massachusetts") map.push("GA", "Georgia") map.size #=> 2
# File lib/containers/splay_tree_map.rb, line 90 def size @size end
Private Instance Methods
Recursively determine height
# File lib/containers/splay_tree_map.rb, line 274 def height_recursive(node) return 0 if node.nil? left_height = 1 + height_recursive(node.left) right_height = 1 + height_recursive(node.right) left_height > right_height ? left_height : right_height end
Moves a key to the root, updating the structure in each step.
# File lib/containers/splay_tree_map.rb, line 231 def splay(key) l, r = @header, @header t = @root @header.left, @header.right = nil, nil loop do if (key <=> t.key) == -1 break unless t.left if (key <=> t.left.key) == -1 y = t.left t.left = y.right y.right = t t = y break unless t.left end r.left = t r = t t = t.left elsif (key <=> t.key) == 1 break unless t.right if (key <=> t.right.key) == 1 y = t.right t.right = y.left y.left = t t = y break unless t.right end l.right = t l = t t = t.right else break end end l.right = t.left r.left = t.right t.left = @header.right t.right = @header.left @root = t end