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


3 comments:

  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
  2. شركة نقل اثاث بالرياض  http://url.ie/13xnl  نقل عفش بتعتبر أعمال نقل العفش من أهم الأعمال على الاطلاق ؛فالكثير من الأفراد يحتاجون الى القيام بأعمال النقل المميزة لحمايه كافه أجزاء الاثاث من التعرض للتكسير أو الخدوش وغيرها من الأمور الأخرى ؛لذلك نحن شركة نقل عفش بالرياض التى تعتمد على أفضل العاملين المتخصصين وأفضل الأساليب الحديثة للقيام بنقل جميع أجزاء الاثاث سواء غرف النوم والسفر والصالونات وغيرها من الأدوات المكتبية والأدوات الخاصه بالأمور الفندقية وغيرها من أجزاء الاثاث التى تتعلق بالشقق والقصور والفلل وجميع الأمور الأخرى .

    تتخصص الشركة فى أعمال نقل الأجهزة الكهربية وغيرها من الأمور الأخرى التى تتعلق بالمطابخ وغيرها من الأمور الأخرى ؛فقط نحن شركة نقل عفش بالرياض التى تعتمد على أفضل الأساليب الحديثة والطرق المميزة للقيام بأعمال نقل العفش .… اقرأ المزيد

    المصدر: شركة نقل اثاث بالرياض

    شركة كشف تسربات المياه بالرياض http://url.ie/13xmw علامات الاستدلال على التسربات المائية بالرياض ؟
    هناك عدة علامات بارزة تدل على تعرض المواسير المائية للعديد من التسربات الخطيرة :
    1-تعرض الحوائط والأسقف للتسربات المائية وسقوطها على الأرضيات .

    2-ارتفاع فواتير الاستهلاك المائية عن المعدلات الطبيعيه .

    3-تعرض الحوائط للعديد من التشققات والتصدعات نتيجو رشح مياه المواسير على الجوانب المنزليه المختلفه .

    4-تعرض الدهانات للعديد من القشور والتلفيات والسقوط مما يشوه من المظهر الخارجى للأرضيات .

    5-تعرض الأرضيات من سيراميك وبلاط وباركيه للعديد من المخاطر والتلفيات نتيجة تساقط المياه على الأرضيات .

    كيفيه القيام بكشف التسربات المائية بالرياض ؟
    تعتمد شركة اصلاح تسربات المياه على مجموعه من الطرق الحديثة والمعدات والأجهزة المميزة للقيام بأعمال كشف التسربات المائية ومن أبرز الأمور :

    1-الاعتماد على أجهزة الكورليشين
    تتمكن كشف تسربات المياه بالرياض من الاعتماد على أفضل الأجهزة الحديثة وخاصه أجهزة الكورليشين التى تتمكن من الكشف عن التسربات المائية وتأثيراتها السلبيه الخطيرة .

    2-الاعتماد على أجهزة التحسس الأرضية
    لا يمكن للأذن البشرية معظم الوقت التعرف على أماكن التسربات المائية وتحديدها بشكل كبير ؛لذلك يمكن الاعتماد على أجهزة الاستماع الأرضية التى تصدر مجموعه من الذبذبات التى تتمكن من التعرف على أماكن التسربات المائية .

    3-الاعتماد على أجهزة الايكوفون
    تتمكن الشركة من الاعتماد على أفضل الأجهزة الالكترونية الحديثة وخاصه أجهزة الايكوفون التى تطلق مجموعه من القراءات العلمية البحته ؛تلك الأجهزة تتتمكن من الكشف عن التسربات المائية سريعا ؛وخاصه التسربات المتواجدة فى الأماكن المختفيه وخاصه الأماكن التى تتواجد خلف المغاسل أو الأحواض ؛وتصل معدلات الدقة بهذه الأجهزة الى 96 % وهى نسبة كبيرة مقارنة بالنسب الأخرى التى تصدرها الأجهزة الأخرى .

    4-الاعتماد على الأجهزة الالكترونية
    تعتمد شركة اصلاح تسربات المياه على مجموعه من الأجهزة الحديثة التى تصدر مجموعه من الذبذبات والاشارات التى تتعرف على أماكن التسربات المائية وتساعد على معالجتها سريعا والتخلص منها .

    خطوات الكشف عن التسربات المائية
    تتمكن شركة اصلاح تسربات المياه من الاعتماد على أفضل أجهزة التسربات المائية وبالقيام بالخطوات الأتيه :

    1-يتم فحص المكان جيدا والكشف عن البدرومات وعزل الأسطح وحمامات السباحة وغيرها من الأمور الأخرى .

    2-فحص جدران المنازل وفحص نبضات التسربات المائية عبر مجموعه من أحدث الأساليب .

    3-امكانيه الكشف عن التسربات المائية دون القيام بأى أعمال تكسير ؛واذا تم القيام بأى أعمال كسر أو تلفيات يتم معالجتها دون التسبب فى ترك أى شروخ بالمكان .… اقرأ المزيد

    المصدر: شركة كشف تسربات المياه بالرياض

    ReplyDelete


  3. افضل شركة شفط بيارات بالرياض http://url.ie/13xnp فريقنا يستخدم بفخر حلول التنظيف السكنية التي هي مسئوليتنا بيئياً , حيث لدينا طرق شفط البيارات صديقة للبيئة .هل ترغب في أن يكون لديك المزيد من وقت الفراغ؟ يمكننا أن نجعل ذلك يحدث!… اقرأ المزيد

    المصدر: شركة شفط بيارات بالرياض

    ReplyDelete