Explain an Insertion Operation in a Red-Black Tree | Data Structure Tutorial

In this article, you will learn about Insertion Operation in a Red-black Tree.

The red-Black tree is a self-balancing binary search tree in which each node has an extra bit for denoting the color of the node, either red or black. 

The new node in the Red-black tree is always inserted in a Red color node. After performing the insertion operation, if the tree is invading the properties of the red-black tree then we have to perform the following operations:

1. Recolor
2. Rotation

The Algorithm to insert a New Node:

The Steps that need to be followed to insert a new item into a red-black tree:

1. Take the new node i.
2. Let m be the leaf and n be the root of the Red-Black Tree. 
3. First, we need to check whether the tree is empty. If yes, insert i(i.e new node) as a root node of the tree in black color.
4. Otherwise, perform the following steps until we reach the leaf's value NIL.
1. Compare the value of newkey with the rootKey.
2. If the newkey is greater than the rootkey, go to the right subtree.
3. Or go to the left subtree.
5. Now, allocate the parent of the leaf as the parent of the i (i.e new node).
6. If the value of the leafkey is greater than the value of the newkey, make the i as rightChild.
7. Or else make i (i.e new node) as leftChild.
8. Now, the value of the leftChild and rightChild of the newNode is Null.
9. Color the newNode as RED.
10. If the property of the red-black tree is broken, then immediately call the InsertFix - algorithm.

Give a reason to assign the red color to the new node in the Red-black Tree.

We insert the new node in a red color node because it does not invade the depth property of a Red-black tree. If we entangle the red node into a red node, then the rule is broken. 

Algorithm to keep the property of Red-black Tree, after insertion operation:

This particular algorithm is used in preserving the property of a Red-Black tree if it broke while performing the insertion operation

1. Perform the following steps until the color of the parent node n is RED.
2. If n is the left child of grandParent gn of newNode, execute the following steps:

Case - I:

1. Suppose, the color of the right child of the gn of n is RED, then assign the black color to the children of the gn and change the color of the gn to RED.
2. Set gn to the n (i.e new node).

Case - II:

1. Before executing this step, we need to check the value of the while loop. If the condition is not satisfied, then the loop is broken. Else if the new node is the right child of n, then set p to the new node.
2. Do left rotate in newnode n.

Case - III:

1. Again the condition of the while loop is checked, if not satisfied, it means the loop is broken. Now, set the color of n as BLACK and the color of the grandparent gn as RED.
2. Do Right-Rotate in gn.

3. Otherwise, perform the following steps:

1. If the color of the left child of gn of q is RED, assign the color of both the children of gn as BLACK and the color of gn as RED.
2. Set gn to a new node.
3. Else if the newnode is the left child of n, then set n to the newnode and do the right rotation of the newnode.
4. Set the color of n as BLACK and the color of gn as RED.
5. Do left rotation gn.

4. After all this, set the color of the root node as BLACK.