Red-Black Tree Deletion
This lesson will cover the deletion operation in Red-Black Trees, discussing all four of the deletion cases.
We'll cover the following...
Deletion in Red-Black Tree #
Before we start discussing how deletion works in a Red-Black Tree, let’s see the main difference between insertion and deletion operations in Red-Black Trees.
In insertion, we may violate the property of a red parent having a red child. At the same time, in a deletion operation, we may end up deleting a black node which could violate the property of, “the same number of black nodes from root to the null for every path”.
In insertion, we check the color of the uncle node (uncle to currentNode), and based on the color we perform appropriate operations to balance the tree. In the deletion operation, we will check the color of the sibling node (sibling to currentNode), and based on its color we will perform some actions to balance the tree again.
Disclaimer: The illustrations given in this lesson are providing the visual representation of one case at a time. Therefore, you may notice that the tree gets unbalanced at the end of some of the illustrations. These trees have dummy values. However, in the case ...