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, line 22
def initialize
  @size = 0
  clear
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, line 77
def clear
  @root = nil
  @size = 0
  @header = Node.new(nil, nil, nil, nil)
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, 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() { |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, 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) 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, line 116
def get(key)
  return nil if @root.nil?
  
  splay(key)
  (@root.key <=> key) == 0 ? @root.value : nil
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, line 104
def has_key?(key)
  !get(key).nil?
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, line 91
def height
  height_recursive(@root)
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, 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() 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, 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) 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, 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
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, line 69
def size
  @size
end

Private Instance Methods

height_recursive(node) click to toggle source

Recursively determine height

# File lib/containers/splay_tree_map.rb, line 253
def height_recursive(node)
  return 0 if node.nil?
  
  left_height   = 1 + height_recursive(node.left)
  right_height  = 1 + height_recursive(node.right)
  
  left_height > right_height ? left_height : right_height
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, line 210
def splay(key)
  l, r = @header, @header
  t = @root
  @header.left, @header.right = nil, nil
  
  loop do
    if (key <=> t.key) == -1
      break unless t.left
      if (key <=> t.left.key) == -1
        y = t.left
        t.left = y.right
        y.right = t
        t = y
        break unless t.left
      end
      r.left = t
      r = t
      t = t.left
    elsif (key <=> t.key) == 1
      break unless t.right
      if (key <=> t.right.key) == 1
        y = t.right
        t.right = y.left
        y.left = t
        t = y
        break unless t.right
      end
      l.right = t
      l = t
      t = t.right
    else
      break
          end
  end
  l.right = t.left
  r.left = t.right
  t.left = @header.right
  t.right = @header.left
  @root = t
end