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