Red-Black Insert Fix-up
Red uncle: recolour and move up. Black uncle: one or two rotations plus a recolour, then stop.
Red-Black Tree: Ascending inserts, every case
z = 40 is red under a red parent p = 30. Grandparent g = 20, uncle u = 10. Case 1, red uncle: colour p and u black and g red. Every path through g still has the same black count, and the problem moves up to g.
Cost
- Best
- O(1)
- Average
- O(log n)
- Worst
- O(log n)
- Space
- O(1)
At most two rotations per insert.
Leads to
Topics that need this one first.
Taught by the same lesson
Red-Black Tree covers these too, in the same run.