AlgoScope

Red-Black Tree

A search tree kept within 2 log n height by one colour bit per node and a fixup after each insert.

Data structures, data structure, advanced
Red-black tree with 8 nodes and height 4.1020304050607080
Red-black tree with 8 nodes and height 4.1020304050607080

Red-Black Tree: Ascending inserts, every case

Result, step 26 of 26

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

Leads to

Topics that need this one first.

Taught by the same lesson

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