Explain Deletion Operation From a Red-Black Tree | Data Structure Tutorial
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.
- Take the deletenode.
- Save the color of the deletenode in initialColor.
- If the left child of the deletenode is NULL, then
- Set the right child of deletenode to m.
- Change the deletenode with m.
- Perform the 3rd step in the vice-versa way, if the right child of the deletenode is NULL.
- Otherwise,
- Set the minimum value of the right subtree of deletenode into n.
- Save the color of the n in initialColor.
- Set the rightchild of n into m.
- If n is the child of the deletenode, then set the value of parent m as n.
- Or change n with rightChild of m.
- Set the color of m with the initialcolor.
- 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:
- It held out the root node.
- If i point to a red-black node. In this scenario, i is colored black.
- Satisfactory rotations and recoloring are performed.
The algorithm that can retain the properties of a red-black tree:
- Perform the following steps until the i is not the root of the tree and the color of i is black.
- If i is the left child of its parent, then
- Assign x to the siblings of i.
- If the sibling of i is red.
Case I:
- Put the color of the right child of the parent of i as black.
- Put the color of the parent of i as red.
- Rotate it to the left of the parent as i.
- 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:
- Put the color red to x.
- Assign the parent of i as i.
d. Or else, the color on the rightchild of x is black.
Case III:
- Put the color of the leftchild of x as black.
- Put the color of x as red.
- Right rotation x.
- 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:
- Put the color of x as the color of the parent of i.
- Put the color of the parent of i as Black.
- Put the color on the rightchild of x as black.
- Rotate left the parent of i.
- 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.