Red black tree in ruby.

red_black_tree_revisited.md

Red Black Tree revisit.

	TIME
INSERTION	O(log n)
DELETION	O(log n)
SEARCH	O(log n)

SPACE	O(n)

Introduction

Red black tree is a height-balanced bst data structure which slightly relief on its height balance restriction by introducing red and black color as a balance factor. Unlike AVL tree which strictly require its balance factor(height) should keep the same in each node, red black tree require 5 properties and provide less rotation in both insertion and deletion operations. Below list 5 properties and inspections about this data structure.

• It guarantee each insertion at most need 2 rotations and 3 rotations for each deletion.

• 5 properties are:

  1. A node must be colored as RED or BLACK.
  2. Root must be BLACK color.
  3. Null node must be colored as BLACK.
  4. There has no two consecutive RED nodes connected. Which means if a node is RED, then its father and children should be BLACK. If a node is RED, its left or right node must BOTH be BLACK.
  5. Any node has the same BLACK count from itself to the every leaf node.

• Due to above properties, red black tree guarantee the height would be at most 2*log(n+1), you can prove it by mathematical induction. http://www.cnblogs.com/skywang12345/p/3245399.html

  A red black tree's height would be at most 2log(n+1)
  n >= 2^(H/2) - 1
  -> 2^(H/2) <= n + 1
  -> H <= 2log(n+1)

How to build a Red Black Tree

First build A BST, at first step the insertion and deletion would be the same as building a BST.

Insertion

• If parent's color is BLACK, we dont have to do anything because inserted new node's color is RED.
• If you would allowed duplicated key value stored in BST, pick either greater or equal than current value to right sub-node, or smaller or equal thean current value to left node. A new insert node's color is always RED.

# red_black_tree_rev.rb#insert
def insert(key)
  node = root
  current = nil
  while node != nil
    current = node
    # allowed duplicate keys, set it to left node.
    node = node.key >= key ? node.left : node.right
  end

  node = RBNode.new(key)
  node.parent = current
  if current.key >= key
    current.left = node
  else
    current.right = node
  end

  # above is normal BST insertion

  # fix-up nodes
  insertion_fixup(node)
  root.color = RBNode::BLACK
end

Once we finish the BST insertion, we need auxiliary methods to help us build fixup process.

# red_black_tree_rev.rb
# aux method

def rotation(current)
  parent = current.parent
  node = yield(current)

  if parent
    if parent.left == current
      parent.left = node
    else
      parent.right = node
    end
  else
    @root = node
  end
end

# current:      c      =>      s
#              / \            / \
#             u   s    =>    c   r
#                / \        / \
#               l   r  =>  u   l
def left_rotate(current)
  node = current.right
  rotation(current) do |c|
    c.right = node.left
    node.left = c
    c.right.parent = c if c.right
    node.parent = c.parent
    c.parent = node
    node
  end
end

# current:      c    =>    u
#              / \        / \
#             u   s  =>  l   c
#            / \            / \
#           l   r    =>    r   s
def right_rotate(current)
  node = current.left
  rotation(current) do |c|
    c.left = node.right
    node.right = c
    c.left.parent = c if c.left
    node.parent = c.parent
    c.parent = node
    node
  end
end

def get_uncle(c)
  c.parent.parent && c.parent.parent.left == c.parent ?
     	c.parent.parent.right : c.parent.parent.left
end

The insertion fixup code is in below, the idea is bubble the red color to upper node, if up to root, then switch to black.

memo tips:
1. flip color when parent and uncle both red then bubble up
2. reshape from triangle to line, if it is a line shape, grant parent rotate it and bubble up
3. rotate node always be current node in next fix-up.

# red_black_tree_rev.rb#insert_fixup

# case1 : parent is red, uncle is red
#   set unclde and parent to black, grand parent to red,
#   set current to grand parent. (bubble up, repeat fixup process)
#
# case2 : parent is red, uncle at right, current is right child
#        g
#       / \
#      p   u     => hint: the link from g to c shape likes a triangle
#     / \
#    x   c
#   set parent as current, left rotate parent.
#   repeat fixup process.
#
# case3 : parent is red, uncle at right, current is left child
#        g
#       / \
#      p   u     => hint: the link from g to c shape likes a line
#     /
#    c
#   set parent to black, grand parent to red.
#   set current to grand parent, right rotate grand parent.
# 
# If parent at right, uncle at left:
#   switch all left and right operations and condition checks.
#
# Repeat fixup process until hit root and change root to black.

# Policy: if current is as inside branch of parent (triangle shape), then rotate it out at parent(as current) (line shape), 
#         if as line shape, flip parent and grand parent colors, rotate at grand parent(as current) and all violations are eased.
#         ex: parent left red, uncle right black, current right red
#             1. left rotate parent, 
#                set current to parent, do point 2 fixup
#             2. recolor grand parent red, parent to black, 
#                right rotate grand parent, done.

def insertion_fixup(current)
  # root must be black, which means parent must not be root at start.
  # it also proves it must have grand parent node at start.
  while current.parent && current.parent.color == RBNode::RED
    uncle = get_uncle(current)
    parent = current.parent

    # uncle is leaf => color is black
    if (uncle == nil) || (uncle && uncle.color == RBNode::BLACK)
    
      # if uncle is at right, parent at left.
      if parent.parent.left == parent
      	# from shape triangle to line
      	if parent.left != current
	  # case 2
          left_rotate(parent)
          current = parent
	  parent = current.parent
	end

	# grand parent rotation from line shape
        if parent.left == current
          # case 3
          parent.color = RBNode::BLACK
          parent.parent.color = RBNode::RED
          right_rotate(parent.parent)
          # will break because parent color has changed to black.          
        end
      else
        # from shape triangle to line
      	if parent.right != current
	  # case 2 reverse version
          right_rotate(parent)
          current = parent
	  parent = current.parent
	end
	
	# grand parent rotation from line shape
        if parent.right == current
          # case 3 reverse version
          parent.color = RBNode::BLACK
          parent.parent.color = RBNode::RED
          left_rotate(parent.parent)
          # will break because parent color has changed to black.  
        end
      end
    elsif uncle && uncle.color == RBNode::RED
      # case 1
      parent.color = RBNode::BLACK
      uncle.color = RBNode::BLACK
      parent.parent.color =  RBNode::RED
      current = parent.parent
    end
  end
end

Deletion

BST deletion

• If target node has only one child, then just delete that node and make the child connect to its faher, no rebalancing needed.
• If target node does not have any children, just delete it, no rebalancing needed (nil node will replace it and color as BLACK).
• If target node has left and right child, then find successor in right sub paths; copy the successor's value to target node, and delete successor node. Now consider the successor, we only have the case that successor only has right child (one child), otherwise the successor should be its left child instead. So, connect successor's parent and successor's right child, then delete the successor node.

Analysis of rebalancing black count

• why delete either successor or predecessor?
  • Because merely copying a value from successor or predecessor does not violate any red–black properties, this reduces to the problem of deleting a node with at most one non-leaf child (successor or predecessor).
• successor have two child nodes would never occur o.w. its left child should be successor node instead, Therefore, for the remainder of this discussion we address the deleted successor node with at most one non-leaf child (N).
• If successor node is RED, we don't need to do any rebalancing since non-leaf child node sub-paths maintain the same black count as before deletion.
• If successor node is BLACK and has only one child, then its child must be RED, o.w. it will not get the same black count from both left and right sub-paths. In this case, we simply color successor node's child to black and restore the property 5.
• If successor node is BLACK and 2 black leaf nodes, then we need fixup, and leafs extra color now assume to BLACK(from deleted successor node), so we can reduce the property 5.

The leaf nodes of red–black trees do not contain data. These leaves need not be explicit in computer memory—a null child pointer can encode the fact that this child is a leaf—but it simplifies some algorithms for operating on red–black trees if the leaves really are explicit nodes. To save execution time, sometimes a pointer to a single sentinel node (a terminated node, instead of a null pointer) performs the role of all leaf nodes; all references from internal nodes to leaf nodes then point to the sentinel node.

Let's start at normal BST deletion.

# red_black_tree_rev.rb#delete
def delete(key)
  node = root
  while node != nil && node.key != key
    #current = node
    node = node.key > key ? node.left : node.right
  end

  # cannot find deleted node.
  return if node == nil

  # BST node deletion.
  parent = node.parent
  child = nil
  if node.left && node.right
    # we find its successor, that succ must only has one child.
    # Other wise it cannot be succ for the node(can go deeper).
    succ = find_successor(node)
    node.key = succ.key

    # We know succ must at left most sub node.
    # So succ.left must equal to nil
    parent = succ.parent
    node = succ
    if succ.right != nil
      child = succ.right
    end
  elsif !node.left and node.right
    child = node.right
  elsif node.left and !node.right
    child = node.left
  end

  if parent
    parent.left == node ? parent.left = child : parent.right = child
    child.parent = parent if child
  else
    @root = child
    @root.parent = nil if root
  end

  # above is normal BST deletion

  # delete node (successor node) color is black, then we have to fix, o.w. don't need to change.
  # fixup deletion
  if node.color == BLACK
    deletion_fixup(child, parent)
  end
end

Auxiliarly methods to find successor, and a method return true for some cases we might treat current node as nil node which is BLACK color.

# red_black_tree_rev.rb
# aux methods

# Inorder traversal's successor
def find_successor(n)
  if n.right
    succ = n.right
    succ = succ.left while succ.left
  else
    succ = n.parent
    while succ && succ.right == n
      n = succ
      succ = succ.parent
    end
    succ = succ && succ.left == n ? succ : nil
  end
  succ
end

def find_predecessor(n)
  if n.left
    pred = n.left
    pred = pred.right while pred.right
  else
    pred = n.parent
    while pred && pred.left == n
      n = pred
      pred = pred.parent
    end
    pred = pred && pred.right == n ? pred : nil
  end
  pred
end

# This help us dont have to care about node is nil case.
def color_is_black(n)
  true if n == nil || n.color == BLACK
end

Deletion fixup do the similar thing as insertion fixup, the idea is: put the extra black to upper node, balance bottom nodes first. Consider all parent, sibling, sibling's left, and sibling's right color combinations.

if successor node is delete, replaced leaf node (nil node) is at left:

parent	sibling	sibling's left	sibling's right	valid fixtation case	violation	fixtation rule
R	R	R	R		consecutive red
R	R	R	B		consecutive red
R	R	B	R		consecutive red
R	R	B	B		consecutive red
R	B	R	R	v		case 6
R	B	R	B	v		case 5
R	B	B	R	v		case 6
R	B	B	B	v		case 4
B	R	R	R		consecutive red
B	R	R	B		consecutive red
B	R	B	R		consecutive red
B	R	B	B	v		case 2
B	B	R	R	v		case 6
B	B	R	B	v		case 5
B	B	B	R	v		case 6
B	B	B	B	v		case 3

# red_black_tree_rev.rb#deletion_fixup

# Extra color as black by in default is trying to reduce property 5
# So now only property 1, 2, 4 need to be considered.

# Setting extra color as black by in default is trying to reduce property 5
# So now only property 1, 2, 4 need to be considered.
# 4 cases will happened
# case 1: node is new root.
# =>	  then we don't need to do every thing.
#
# case 2: node at left, sibling is red, parent is black.
# =>      Set parent color to RED, sibling to BLACK, left rotate at parent.
# =>      Then reset sibling to parent's right(originally is sibling left).
#
# case 3: node at left, sibling is black, both sibling's children are black, parent is black.
# =>      Set sibling color to RED, set current to current's parent (done)
#
# case 4: node at left, sibling is black, both sibling's children are black, parent is red.
# =>      Set sibling color to RED, set current to current's parent (done)
#
# case 5: node at left, sibling is black, sibling's right child is black, left is red.
# =>      Set ulc(sibling's left child) to BLACK, sibling to RED.
# =>      Then right rotate at sibling. reset sibling to ulc.
# =>      This tend to reduce the 2 possible cases for one red in sibling children to one, as case 6 presumption.
#
# case 6: node at left, sibling is black, sibling's right child is red.
# =>      Set sibling's color to parent's color. parent set to BLACK
# =>      Urc set to BLACK, left rotate parent. set current to root to end of loop.
#
# sibling must exist if delete node is black

def deletion_fixup(c, p)
  while true
    # case 1
    if c == root
      c.color = BLACK
      break
    end
    
    p = c.parent
  
    if p.left == c
      sibling = p.right

      # case 2
      if !color_is_black(sibling)
        p.color = RED
        sibling.color = BLACK
        left_rotate(p)
      end
      
      sibling = p.right
      
      # parent is black, sibling, and sibling's children are all black
      # case 3
      if color_is_black(p) && color_is_black(sibling) && color_is_black(sibling.left) && color_is_black(sibling.right)
        sibling.color = RED
	c = p
	next
      end
      
      # parent is red, sibling, and sibling's children are all black
      # case 4
      if !color_is_black(p) && color_is_black(sibling) && color_is_black(sibling.left) && color_is_black(sibling.right)
        p.color = BLACK
        sibling.color = RED
	break
      end

      # above cases sibling children are all back, now reduce one of sibling child is red cases:
      # if sibling's left is red, sibling's right is black (triangle pattern again)
      # case 5
      if color_is_black(sibling) && !color_is_black(sibling.left) and color_is_black(sibling.right)
        sibling.color = RED
        sibling.left.color = BLACK
        right_rotate(sibling)
      end
      
      sibling = p.right

      # sibling's left is black, sibling's right is red, sibling is black
      # since one of sibling child is red cases are are reduce to only this case
      # now compare to current node again.
      # case 6
      if color_is_black(sibling) && !color_is_black(sibling.right)
        sibling.color = p.color
	p.color = BLACK
        sibling.right.color = BLACK
        left_rotate(p)
        break
      end
    else
      sibling = p.left

      # case 2
      if !color_is_black(sibling)
        p.color = RED
        sibling.color = BLACK
        right_rotate(p)
      end
      
      sibling = p.left
      
      # parent is black, sibling, and sibling's children are all black
      # case 3
      if color_is_black(p) && color_is_black(sibling) && color_is_black(sibling.left) && color_is_black(sibling.right)
        sibling.color = RED
	c = p
	next
      end
      
      # parent is red, sibling, and sibling's children are all black
      # case 4
      if !color_is_black(p) && color_is_black(sibling) && color_is_black(sibling.left) && color_is_black(sibling.right)
        p.color = BLACK
        sibling.color = RED
	break
      end
      
      # above cases sibling children are all back, now reduce one of sibling child is red cases:
      # if sibling's inner right is red, sibling's left is black (triangle pattern again)
      # case 5
      if color_is_black(sibling) && color_is_black(sibling.left) and !color_is_black(sibling.right)
        sibling.color = RED
        sibling.right.color = BLACK
        right_rotate(sibling)
      end
      
      sibling = p.left

      # sibling's left is red, sibling's right is black, sibling is black
      # since one of sibling child is red cases are are reduce to only this case
      # now compare to current node again.
      # case 6
      if color_is_black(sibling) && !color_is_black(sibling.left)
        sibling.color = p.color
	p.color = BLACK
        sibling.left.color = BLACK
        right_rotate(p)
        break
      end
    end
  end
end

References

1. http://www.cnblogs.com/skywang12345/p/3245399.html
2. https://en.wikipedia.org/wiki/Red%E2%80%93black_tree
3. https://youtu.be/A3JZinzkMpk
4. https://blog.csdn.net/v_JULY_v/article/details/6105630