Red-Black Delete Fix-up
Removing a black node creates a "double black" that is pushed up or resolved by sibling cases.
Red-Black Tree: Deleting a black node: the fixup cases
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.
Cost
- Best
- O(1)
- Average
- O(log n)
- Worst
- O(log n)
- Space
- O(1)
At most three rotations per delete.
Before this
Taught by the same lesson
Red-Black Tree covers these too, in the same run.