AlgoScope

Red-Black Insert Fix-up

Red uncle: recolour and move up. Black uncle: one or two rotations plus a recolour, then stop.

Tree algorithms, algorithm, advanced
Case 1 at 40.10203040zupg
Case 1 at 40.10203040zupg

Red-Black Tree: Ascending inserts, every case

Decision, step 9 of 26

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.