Red Black Trees !

A journey of thousand miles begins with a single step” – Unknown

This post is a part of IIT-M CSE “Concept-Sunday” series .


src : http://wallpaperswide.com/lone_red_tree-wallpapers.html ; http://www.blacktreepublishing.co.uk

Well, color makes a difference – no I am not at all being racist; you ask a data structure guy and he will surely convince you that color does matter. From back to white to red – some special data structures internally use colors to organise(or distinguish) the data. Red Black trees belong to this special class, but having said that I still wonder why did they name it red-black trees and not white-black trees. Some say inventors made use of red and black pens extensively whereas others claim that they liked the red color prints coming out their printers.

We don’t know what is right and what is wrong; the truth is last week we talked about AVL trees and this week we are are back with a similar setup! Today we will discuss about Red Black trees which have been gained popularity for right reasons 🙂

Red Black trees are yet another balanced Binary search tree, with different balancing strategy that fares well in some areas as compared to AVL trees. From now on wards we will refer to Red Black trees as RB trees wherever necessary. RB tree does better at insertion and deletion while AVL tree is  better at searching. So if your application needs faster insertion and deletion RB trees fit in well whereas if your application is query intensive you are better off with our good old AVL trees. AVL trees have somewhat strict balancing strategy that makes insertion and deletion a costly affair but as a result height of the tree is better balanced, which makes search/query faster. However RB trees with their weaker balancing strategy complete insertion and deletion in one single pass(log n) through the tree.

Back with AVL trees we used the balance factor to check balance; with RB trees, we use the colour of the nodes and certain properties to check and maintain the balance of the tree.

Red Black Tree is characterised by following properties :

  1. Every node is either red or black
  2. Root and leaves (nil’s ) are black
  3. There can never be  2 consecutive red nodes  (alternatively mentioned as , a red node always has a black parent. )
  4. All simple paths from a node ‘x’ to a descendent leaf have the same number of black nodes in them.

Insertion in a Red Black Tree

Since the structure of RB tree is same as that of the binary search tree, searching for the location to insert is same as BST / AVL. The goal however here, is to maintain the Red Black Tree properties  .

If the tree is empty simply create a single black node and mark it as root node.

And if the tree is non-empty

  • Search for the location, and insert the node
  • colour the node- Red
  • Now restore red-black tree properties (if required )

Searching and inserting the node follows the same procedure as BST; there is no rocket science in colouring node red either 😉 So the only thing that’s important here is algorithm involved in restoring the red-black tree properties.  The only property that may be violated is property 2 and property 3. It may happen that the newly added node is the only node making a red node as root node(we have already talked about this case earlier) or it may happen that they added node is child of a red node violating property 3.

The idea behind colouring the newly inserted node with Red , is that only property 3(property 2 violation is trivial) can be violated which can then be solved by either

  • Recolouring , or by
  • Rotation (as in AVL trees )

We move the violation in the RB Tree upwards and solve it using the above mentioned options. Next we dissect the restoration of red-black tree into several case and consider each case in detail.

Suppose, 

  • x is the newly added node 
  • p refers to the parent node
  • u refers to the uncle node
  • g refers to the grandparent node.

Case 1 : If the color of x’s parent is black :

In this case we don’t have to worry, because the tree still satisfies the properties 🙂 

Case 2: If the color of x’s parent is red : (Note that we have now violated rule 3).

   Case 2.A :If the color of x’s uncle is red :

   Note : the grandparent will be black in this case

   We perform following steps here:

  •  Recolour x’s parent and uncle with Black.
  •  Recolour the grandparent to Red.  (This will violate Rule 3 for the grandparent )
  •  Now consider the grandparent to be the newly inserted node , and repeat Case 2.
case1

If both parent and uncle are red- color parent and uncle as black and grand parent as  red.

Case 2.B: If the color of x’s uncle is black

(NOTE : In this case  the grandparent  has 2 children, one of them is red who is the parent of the newly inserted node , and the other is uncle whose color is black. We now know that the grandparent node has paths to leaves of the tree with unequal black nodes in them . Hence in order to preserve the properties of RB Tree, we need some operations)

We consider four sub cases here and rotation cum recolouring  diagram for each case will ensure that the RB Tree properties are satisfied.

1. LL Case : p is to the left of g, and x is to the left of p

ll_case

LL Case : Perform right rotation followed by color exchange between g and p

2. LR Case : p  is to the left of g , and x is to the right of p

lr_case
LR Case : Perform left rotation, the situation now becomes same as the LL case

3. RR Case : p is to the right of g, and x is to the right of p

rr_case.PNG

RR Case : Perform left rotation followed by color exchange between g and p

4. RL Case : p is to the right of g, and x is to the left of p

rl_case

RL Case : Perform right rotation, the situation now becomes same as the RR case

Feel free to check out these pages for animations of Red Black Tree operations

Content credit : Ganesh K .

One thought on “Red Black Trees !

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s