Red-Black Tree Deletion
Explore the Red-Black Tree deletion process by understanding how to remove nodes while maintaining tree balance. Learn the algorithm steps, key node roles, and how different cases involving rotations and recoloring help preserve the tree's properties.
Deletion in Red-Black Tree #
Before we start discussing how deletion works in a Red-Black tree, let’s discuss the main difference between the Insertion and Deletion operations in Red-Black trees.
In insertion, we may violate the alternating parent-child color property, i.e., a red parent may have a red child. But in the deletion function, we may end up deleting a black node that could violate the property that “the same number of black nodes must exist from the root to the None node for every path.”
In insertion, we check the color of the sibling of the parent of the currentNode and based on the color we perform appropriate operations to balance the tree. But now in the deletion operation, we will check the color of the sibling node of the currentNode and based on its color, we will perform some actions to balance the tree again.