Class Containers::RubySplayTreeMap

  1. lib/containers/splay_tree_map.rb
Parent: Object

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.

Methods

public class

  1. new

public instance

  1. []
  2. []=
  3. clear
  4. delete
  5. each
  6. get
  7. has_key?
  8. height
  9. max
  10. min
  11. push
  12. size

Included modules

  1. Enumerable

Constants

Node = Struct.new(:key, :value, :left, :right)

Public class methods

new ()

Create and initialize a new empty SplayTreeMap.

[show source]
    # File lib/containers/splay_tree_map.rb, line 22
22:   def initialize
23:     @size = 0
24:     clear
25:   end

Public instance methods

[] (key)

Alias for get

[]= (key, value)

Alias for push

clear ()

Remove all elements from the SplayTreeMap

Complexity: O(1)

[show source]
    # File lib/containers/splay_tree_map.rb, line 77
77:   def clear
78:     @root = nil
79:     @size = 0
80:     @header = Node.new(nil, nil, nil, nil)
81:   end
delete (key)

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
[show source]
     # File lib/containers/splay_tree_map.rb, line 170
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 () {|cursor.key, cursor.value| ...}

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

[show source]
     # File lib/containers/splay_tree_map.rb, line 189
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)

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"
[show source]
     # File lib/containers/splay_tree_map.rb, line 116
116:   def get(key)
117:     return nil if @root.nil?
118:     
119:     splay(key)
120:     (@root.key <=> key) == 0 ? @root.value : nil
121:   end
has_key? (key)

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
[show source]
     # File lib/containers/splay_tree_map.rb, line 104
104:   def has_key?(key)
105:     !get(key).nil?
106:   end
height ()

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
[show source]
    # File lib/containers/splay_tree_map.rb, line 91
91:   def height
92:     height_recursive(@root)
93:   end
max ()

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"]
[show source]
     # File lib/containers/splay_tree_map.rb, line 150
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 ()

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"]
[show source]
     # File lib/containers/splay_tree_map.rb, line 132
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)

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"
[show source]
    # File lib/containers/splay_tree_map.rb, line 34
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
size ()

Return the number of items in the SplayTreeMap.

map = Containers::SplayTreeMap.new
map.push("MA", "Massachusetts")
map.push("GA", "Georgia")
map.size #=> 2
[show source]
    # File lib/containers/splay_tree_map.rb, line 69
69:   def size
70:     @size
71:   end