class Tree::RedBlackNode
Tree::RedBlackNode
is a pure-Ruby implementation of a Red-Black tree – i.e., a self-balancing binary search tree with O(log n) search, insert and delete operations. It is appropriate for maintaining an ordered collection where insertion and deletion are desired at arbitrary positions.
The implementation differs slightly from the Wikipedia description referenced above. In particular, leaf nodes are nil
, which affects the details of node deletion.
While a Red-Black tree can be constructed from nodes alone, the Tree::RedBlack
API provides a cleaner way of working with Red-Black trees. Start there if only using the Red-Black tree as a container.
Attributes
Public Class Methods
Example¶ ↑
require 'tree/red_black' root = Tree::RedBlackNode.new(10) p root.key #=> 10 p root.color #=> :RED p root.parent #=> nil p root.left #=> nil p root.right #=> nil
# File lib/tree/red_black/red_black_node.rb, line 52 def initialize(value = nil, color = :RED) raise "color must be :RED or :BLACK" unless [:RED, :BLACK].include?(color) @left = @right = @parent = nil @key = value @color = color end
Public Instance Methods
Returns a node satisfying a criterion defined in block
by binary search.
If block
evaluates to true
or false
, returns the first node for which the block
evaluates to true
. In this case, the criterion is expected to return false
for nodes preceding the matching node and true
for subsequent nodes.
Example¶ ↑
require 'tree/red_black' shuffled_values = [*1..10].shuffle root = shuffled_values.reduce(Tree::RedBlackNode.new) do |acc, v| acc.insert_red_black(v) end root.bsearch { |node| node.key >= 7 } #=> <Tree::RedBlackNode:0x00... @key=7 ...>
If block
evaluates to <0
, 0
or >0
, returns first node for which block
evaluates to 0
. Otherwise returns nil
. In this case, the criterion is expected to return <0
for nodes preceding the matching node, 0
for some subsequent nodes and >0
for nodes beyond that.
Example¶ ↑
require 'tree/red_black' shuffled_values = [*1..10].shuffle root = shuffled_values.reduce(Tree::RedBlackNode.new) do |acc, v| acc.insert_red_black(v) end root.bsearch { |node| 7 <=> node.key } #=> <Tree::RedBlackNode:0x00... @key=7 ...>
If block+
is not given, returns an enumerator.
# File lib/tree/red_black/red_black_node.rb, line 227 def bsearch(&block) return enum_for(:bsearch) unless block_given? return nil if key.nil? result = block.call(self) case result when Integer if result > 0 right ? right.bsearch(&block) : nil elsif result < 0 left ? left.bsearch(&block) : nil else self end when TrueClass, FalseClass if result left ? (node = left.bsearch(&block); node ? node : self) : self else right ? right.bsearch(&block) : nil end else nil end end
Deletes the given value
from a tree whose root node is self
. If the tree has only one remaining node and its key
attribute matches value
, then the remaining node's key
attribute is set to nil
but the node itself is not removed. Otherwise, the first node found whose key
matches value
is removed from the tree, and the tree is re-balanced. The root of the balanced tree is returned.
Example¶ ↑
require 'tree/red_black' root = [*1..10].reduce(Tree::RedBlackNode.new) do |acc, v| acc.insert_red_black(v) end root = [*4..8].reduce(root) do |acc, v| acc.delete_red_black(v) end root.map(&:key) #=> [1, 2, 3, 9, 10]
# File lib/tree/red_black/red_black_node.rb, line 147 def delete_red_black(value) if key.nil? nil elsif value > key right ? right.delete_red_black(value) : nil elsif value < key left ? left.delete_red_black(value) : nil else if left && right node = right.min @key = node.key node.substitute_with_child else substitute_with_child end end end
Returns a deep copy of the tree with root self
, provided that the dup
method for the key
attribute of a node is also a deep copy.
Example¶ ↑
require 'tree/red_black' root = Tree::RedBlackNode.new({a: 1, b: 2}) root_copy = root.dup p root.key #=> {:a=>1, :b=>2} p root.key.delete(:a) #=> 1 p root.key #=> {:b=>2} p root_copy.key #=> {:a=>1, :b=>2}
# File lib/tree/red_black/red_black_node.rb, line 404 def dup copy = RedBlackNode.new(key.dup, color) if left copy.left = left.dup copy.left.parent = copy end if right copy.right = right.dup copy.right.parent = copy end copy end
Returns an enumerator for nodes in the tree with root self
by in-order traversal.
Example¶ ↑
require 'tree/red_black' shuffled_values = [*1..10].shuffle root = shuffled_values.reduce(Tree::RedBlackNode.new) do |acc, v| acc.insert_red_black(v) end root.in_order.map(&:key) #=> [1, 2, ..., 10]
# File lib/tree/red_black/red_black_node.rb, line 380 def in_order(&block) return enum_for(:in_order) unless block_given? left.in_order(&block) if left yield self right.in_order(&block) if right end
Since a Red-Black tree maintains an ordered, Enumerable collection, every value inserted must be Comparable with every other value. Methods each
, map
, select
, find
, sort
, etc., can be applied to a Red-Black tree's root node to iterate over all nodes in the tree.
Each node yielded by enumeration has a key
attribute to retrieve the value stored in that node. Method each
, in particular, is aliased to in_order
, so that nodes are sorted in ascending order by key
value. Nodes can also be traversed by method pre_order
, e.g., to generate paths in the tree.
Example¶ ↑
require 'tree/red_black' root = Tree::RedBlackNode.new p root.key #=> nil root = root.insert_red_black(0) p root.key #=> 0 root = root.insert_red_black(1) p root.key #=> 0 p root.left #=> nil p root.right.key #=> 1 root = root.insert_red_black(2) p root.key #=> 1 p root.left.key #=> 0 p root.right.key #=> 2
# File lib/tree/red_black/red_black_node.rb, line 113 def insert_red_black(value, allow_duplicates = true) node = allow_duplicates ? insert_key(value) : insert_unique_key(value) return nil if node.nil? node.color_insert while node.parent node = node.parent end node end
Returns the node whose key
is a maximum in the sub-tree with root self
.
Example¶ ↑
require 'tree/red_black' root = [*0..10].reduce(Tree::RedBlackNode.new) do |acc, v| acc.insert_red_black(v) end root #=> <Tree::RedBlackNode:0x00..., @key=4, ...> root.max #=> <Tree::RedBlackNode:0x00..., @key=10, ...> root.left #=> <Tree::RedBlackNode:0x00..., @key=2, ...> root.left.max #=> <Tree::RedBlackNode:0x00..., @key=3, ...>
# File lib/tree/red_black/red_black_node.rb, line 291 def max node = self while node.right node = node.right end node end
Returns the node whose key
is a minimum in the sub-tree with root self
.
Example¶ ↑
require 'tree/red_black' root = [*0..10].reduce(Tree::RedBlackNode.new) do |acc, v| acc.insert_red_black(v) end root #=> <Tree::RedBlackNode:0x00..., @key=4, ...> root.min #=> <Tree::RedBlackNode:0x00..., @key=0, ...> root.right #=> <Tree::RedBlackNode:0x00..., @key=6, ...> root.right.min #=> <Tree::RedBlackNode:0x00..., @key=5, ...>
# File lib/tree/red_black/red_black_node.rb, line 268 def min node = self while node.left node = node.left end node end
Returns an enumerator for nodes in the tree with root self
by pre-order traversal.
Example¶ ↑
require 'tree/red_black' root = [*1..10].reduce(Tree::RedBlackNode.new) do |acc, v| acc.insert_red_black(v) end root.pre_order.map(&:key) #=> [4, 2, 1, 3, 6, 5, 8, 7, 9, 10]
# File lib/tree/red_black/red_black_node.rb, line 359 def pre_order(&block) return enum_for(:pre_order) unless block_given? yield self left.pre_order(&block) if left right.pre_order(&block) if right end
Returns the node preceding self
, or nil
if no predecessor exists. If duplicate keys are allowed, it's possible that pred.key == key
.
Example¶ ↑
require 'tree/red_black' root = [*1..10].reduce(Tree::RedBlackNode.new) do |acc, v| acc.insert_red_black(v) end root.right.right.key #=> 8 root.right.right.pred.key #=> 7
# File lib/tree/red_black/red_black_node.rb, line 313 def pred return left.max if left node = parent while node && node.key > key node = node.parent end node end
Returns a node whose key
matches value
by binary search. If no match is found, calls non-nil ifnone
, otherwise returns nil
.
Example¶ ↑
require 'tree/red_black' shuffled_values = [*1..10].shuffle root = shuffled_values.reduce(Tree::RedBlackNode.new) do |acc, v| acc.insert_red_black(v) end root.search(7) #=> <Tree::RedBlackNode:0x00..., @key=7, ...>
# File lib/tree/red_black/red_black_node.rb, line 178 def search(value, ifnone = nil) if key.nil? ifnone && ifnone.call elsif value > key right ? right.search(value, ifnone) : ifnone && ifnone.call elsif value < key left ? left.search(value, ifnone) : ifnone && ifnone.call else self end end
Returns the node succeeding self
, or nil
if no successor exists. If duplicate keys are allowed, it's possible that succ.key == key
.
Example¶ ↑
require 'tree/red_black' root = [*1..10].reduce(Tree::RedBlackNode.new) do |acc, v| acc.insert_red_black(v) end root.right.right.key #=> 8 root.right.right.succ.key #=> 9
# File lib/tree/red_black/red_black_node.rb, line 337 def succ return right.min if right node = parent while node && node.key < key node = node.parent end node end