class SplayTree
Constants
- UndefinedValue
- VERSION
Attributes
The default value for non existent key
@api public
The default block for non existent key
@api public
Public Class Methods
Create a SplayTree
@param [Object] default
the default value for missing key
@api public
# File lib/splay_tree.rb, line 27 def initialize(default = UndefinedValue, &block) if !UndefinedValue.equal?(default) && block raise ArgumentError, "You need to pass either argument or a block as a default value" end @root = Node::EMPTY @subtree = Node.new(nil, nil) @default = default @default_proc = block end
Public Instance Methods
Find object by the key
@param [Object] key
the search key
@api public
# File lib/splay_tree.rb, line 164 def [](key) splay(key) unless @root.empty? return default_value if @root.key != key @root.value end
Insert a node into a tree with the given key and value provided that the tree does not already contain the key. The node becomes the root of the tree.
@param [Object] key
the key under which the node is inserted
@param [Object] value
the value of the node inserted into the tree
@return [Boolean]
false if key already exists, true otherwise
@api public
# File lib/splay_tree.rb, line 146 def []=(key, value) if @root.empty? @root = Node.new(key, value) return true end @root = @root.insert(key, value) splay(key) end
Delete a node specified by the key from the tree given the tree contains a node with this key. The deleted node value is returned. If the node is not found a nil is returned.
@param [Object] key
@return [Object]
the node's value under the key
@api public
# File lib/splay_tree.rb, line 196 def delete(key) return if empty? splay(key) return if @root.key != key deleted = @root right = @root.right @root = @root.left if @root.empty? @root = right else splay(key) # ensure empty right child @root.right = right end deleted.value end
Dump the tree structure in bracket format (root left right)
@return [String]
@api public
# File lib/splay_tree.rb, line 230 def dump @root.dump || "" end
Iterate over each key & value pair in the tree
@example
tree = SplayTree.new tree.each { |key, val| ... }
@yield [key, value]
@yieldparam [Object] key @yieldparam [Object] value
@return [self]
@api public
# File lib/splay_tree.rb, line 63 def each(&block) if block_given? @root.each(&block) self else @root.to_enum end end
Iterate over each key in the tree
@example
tree = SplayTree.new tree.each_key { |key| ... }
@yield [key]
@yieldparam [Object] key
@return [self]
@api public
# File lib/splay_tree.rb, line 85 def each_key(&block) if block_given? @root.each_key(&block) self else @root.to_enum(:each_key) end end
Iterate over each value in the tree
@example
tree = SplayTree.new tree.each_value { |val| ... }
@yield [value]
@yieldparam [Object] value
@return [self]
@api public
# File lib/splay_tree.rb, line 107 def each_value(&block) if block_given? @root.each_value(&block) self else @root.to_enum(:each_value) end end
@api public
# File lib/splay_tree.rb, line 39 def empty? @root == Node::EMPTY end
Check if tree contains a node with a matching key.
@return [Boolean]
@api public
# File lib/splay_tree.rb, line 178 def key?(key) return false if @root.empty? splay(key) @root.key == key end
Return a new array of all the keys in the tree
@return [Array]
@api public
# File lib/splay_tree.rb, line 121 def keys each_key.to_a end
@api public
# File lib/splay_tree.rb, line 44 def size @root.size end
Construct and return two trees t1 and t2, where t1 contains items in t less than or equal to key, and t2 contains all items in t greater than key.
@param [Object] key
@api public
# File lib/splay_tree.rb, line 221 def split(key) end
Export tree as hash
@return [Hash]
@api public
# File lib/splay_tree.rb, line 239 def to_hash each_with_object({}) { |(k, v), acc| acc[k] = v } end
Return a new array of all the values in the tree
@return [Array]
@api public
# File lib/splay_tree.rb, line 130 def values each_value.to_a end
Private Instance Methods
@api private
# File lib/splay_tree.rb, line 246 def default_value if @default != UndefinedValue @default elsif @default_proc @default_proc.call end end
Top-down splaying by breaking down the tree.
@param [Object] key
the key at which to splay
@api private
# File lib/splay_tree.rb, line 260 def splay(key) current = @root dummy = left = right = @subtree @subtree.left = @subtree.right = Node::EMPTY loop do break if key == current.key if key < current.key break if current.left.empty? if key < current.left.key current = current.rotate_right break if current.left.empty? end right.left = current right = current current = current.left elsif key > current.key break if current.right.empty? if key > current.right.key current = current.rotate_left break if current.right.empty? end left.right = current left = current current = current.right end end left.right = current.left right.left = current.right current.left = dummy.right current.right = dummy.left @root = current end