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

color[RW]
key[RW]
left[RW]
parent[RW]
right[RW]

Public Class Methods

new(value = nil, color = :RED) click to toggle source

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

bsearch(&block) click to toggle source

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
delete_red_black(value) click to toggle source

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
dup() click to toggle source

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
each(&block)
Alias for: in_order
in_order() { |self| ... } click to toggle source

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
Also aliased as: each
insert_red_black(value, allow_duplicates = true) click to toggle source

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
max() click to toggle source

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
min() click to toggle source

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
pre_order() { |self| ... } click to toggle source

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
pred() click to toggle source

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
succ() click to toggle source

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