RB Tree Deletion

Perform BST deletion and perform the following to ensure all properties of RB tree are still satisfied

Understanding Double Black node

In Red-Black Tree (RB tree) deletion, “double black” is a situation that can occur during the process of rebalancing the tree after removing a node. A double black node is a special condition that arises when a black node is deleted from the RB tree, potentially violating the properties of the RB tree. To maintain the RB tree properties, the tree must be adjusted to eliminate the double black node and ensure that all RB tree properties are preserved.

The process of handling a double black node typically involves several cases and rotations, and it depends on the sibling of the double black node and the color of the sibling. The possible cases include:

1. Sibling is red: In this case, you can perform rotations and color changes to turn the sibling black while moving the double black up to the parent.
2. Sibling is black, and both of its children are black: In this case, you can simply change the sibling to red and move the double black up to the parent. This operation may cause a new double black problem at the parent node.
3. Sibling is black, and one of its children is red: This case involves rotations and color changes to balance the tree and resolve the double black issue.

The exact steps and rotations for handling a double black node in an RB tree may vary depending on the specific implementation or the book/reference you are using. The key idea is to maintain the properties of the RB tree, which include ensuring that there are no adjacent red nodes, and the black height of the tree remains balanced. This rebalancing process continues recursively up the tree until the double black node is eliminated, or the root of the tree is reached.

Here if the deleted node is black, then it disturbs the black height property of RB tree, in this case we delete the node and create a double black node (DB), perform the following steps to remove double black node from the tree

Case 1-If node to be deleted is RED => just delete it

Case 2– If root node is DB, => remove DB

• Case 3– If DB’s sibling is black and both of its children are BLACK
• ===>Remove DB
• ===> Add extra black to its parent
• =====> if parent is RED, then make it BLACK
• =====> if parent is BLACK, then make it double BLACK
•  ====> Make sibling RED
• ====> If still DB exists, apply other cases.

• Case 4 – If DB sibling is RED
• ===> swap colors of  PARENT and its SIBLING
• ===> rotate PARENT in DB direction
• ===> reapply cases

• Case 5 – DB’s sibling is BLACK, check sibling child’s who is far from DB is BLACK but near child to DB is RED
• ===> Swap color of DB’s sibling & siblings child who is near to DB
• ===> Rotate sibling in opposite direction to DB
• ===> Apply case 6

• Case 6 – DB’s sibling is BLACK and far child is RED
• ===> Swap color of PARENT and SIBLING
• ===> Rotate PARENT in DB’s direction
• ===> Remove DB
• ===> Change color of RED child to BLACK

The goal of handling a double black node is to ensure that the RB tree remains balanced and follows the RB tree properties, which include having a black height that is the same for all paths from the root to the leaves.