Red Black Tree

Red Black Trees

Red-black trees are a variation of binary search trees to ensure that the tree is balanced. In a Red Black Tree, every node is colored either RED or BLACK. The color of the node is decided based on the properties defined below:

1. Red Black Tree must be a Binary Search Tree.
2. The ROOT node must be colored BLACK.
3. The children of Red colored node must be colored BLACK. (There should be no consecutive RED nodes.)
4. In all the paths of the tree, there must be same number of BLACK colored nodes.
5. Every new node must be inserted with RED color.
6. Every leaf (i.e. NULL node) must be colored BLACK.

Example:

For conveinence, we use a sentinel NIL[T] to represent all the NIL nodes at the leafs.

• NIL[T] has the same fields as an ordinary node
• Color[NIL[T]] = BLACK
• The other fields may be set to arbitrary values

Insertion into a RED BLACK Tree

In a Red Black Tree, every new node inserted is colored RED. The insertion operation in Red Black Tree is similar to insertion operation in Binary Search Tree with the additional color property. After every insertion operation, we need to check all the properties of Red Black Tree. If all the properties are satisfied then we go to next operation, otherwise we need to perform following operations to make it Red Black Tree:

1. Recolor
2. Rotation followed by Recolor

The insertion operation in Red Black Tree is performed using the following steps:

1. Check whether tree is EMPTY
2. If the tree is Empty then insert the newNode as Root node with colorBlack and exit from the operation
3. If tree is not Empty then insert the newNode as a leaf node with Red color
4. If the parent of newNode is Black then exit from the operation
5. If the parent of newNode is Red then check the color of parent node's sibling of newNode
6. If it is Black or NULL node then make a suitable Rotation and Recolor it
7. If it is Red colored node then perform Recolor and Recheck it. Repeat the same until tree becomes Red Black Tree

Example:

Create a RED BLACK Tree by inserting following sequence of numbers: 8, 18, 5, 15, 17, 25, 40 and 80.

1. Insert (8)

Tree is Empty. So, insert newNode as Root node with blackcolor.

2. Insert (18)

Tree is not Empty. So, insert newNode with red color.

3. Insert (5)

Tree is not Empty. So insert newNode with red color.

4. Insert (15)

Tree is not Empty. So, insert newNode with red color.

5. Insert (17)

Tree is not Empty. So, insert newNode with red color.

6. Insert (25)

Tree is not Empty. So, insert newNode with red color.

7. Insert (40)

Tree is not Empty. So, insert newNode with red color.

8. Insert (80)

Tree is not Empty. So, insert newNode with red color.

Finally, above tree is satisfying all the properties of a Red Black Tree. So, it is a perfect Red Black Tree.

References

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, “Introduction toAlgorithms”
2. G. Brassard and P. Bratley, “Fundamentals of Algorithms”
3. R. L. Kruse, B. P. Leung, C. L. Tondo, “Data Structure and Program designin C”