This post will outline the procedure for deleting an element from a Red-Black Tree. I have a separate post for insertion. This post will not focus on why all of the different cases are needed and why they work, but I may be following up with a separate post to further explain.
To delete a node, first determine the node that will be removed, and its child (or a black empty node if it doesn’t have a child) using standard BST deletion. Then, you will need to balance the tree.
If the removed node or its child is red, will just need to set the child that is replacing it to be black to rebalance the tree.
Otherwise, let the child be the current node, and it is now double black (due to merging the two black nodes together). This must be fixed with the double black rules:
- Node is the root: change the node to just be black. Changing the root from double black to black will just reduce the number of black nodes to every leaf by 1.
- Sibling of node is red: rotate on the parent in the direction of the double black node. Then, color the sibling (which will now be the double black nodes grandparent) black, and the parent of node red. Then, you just need re-run the double black rules on the still double black node.
- Sibling has one red child Like insertion’s grandparent rotations, this is symmetric, based on the orientation of the sibling and its red child compared to the parent. Let RedC be the child of the sibling that is red. If both are, then it doesn’t matter which of the sibling’s children you choose.
- Sibling is left child of parent: Will ultimately do a right rotation on parent to shift it to the right side of the subtree.
- Sibling is right child of parent: Will ultimately do a left rotation on parent to shift it the left side of the tree.
Once the rotations are completed, change the color of the new subtree owner (the new parent for the parent of the double black node) to the color of the double black nodes parent. Then, change the color of both children of the subtree owner to black.
- Sibling and its children are black: ‘shift the black’ up from the sibling by changing the sibling to red.
If their parent is red set it to black.
Otherwise, will change the parent to be double black, and then recursively handle the double black case.