Two more ways to stay balanced — and one that plays favourites

Red-black trees: looser rules, same guarantee

A red-black tree colors every node red or black and enforces five rules: the root is black; every leaf (treated as an imaginary NULL node) is black; a red node never has a red child; and — the rule that actually does the work — every path from a node down to any of its NULL leaves passes through the same number of black nodes.

That last rule is what bounds the height without demanding AVL's tight left-right balance — a red-black tree can be up to roughly twice as tall as a perfectly balanced one and still guarantee logarithmic search, which is looser than AVL but still far better than the chain shape from Lesson 5.

Why looser is sometimes better

AVL's tight balance costs more rotations on every insertion and deletion, in exchange for the shortest possible tree. A red-black tree accepts a slightly taller tree in exchange for needing far fewer rotations per write. The standard rule of thumb: choose AVL when you search far more often than you modify, and red-black when insertions and deletions are frequent — which is exactly why C++'s std::map and the Linux kernel's scheduler both use red-black trees.

Splay trees: the WhatsApp chat list of data structures

Open WhatsApp and message someone — that chat jumps straight to the top of your list, ahead of every other conversation, because you are likely to message them again soon. A splay tree applies the exact same idea to search: every single access, whether it finds the value or not, ends with a sequence of rotations called splaying that drags the accessed node all the way up to become the new root.

This means a splay tree has no fixed balance guarantee at any single moment — right after an access, the tree can look lopsided. What it guarantees instead is amortized speed: if you tend to access the same handful of values repeatedly, as most real programs do, those values stay near the root and stay fast, even though the tree itself is never explicitly kept balanced the way AVL or red-black trees are.

Four trees, one unit — a quick comparison

A plain BST is the simplest and can degrade to a chain. AVL keeps the tightest balance, favouring fast, predictable search over cheap writes. Red-black keeps a looser balance, favouring cheap writes over the shortest possible search. A splay tree keeps no fixed balance at all, favouring whatever you have been accessing recently over everything else. Choosing between them is choosing what your program actually does most: read, write, or repeat.