Deletion in Red-Black (RB) Tree

Deletion in R-B Tree is a bit tricky than other binary trees. Here I present the delete operation with suitable examples to demonstrate all the cases. Follow https://twitter.com/SwatiRajwal for upcoming articles:)

Pre-requisites:

You should have some knowledge of all operations performed on a Binary search tree (BST) and insert operation in an R-B tree. You should be familiar with terms like sibling, parent, grandparent of a node.

A quick recap to R-B Tree:

1. A red-black tree is a binary search tree with one extra bit of storage per node for its color (red/black)
2. This tree is approximately balanced.
3. Every node is either red or black.
4. The root is black
5. Every leaf (NIL) is black
6. If a node is red, then both its children are black.
7. For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

Why need an R-B Tree?

You may wonder what is the need for such a complex data structure when various other tree data structures are already available (B-Tree, BST, AV). Well, it would be unfair to say that R-B trees are not useful. Just like any other data structure, R-B tress has its own set of pros and cons. An R-B tree is majorly used in systems where insertion and/or deletion is performed frequently. This tree guarantees the time complexity of O(log n) for search, deletion, and insertion operations.

NIL Node

Fig. 1: RB Tree with NIL Nodes

Fig. 2: RB Tree without NIL Nodes

Every leaf node has a unique invisible child (or children) called NIL node(s). They are always colored black.

Fig. 1 and fig. 2 are equivalent. It is not necessary to specify NIL nodes in the diagram. But they are important while performing the deletion. When you delete a node, it becomes a NIL node and is marked as a double black, DB, node (I’ll cover this shortly).

All in all, that’s all for NIL nodes.

Deletion cases

Always keep one thing in mind-

A red-black tree should still remain a red-black tree after an element (key) is deleted.

The below table is useful to identify the case and its corresponding set of actions to be performed. No need to remember it all. In this, DB stands for double black. Worry not. Below examples will explain what DB is.

Just skip this table and jump to the next section. Come back to this table as and when needed.

Table 1: Various cases while deleting a key from the red-black tree

Example 1: Delete 30 from the RB tree in fig. 3

Fig. 3: Initial RB Tree

You first have to search for 30, once found perform BST deletion (assuming you know it). For a node with value ‘30’, find either the maximum of the left subtree or a minimum of the right subtree and replace 30 with that value. This is BST deletion (in short).

Fig. 4: RB Tree after replacing 30 with min element from right subtree

The resulting RB tree will be like one in fig. 4. Element 30 is deleted and the value is successfully replaced by 38. But now the task is to delete duplicate element 38.

Go to the table above and you’ll observe case 1 is satisfied by this tree.

Fig. 5: After removing the red leaf node

Since node with element 38 is a red leaf node, remove it and the tree looks like the one in fig. 5.

Observe that if you perform correct actions, the tree will still hold all the properties of the RB tree.

Example 2: Delete 15 from RB tree in fig. 6

Fig. 6: Initial RB Tree

15 can be removed easily from the tree (BST deletion). In the case of RB trees, if a leaf node is deleted you replace it with a double black (DB) nil node (fig. 7). It is represented by a double circle.

Fig. 7: NIL node added in place of 15

The entire problem is now drilled down to get rid of this bad boy, DB, via some actions.

Go back to our rule book (table) and case 3 fits perfectly.

Fig. 8: NIL Node removed after applying actions

In short, remove DB and then swap the color of its sibling with its parent (fig. 8).

You’re getting pro already! See if you can solve the next examples.

Example 3: Delete ‘15’ from fig. 9(A).

Fig. 9: (A) Initial RB Tree, (B) NIL node added in place of 15

Delete node with value 15 and, as a rule, replace it with DB nil node as shown. Now, DB’s sibling is black and sibling’s both children are also black (don’t forget the hidden NIL nodes!), it satisfies all the conditions of case 3. Here,

Fig. 10: RB Tree after case 3 is applied

1. DB’s parent is 20
2. DB’s parent is black
3. DB’s sibling is 30

With these points in mind perform the actions and you get an RB tree as in fig. 10.

20 becomes DB and hence the problem is not resolved yet. Reapply case 3 (check yourself how conditions match).

Fig. 11: RB Tree after case 3 is applied

The resulting tree looks like the one in fig. 11.

The DB still exist (urgh!!!!). Recheck which case will be applicable.

Fig. 12: NIL Node removed after applying actions

Found it? It’s case 2, the simplest of all!

The root resolved DB and becomes a black node. And you’re done deleting 15 successfully.

Example 4: Delete ‘15’ from fig. 13

Fig. 13: (A) Initial RB Tree, (B) NIL node added in place of 15

First, Search 15 as per BST rules and then delete it. Second, replace deleted node with DB NIL node as shown in fig. 13 (B).

DB’s sibling is red. Clearly, case 4 is applicable.

Fig. 14: RB Tree after case 4 is applied

(a) Swap DB’s parent’s color with DB’s sibling’s color. I know this is confusing, but take it easy and keep following. The tree looks like fig. 14.

Fig. 15

(b) Perform rotation at parent node in direction of DB. The tree becomes like the one in fig. 15. DB is still there (what’s its problem!).

(c) Check which case can be applied in the current tree. And got it, case 3.

Fig. 16: NIL Node removed after applying actions

(d) Apply case 3 as explained and the RB tree is free from the DB node as shown in fig. 16.

I know it’s tiresome, but I swear if you practice these examples 2–3 times, you will have a good grasp of the concept of deletion in RB trees.

Example 5: Delete ‘1’ from fig. 17

Fig. 17: (A) Initial RB Tree, (B) NIL node added in place of 1

Perform the basic preliminary steps- delete the node with value 1 and replace it with DB NIL node as shown in fig. 17(B). Check for the cases which fit the current tree and it’s case 3(DB’s sibling is black).

Fig. 18: RB Tree after case 3 is applied

Apply case 3 as discussed above and you get the tree as shown in fig. 18.

Node 5 has now become a double black node. We need to get rid of it.

Search for cases that can be applied and case 5 seems to fit here (not case 3).

Fig. 19: (A) Tree after swapping colors of 30 & 25 (B) Tree after rotation

Case 5 is applied as follows-

(a) swap colors of nodes 30 and 25 (fig. 19(A))

(b) Rotate at sibling node in the direction opposite to the DB node. Hence, perform right rotation at node 30 and the tree becomes like fig. 19 (B).

The double black node still haunts the tree! Re-check the case that can be applied to this tree and we find that case 6 (don’t fall for case 3) seems to fit.

Fig. 20

Apply case 6 as follow-

(a) Swap colors of DB’s parent with DB’s sibling.

(b) Perform rotation at DB’s parent node in the direction of DB (fig, 20(B)).

Fig. 21: NIL Node removed after applying actions

(c) Change DB node to black node. Also, change the color of DB’s sibling’s far-red child to black and the final RB tree will look fig. 21.

And, voilà! The RB tree is free of element 1 as well as of any double node. Life is good now.

Conclusion

I have given examples and explained all the cases possible as one performs a delete operation on a red-black tree. Without a doubt, it appears exhausting but if you try these examples as many times as required, you’ll understand the concept easily.

Also, you can ask me a question on https://twitter.com/SwatiRajwal!

References

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein:
   Introduction to Algorithms, 3rd Edition. MIT Press 2009, ISBN 978–0–262–03384–8.
2. Jenny’s lectures CS/IT NET&JRF. (2019, November 10). Red Black Tree deletion | Data structure [Video]. YouTube. https://www.youtube.com/watch?v=w5cvkTXY0vQ