Explain Deletion Operation From a Red-Black Tree | Data Structure Tutorial

In this article, you will understand how to perform deletion from 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. 

Similar to the insertion operation, deleting a node from the tree can also intrude on the properties of the Red-Black Tree. To fix the properties, we again use the fixing algorithm to regain the red-black properties.

Delete an element from a Red-Black Tree

It deletes a node from the tree. Once the operation is finished, the red-black property is maintained.

1. Take the deletenode.
2. Save the color of the deletenode in initialColor.
3. If the left child of the deletenode is NULL, then
1. Set the right child of deletenode to m.
2. Change the deletenode with m.
4. Perform the 3rd step in the vice-versa way, if the right child of the deletenode is NULL.
5. Otherwise, 
1. Set the minimum value of the right subtree of deletenode into n.
2. Save the color of the n in initialColor.
3. Set the rightchild of n into m.
4. If n is the child of the deletenode, then set the value of parent m as n.
5. Or change n with rightChild of m.
6. Set the color of m with the initialcolor.
6. If the initialColor is BLACK, call the DeleteFix(m) function.

Algorithm to keep the Red-Black Property after the deletion operation:

This algorithm is only implemented when we need the black node from the tree because it violates the black depth property. The property break only happens when node m has an extra black. This makes the node m neither red nor black. It can be either double black-and-end or black. It violates the red-black property. 

The extra black can be deleted only if:

1. It held out the root node. 
2. If i point to a red-black node. In this scenario, i is colored black. 
3. Satisfactory rotations and recoloring are performed. 

The algorithm that can retain the properties of a red-black tree:

1. Perform the following steps until the i is not the root of the tree and the color of i is black. 
2. If i is the left child of its parent, then 
1. Assign x to the siblings of i. 
2. If the sibling of i is red. 

Case I:

1. Put the color of the right child of the parent of i as black. 
2. Put the color of the parent of i as red.
3. Rotate it to the left of the parent as i. 
4. Assign the rightchild of the parent of i as x.

c. if the color of both the right and the leftchild of x is black.

Case II:

1. Put the color red to x. 
2. Assign the parent of i as i. 

d. Or else, the color on the rightchild of x is black. 

Case III:

1. Put the color of the leftchild of x as black.
2. Put the color of x as red. 
3. Right rotation x.
4. Assign the rightchild of the parent of i as x.

e. If any of the above cases do not occur, then do the following steps:

Case VI:

1. Put the color of x as the color of the parent of i.
2. Put the color of the parent of i as Black. 
3. Put the color on the rightchild of x as black.
4. Rotate left the parent of i.
5. Set the i as the root of the tree. 

3. Otherwise, follow the above step on the right to the left and vice-versa.

4. Set the color of the i as black.