This builds on red-black insertion. The rules are the same: the root is black, no red node has a red child, and every path down to an empty (NIL) spot passes through the same number of black nodes. Insertion risks a red-red clash. Deletion risks a path that is one black short, which is harder to fix.
Exactly as in a binary search tree: a leaf just goes, a node with one child is replaced by that child, and a node with two children is replaced by its in-order successor. In the two-child case, the successor also takes over the deleted node's color, so nothing changes at that spot. What really disappears is the successor's old spot.
| The spot that disappeared was… | What to do |
|---|---|
| Red | Nothing: red nodes don't count toward black heights. |
| Black, and its replacement is red | Color the replacement black. The count is restored. |
| Black, and its replacement is black or NIL | Paths through the replacement are one black short. Call it N and say it carries a double black. Fix it up (below). |
Look at N's family. NIL spots count as black and are drawn as small squares when they matter.
| Situation | What to do | Then |
|---|---|---|
| N is red, or N is the root | Color N black (at the root, just drop the extra black). | Done. |
| S is red | Rotate at P toward N, swap the colors of P and S. | N now has a black sibling: look again. |
| S black, C and D black | Color S red. P's whole subtree is now one black short. | P becomes N: the double black moves up. |
| S black, C red, D black | Rotate at S away from N, swap the colors of S and C. | Now D is red: the last case. |
| S black, D red | Rotate at P toward N. S takes P's color; P and D turn black. | Done: N's side gained a black. |
Only the "S black, C and D black" case moves the double black up, and it needs no rotation, so a deletion does at most three rotations in total. With these rules the tree stays balanced, and deletion costs O(log n), like insertion.