AlgoScope

Red-Black Rules

Root black, no red under red, equal black count on every path. Checked bottom-up by black height.

Tree algorithms, analysis, advanced
Root 50 is black.20304050607080check
Root 50 is black.20304050607080check

Red-Black Tree: Check the rules on a built tree

Decision, step 2 of 10

Rule 2: the root 50 is black.

How red-black tree works

Cost

Space
O(1)

Leads to

Topics that need this one first.

Taught by the same lesson

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