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 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 of an actual tree with real values, if one step ends up unbalancing the tree, then we keep moving in a bottom-up manner and applying the next possible case until the tree gets balanced again.

Steps for Deletion #

Following are the steps involved to remove any value in a Red-Black Tree:

1. Search for a node with the given value to remove. We will call it currentNode
2. Remove currentNode using standard BST deletion operation that we studied earlier

We already know that for deletion in BST, we always end up deleting either a leaf node or a node with only one child.

• In the case of leaf node deletion, it is easy to just delete the node and link the parent of the node to be deleted with null
• In the case of a node with one child, deletion is relatively easy as we just link the parent of the node to be deleted with that one child

Let’s name some nodes relative to Node C, which is the node that we want to delete:

• Node C – node to be deleted (currentNode)
• Node P – parent node of currentNode
• Node S – sibling node (once we rotate tree, Node R will have a sibling node which we name as Node S)
• Node SC – child node of Node S
• Node R – node to be replaced with currentNode and linked with Node P (Node R is the single child of Node C)

Deletion Cases #

Now we will take a look at some of the deletion cases and see what steps should be performed in each of these cases to make the tree balanced again. Given below is the first case in which Node C or Node R is red. In this type of scenario, we make Node R black and link it to Node P.