Red-Black Tree Deletion

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 ...