Red-Black Tree
A search tree kept within 2 log n height by one colour bit per node and a fixup after each insert.
Red-Black Tree: Ascending inserts, every case
8 nodes, height 4, after 4 rotations and 19 recolourings. The rules keep the longest root-to-leaf path at most twice the shortest, so the height is at most 2 log2(n + 1), about 6 here, and every operation stays O(log n).
Cost
- Search
- O(log n)
- Insert
- O(log n)
- Delete
- O(log n)
- Space
- O(n)
Fewer rotations than AVL on insert. Slightly taller trees.
Before this
Related
Leads to
Topics that need this one first.
Taught by the same lesson
Red-Black Tree covers these too, in the same run.