“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 :
- Every node is either red or black
- Root and leaves (nil’s ) are black
- There can never be 2 consecutive red nodes (alternatively mentioned as , a red node always has a black parent. )
- 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.
- 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.
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
2. LR Case : p is to the left of g , and x is to the right of p
3. RR Case : p is to the right of g, and x is to the right of p
4. RL Case : p is to the right of g, and x is to the left of p
Feel free to check out these pages for animations of Red Black Tree operations
Content credit : Ganesh K .