AlgoScope

Red-Black Delete Fix-up

Removing a black node creates a "double black" that is pushed up or resolved by sibling cases.

Tree algorithms, algorithm, expert
Delete 10: No children: unlink it.1020304050607080z
Delete 10: No children: unlink it.1020304050607080z

Red-Black Tree: Deleting a black node: the fixup cases

Decision, step 2 of 7

10 is a leaf: unlink it. The node leaving is black, so every path through it is now one black short and a fixup is needed.

How red-black tree works

Cost

Best
O(1)
Average
O(log n)
Worst
O(log n)
Space
O(1)

At most three rotations per delete.

Taught by the same lesson

Red-Black Tree covers these too, in the same run.