class Containers::RubySplayTreeMap

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.

Constants

Node

Public Class Methods

new() click to toggle source

Create and initialize a new empty SplayTreeMap.

   # File lib/containers/splay_tree_map.rb
22 def initialize
23   @size = 0
24   clear
25 end

Public Instance Methods

[](key)
Alias for: get
[]=(key, value)
Alias for: push
clear() click to toggle source

Remove all elements from the SplayTreeMap

Complexity: O(1)

   # File lib/containers/splay_tree_map.rb
77 def clear
78   @root = nil
79   @size = 0
80   @header = Node.new(nil, nil, nil, nil)
81 end
delete(key) click to toggle source

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
170 def delete(key)
171   return nil if @root.nil?
172   deleted = nil
173   splay(key)
174   if (key <=> @root.key) == 0 # The key exists
175     deleted = @root.value
176     if @root.left.nil?
177       @root = @root.right
178     else
179       x = @root.right
180       @root = @root.left
181       splay(key)
182       @root.right = x
183     end
184   end
185   deleted
186 end
each() { |key, value| ... } click to toggle source

Iterates over the SplayTreeMap in ascending order. Uses an iterative, not recursive, approach.

    # File lib/containers/splay_tree_map.rb
189 def each
190   return nil unless @root
191   stack = Containers::Stack.new
192   cursor = @root
193   loop do
194     if cursor
195       stack.push(cursor)
196       cursor = cursor.left
197     else
198       unless stack.empty?
199         cursor = stack.pop
200         yield(cursor.key, cursor.value)
201         cursor = cursor.right
202       else
203         break
204       end
205     end
206   end
207 end
get(key) click to toggle source

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
116 def get(key)
117   return nil if @root.nil?
118   
119   splay(key)
120   (@root.key <=> key) == 0 ? @root.value : nil
121 end
Also aliased as: []
has_key?(key) click to toggle source

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
104 def has_key?(key)
105   !get(key).nil?
106 end
height() click to toggle source

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
91 def height
92   height_recursive(@root)
93 end
max() click to toggle source

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
150 def max
151   return nil if @root.nil?
152   n = @root
153   while n.right
154     n = n.right
155   end
156   splay(n.key)
157   return [n.key, n.value]
158 end
min() click to toggle source

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
132 def min
133   return nil if @root.nil?
134   n = @root
135   while n.left
136     n = n.left
137   end
138   splay(n.key)
139   return [n.key, n.value]
140 end
push(key, value) click to toggle source

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
34 def push(key, value)
35   if @root.nil?
36     @root = Node.new(key, value, nil, nil)
37     @size = 1
38     return value
39   end
40   splay(key)
41   
42   cmp = (key <=> @root.key)
43   if cmp == 0
44     @root.value = value
45     return value
46   end
47   node = Node.new(key, value, nil, nil)
48   if cmp < 1
49     node.left = @root.left
50     node.right = @root
51     @root.left = nil
52   else
53     node.right = @root.right
54     node.left = @root
55     @root.right = nil
56   end
57   @root = node
58   @size += 1
59   value
60 end
Also aliased as: []=
size() click to toggle source

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
69 def size
70   @size
71 end

Private Instance Methods

height_recursive(node) click to toggle source

Recursively determine height

    # File lib/containers/splay_tree_map.rb
253 def height_recursive(node)
254   return 0 if node.nil?
255   
256   left_height   = 1 + height_recursive(node.left)
257   right_height  = 1 + height_recursive(node.right)
258   
259   left_height > right_height ? left_height : right_height
260 end
splay(key) click to toggle source

Moves a key to the root, updating the structure in each step.

    # File lib/containers/splay_tree_map.rb
210 def splay(key)
211   l, r = @header, @header
212   t = @root
213   @header.left, @header.right = nil, nil
214   
215   loop do
216     if (key <=> t.key) == -1
217       break unless t.left
218       if (key <=> t.left.key) == -1
219         y = t.left
220         t.left = y.right
221         y.right = t
222         t = y
223         break unless t.left
224       end
225       r.left = t
226       r = t
227       t = t.left
228     elsif (key <=> t.key) == 1
229       break unless t.right
230       if (key <=> t.right.key) == 1
231         y = t.right
232         t.right = y.left
233         y.left = t
234         t = y
235         break unless t.right
236       end
237       l.right = t
238       l = t
239       t = t.right
240     else
241       break
242           end
243   end
244   l.right = t.left
245   r.left = t.right
246   t.left = @header.right
247   t.right = @header.left
248   @root = t
249 end