Red-Black Tree Deletion

Deletion in red-black tree

Before 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, you may violate the alternating parent-child colors property, i.e., a red parent may have a red child. But in the deletion function, you may end up deleting a black node that could violate the property: “the same number of black nodes must exist from the root to the None node for every path.”

In insertion, check the color of the sibling of the parent of the currentNode. Based on the color, perform appropriate operations to balance the tree. But, in the deletion operation, you will check the color of the sibling node of the currentNode. And based on its color, you will perform some actions to balance the tree again.

Algorithm for deletion

Here is a high-level description of the algorithm to remove the value in a red-black tree:

1. Search for a node with the given value to remove. Call it

...