Red-Black Tree Deletion Overview
What you'll learn: You'll understand why deletion in Red-Black Trees is complex and what "double-black" means.
Why Deletion Gets Complicated
You've learned how to insert nodes into a Red-Black Tree while maintaining balance. Deletion is trickier because removing a node can violate multiple Red-Black properties at once—especially the critical rule that every path from root to leaf must contain the same number of black nodes.
When you delete a black node, you create a "deficit" in black height along certain paths. The tree must somehow compensate for this missing blackness to restore balance.
The Double-Black Concept
Here's where Red-Black deletion gets unique: we introduce the idea of a double-black node. This is a temporary marking—not a real color—that tracks where we've lost a black node.
Think of it like this: imagine each black node carries one "black token." When you remove a black node, that token doesn't disappear—it gets pushed onto the node that takes its place (or onto the NIL node if there's nothing there). That node now carries two black tokens, making it "double-black."
A double-black node signals: "This position is missing one unit of blackness compared to what the tree needs." Your job during deletion is to redistribute or eliminate this extra blackness through rotations and recoloring, similar to how you handled insertion violations—but with more cases to consider.
The deletion process will identify which case applies based on the double-black node's sibling and that sibling's children, then fix the violation accordingly.
Key Takeaway: Red-Black Tree deletion introduces the temporary concept of double-black nodes to track black-height violations, requiring case-by-case fixes to restore all Red-Black properties.