Red/Black Tree
Current sequence—
The tree is empty. Insert an integer to begin.
Mnemonics
Left-root-right; root & leaves black; no red-red; equal black paths
- Left-root-right
- Left child < root < right child (BST order).
- Root & leaves black
- The root is black, and NIL leaves count as black.
- No red-red
- A red node’s children must both be black.
- Equal black paths
- Every path from a node to its descendant NIL leaves has the same black height.
Insert by hand
Black uncle: rotate & recolor. Red uncle: recolor & move up.
Black uncle: rotate and recolor
Uncle is black (including NIL): rotate LL / LR / RL / RR, then color the parent black and the grandparent red.
Red uncle: recolor and move up
Uncle is red: color parent and uncle black, grandparent red, then continue checking from the grandparent.
Five red-black properties
- 01Every node is either red or black.
- 02The root is black.
- 03All NIL leaves are black.
- 04A red node’s children are black — no two reds in a row.
- 05Every path from a node to its descendant NIL leaves has the same black height.