class Containers::RubySplayTreeMap

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

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. clear
  2. delete
  3. each
  4. get
  5. has_key?
  6. height
  7. max
  8. min
  9. push
  10. size

Included modules

  1. Enumerable

Constants

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

Public Instance Aliases

[] -> get
[]= -> push

Public Class methods

new ()

Create and initialize a new empty SplayTreeMap.

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

Public Instance methods

clear ()

Remove all elements from the SplayTreeMap

Complexity: O(1)

[show source] 
# 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)

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
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 ()

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

[show source] 
# 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)

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
def get(key)
  return nil if @root.nil?
  
  splay(key)
  (@root.key <=> key) == 0 ? @root.value : nil
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
def has_key?(key)
  !get(key).nil?
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
def height
  height_recursive(@root)
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
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 ()

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
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)

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
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 ()

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