Class: Containers::RubySplayTreeMap
- Inherits:
-
Object
- Object
- Containers::RubySplayTreeMap
- Includes:
- Enumerable
- Defined in:
- lib/containers/splay_tree_map.rb
Overview
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.
Defined Under Namespace
Classes: Node
Instance Method Summary collapse
-
#clear ⇒ Object
Remove all elements from the SplayTreeMap.
-
#delete(key) ⇒ Object
Deletes the item and key if it’s found, and returns the item.
-
#each ⇒ Object
Iterates over the SplayTreeMap in ascending order.
-
#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 SplayTreeMap, false otherwise.
-
#height ⇒ Object
Return the height of the tree structure in the SplayTreeMap.
-
#initialize ⇒ RubySplayTreeMap
constructor
Create and initialize a new empty SplayTreeMap.
-
#max ⇒ Object
Return the largest [key, value] pair in the SplayTreeMap, or nil if the tree is empty.
-
#min ⇒ Object
Return the smallest [key, value] pair in the SplayTreeMap, or nil if the tree is empty.
-
#push(key, value) ⇒ Object
(also: #[]=)
Insert an item with an associated key into the SplayTreeMap, and returns the item inserted.
-
#size ⇒ Object
Return the number of items in the SplayTreeMap.
Constructor Details
#initialize ⇒ RubySplayTreeMap
Create and initialize a new empty SplayTreeMap.
22 23 24 25 |
# File 'lib/containers/splay_tree_map.rb', line 22 def initialize @size = 0 clear end |
Instance Method Details
#clear ⇒ Object
Remove all elements from the SplayTreeMap
Complexity: O(1)
77 78 79 80 81 |
# File 'lib/containers/splay_tree_map.rb', line 77 def clear @root = nil @size = 0 @header = Node.new(nil, nil, nil, nil) end |
#delete(key) ⇒ Object
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
170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 |
# File 'lib/containers/splay_tree_map.rb', line 170 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 |
#each ⇒ Object
Iterates over the SplayTreeMap in ascending order. Uses an iterative, not recursive, approach.
189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 |
# File 'lib/containers/splay_tree_map.rb', line 189 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 |
#get(key) ⇒ Object Also known as: []
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"
116 117 118 119 120 121 |
# File 'lib/containers/splay_tree_map.rb', line 116 def get(key) return nil if @root.nil? splay(key) (@root.key <=> key) == 0 ? @root.value : nil end |
#has_key?(key) ⇒ Boolean
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
104 105 106 |
# File 'lib/containers/splay_tree_map.rb', line 104 def has_key?(key) !get(key).nil? end |
#height ⇒ Object
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
91 92 93 |
# File 'lib/containers/splay_tree_map.rb', line 91 def height height_recursive(@root) end |
#max ⇒ Object
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"]
150 151 152 153 154 155 156 157 158 |
# File 'lib/containers/splay_tree_map.rb', line 150 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 |
#min ⇒ Object
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"]
132 133 134 135 136 137 138 139 140 |
# File 'lib/containers/splay_tree_map.rb', line 132 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 |
#push(key, value) ⇒ Object Also known as: []=
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"
34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
# File 'lib/containers/splay_tree_map.rb', line 34 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 |
#size ⇒ Object
Return the number of items in the SplayTreeMap.
map = Containers::SplayTreeMap.new
map.push("MA", "Massachusetts")
map.push("GA", "Georgia")
map.size #=> 2
69 70 71 |
# File 'lib/containers/splay_tree_map.rb', line 69 def size @size end |