Monday, October 15, 2012

Red Black Tree: Insertion

If this is your first attempt to understand red-black tree, please watch this video lecture. It will give you a solid foundation. Next, before you start to this tutorial, make sure:
  1. You are not in a hurry. (In that case, just use the code from the link in footnote)
  2. You do not get impatient.
  3. You do not bother why it works. It works. Once you get the algorithm and code it, it will be much simpler to visualize how it works. But, for 'why' -- you may need to research.
So, here we go

One Aim: Approximately balanced tree creation. From root to leaf, no (simple) path is more than twice as long as any other.

Two Rules: (CLRS says five, but others are trivial)
  1. Color Constraint: Red nodes will have both of it's children black. Black nodes can have either.
  2. Number Constraint: For each node, simple path to all the leaves will have same numbers of black children.
Three Situations: Couple of points to be noted before we see the situations
  1. Wherever I refer Uncle, it means (same as in common life) -- "sibling of parent node", "the other child of node's parent's parent".
  2. We assume as NIL nodes of all the leaves are black.
  3. We always insert red node. So, We are not breaking #2: Number Constraint by adding a black node, but we are breaking constaint #1: Color Constraint.
  4. Keep the root node black. You will see, it makes life easier. It does not breaks any of the constraints.
Situations:
  1. A Red uncle is a good uncle: If newly inserted node has red uncle, we can fix the situation just by fixing colors. Invert parent, grand parent, and uncle's colors. Now we need to check if grandparent is satisfying the Color Constraint.

  2. A black uncle on opposite side wants one rotation: If the uncle is black, we got to rotate. A slightly better case is when the newly inserted node is left child of its parent and uncle is right child of its parent or vice versa. In that case, you make a left-rotation or a right-rotation (rotations will be discussed later in this post). And then fix colors.

  3. A black uncle on the same side is double as dangerous: A case when newly inserted node is right child and the black uncle is also right child or both are left children, you need to make a left-rotation if inserted node is right-child or right rotation if newly inserted node is left child. This will make it situation 2.

The good thing about finding a black uncle is your quest ends there. No need to look further up the tree.

Conceptually, you are done here. All left now is some slight minor details about plumbing rotation and a couple of fine prints in algorithm like some times rotation may cause root node reassignment, how we treat a NIL node a black node, etc.

Rotation: A rotation is basically to swap a parent and child such that the BST property still holds. So, why do we call it rotation? Well, the process mutates the tree in such a way that it looks, to a casual observer, as if the tree just did a Toe Loop Jump. (well, this is the best I can explain.)

People claim there are two type of rotations -- right, when left child swaps with it's parent (i.e. moves to right); and left rotation, when a right child swaps with it's parent. Basically, if you start with a tree and right rotate a child, then left rotate the original parent the tree stays unchanged. (Figure out how and why the nodes are snipped and pasted the way they are.)



The algorithm: (Please note the below is not a valid Python code, I have use Python-esque code so that code highlighter shows key areas)
root = NIL

def insert (node)
  if root = NIL
    root = node
    root.color = BLACK
    return
    
  parent = root
  current = root
  
  while current != NIL
    parent = current
    if node.value < root.value 
      current = current.left
    else
      current = current.right
      
  if node.value < parent.value
    parent.left = node
  else
    parent.right = node
    
  node.color = RED
  fixTree(node)
  
def fixTree (node)
  
  if node.parent == RED
    uncle = getUncle(node)
    
      
    #case 1: Uncle Red
    if uncle.color = RED
      node.parent.color = BLACK
      node.parent.parent.color = RED
      uncle.color = BLACK
      fixTree(node.parent.parent)
    
    #Case 2, 3: Sirius Black.
    else if parentInLeftSubTree(node)
      #we are in left subtree, uncle is right child
      #case 3: rotate to case 2
      if node.parent.right = node
        rotateLeft(node)
        
      #case 2: color fix and rotate
      node.color = BLACK
      node.parent = RED
      rotateRight(node)
        
    else
      #we are in right subtree, uncle is left child
      #case 3: rotate to case 2
      if node.parent.left = node
        rotateRight(node)
        
      #case 2: color fix and rotate
      node.color = BLACK
      node.parent = RED
      rotateLeft(node)
      
    root.color = BLACK
  
def getUncle (node)
  if node = NIL or node.parent = NIL
    return NIL
    
  parent = node.parent
  grandParent = parent.parent
  if grandParent = NIL
    return NIL
    
  if parent = grandParent.left
    return grandParent.right
  return 
    return grandParent.left
    
def parentInLeftSubTree (node)
    if node.parent = node.parent.parent.left    
      return true
    else
      return false

"""
 *         g                               g
 *        /                               /
 *       x        Left Rotation(y)       y
 *      / \      ---------------->      / \
 *  alpha  y     <----------------     x   gamma
 *        / \    Right Rotation(x)    / \
 *     beta gamma                 alpha  beta
"""
 
def rotateLeft(y)
   x = y.parent
   g = x.parent
   alpha = x.left
   beta = y.left
   gamma = y.right
   
   y.parent = g
   if g != NIL
     if g.left = x
       g.left = y
     else
       g.right = y
   else
     root = y
     
   x.parent = y
   y.left = x 
   
   x.right = beta
   if beta != NIL
     beta.parent = x
   
def rotateRight(x)
  y = x.parent
  g = y.parent
  alpha = x.left
  beta = x.right
  gamma = y.right
  
  x.parent = g
  if g != NIL
    if g.left = y
      g.left = x
    else
      g.right = x
  else
    root = x
    
  x.right = y
  y.parent = x
  
  y.left = beta
  if beta != NIL
    beta.parent = y
Footnotes:

[1] View a foundation video lecture. it worth watching.
[2] Simulate your input on of a red-black tree creation -- here
[3] View/download Java code for red-black tree from GitHub
[4] I haven't referred much from this chapter, but it may worth reading: Introduction to Algorithms: CLRS, chapter 13: Red-Black Trees
[5] The execution of the code for a sorted input a = {8, 11, 14, 18, 22, 23, 31, 37, 41, 47, 60, 74, 84, 87, 88, 97, 99}, generates the following tree


1 comment:

  1. Hi Nishant,
    I found this way to contact you. I want to ask a question about your post. I have tried this http://facebook.stackoverflow.com/questions/5058144/facebook-api-get-all-profile-pictures
    To get an albums photo. But I am unable to do this.
    here i am getting JSON array
    var data = JSON.parse(e.result).data;
    and here I am using it to get photos.
    "https://graph.facebook.com/" + data[x].id + "/photos?access_token=" + Ti.Facebook.accessToken,

    plz plz plz can you guide me to solve this problem.

    ReplyDelete