Class: Containers::RubySplayTreeMap

Inherits:
Object
  • Object
show all
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

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

Returns:

  • (Boolean) 


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