class SplayTree::Node

A single tree node representation

Constants

EMPTY
UndefinedValue

Attributes

key[R]
left[RW]
right[RW]
value[R]

Public Class Methods

new(key, value) click to toggle source
# File lib/splay_tree/node.rb, line 18
def initialize(key, value)
  @key, @value = key, value
  @left = @right = Node::EMPTY
end

Public Instance Methods

<=>(other) click to toggle source

Compare node keys

@return [Integer]

@api private

# File lib/splay_tree/node.rb, line 42
def <=>(other)
  @key <=> other.key
end
dump() click to toggle source

Dump the subtree structure starting from this node

@return [String]

@api private

# File lib/splay_tree/node.rb, line 74
def dump
  left = @left.dump
  right = @right.dump
  if !@left.empty? || !@right.empty?
    "(" + [@key, left || "-", right || "-"].compact.join(" ") + ")"
  else
    @key || ""
  end
end
each() { |key, value| ... } click to toggle source

Iterate over subtree nodes

@api private

# File lib/splay_tree/node.rb, line 49
def each(&block)
  @left.each(&block)
  yield [@key, @value]
  @right.each(&block)
end
each_key() { |k| ... } click to toggle source

Iterate over subtree nodes

@api private

# File lib/splay_tree/node.rb, line 58
def each_key
  each { |k, _| yield k }
end
each_value() { |v| ... } click to toggle source

Iterate over subtree nodes

@api private

# File lib/splay_tree/node.rb, line 65
def each_value
  each { |_, v| yield v }
end
empty?() click to toggle source

@api private

# File lib/splay_tree/node.rb, line 24
def empty?
  false
end
insert(key, value) click to toggle source

Insert new root

@api private

# File lib/splay_tree/node.rb, line 119
def insert(key, value)
  case key <=> @key
  when -1
    @left = @left.insert(key, value)
    rotate_right
  when 0
    @value = value
    self
  when 1
    @right = @right.insert(key, value)
    rotate_left
  else
    raise TypeError, "Cannot compare: #{key} with #{@key}"
  end
end
rotate_left() click to toggle source

Rotate left

 Y            X
/ \          / \

A X => Y C

 / \      / \
B   C    A   B

@api private

# File lib/splay_tree/node.rb, line 109
def rotate_left
  tmp      = @right
  @right   = tmp.left
  tmp.left = self
  tmp
end
rotate_right() click to toggle source

Rotate right

   Y         X
  / \       / \
 X   C  => A   Y
/ \           / \

A B B C

@api private

# File lib/splay_tree/node.rb, line 93
def rotate_right
  tmp       = @left
  @left     = tmp.right
  tmp.right = self
  tmp
end
size() click to toggle source

Number of nodes in this subtree

@return [Integer]

@api private

# File lib/splay_tree/node.rb, line 33
def size
  left.size + 1 + right.size
end