Red-black tree
Every node is red or black. New nodes arrive red, and three fix-ups on the way back up keep the rules: rotate left if a red hangs to the right, rotate right if two reds are stacked, and flip colours if both children are red. This is the left-leaning variant, the simplest one to write.
empty tree
This is the left-leaning kind of red-black tree. New nodes start red. Two rules: a red node only ever hangs to the left, and never two reds in a row.
1function insert(h, value) {2 if (h === null) return { value, red: true, left: null, right: null };3 if (value < h.value) h.left = insert(h.left, value);4 else h.right = insert(h.right, value);5 if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);6 if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);7 if (isRed(h.left) && isRed(h.right)) flipColors(h);8 return h;9}1011function add(root, value) {12 root = insert(root, value);13 root.red = false;14 return root;15}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | log n | per insert: the height stays under 2 log n |
| average | log n | per insert, search or delete |
| worst | log n | even sorted input |
| space | n | one node per value, plus one colour bit each |
Where it breaks
- Less balanced than AVL, on purpose. A red-black tree can be up to twice as tall as a perfect tree, while AVL stays within about 1.44 times. In return it does less work per insert, which is why Java's TreeMap and C++'s std::map use red-black trees.
- Sorted input stays shallow. Pick Sorted 1 to 15: every insert lands on the right and triggers fix-ups, yet the tree ends 4 levels tall. A plain BST would be a 15-level chain.
- Deleting is much harder. Insert needs three rules; delete in a red-black tree has many more cases. Libraries hide it, but it is the reason few people write one from scratch.