Keeping a tree balanced

The rotation

Four pointer assignments, O(1), and the in-order sequence is identical afterwards — so the search property survives while the shape changes. Every balanced tree is built out of this one operation. What differs between them is only the rule for when to apply it.

      y                              x
     / \                            / \
    x   C      rotate right →      A   y
   / \                                / \
  A   B                              B   C

  in-order: A x B y C              in-order: A x B y C     ← unchanged

function rotateRight(y) {
  const x = y.left;
  y.left = x.right;      // B moves across
  x.right = y;
  return x;              // x is the new root of this subtree
}

AVL: strict, and fast to read

Every node stores its height, and after each insert or delete the tree rebalances any node whose subtrees differ by more than one. Four cases — left-left, right-right, left-right, right-left — the first two fixed by one rotation and the last two by two.

The result is a height of at most 1.44·log₂ n, which is the tightest of the practical schemes. Lookups are correspondingly fast; the price is more rotations on write, so AVL suits read-heavy work.

Red-black: looser, and cheaper to write

Those rules imply that the longest path is at most twice the shortest, so the height is at most 2·log₂ n — looser than AVL, and in exchange an insert needs at most two rotations and a delete at most three, however big the tree is.

That trade is why red-black trees are behind std::map, Java’s TreeMap, and the Linux kernel’s scheduler. It is not that they are better; it is that bounded rebalancing work is worth more than a slightly shorter tree.

• Every node is red or black; the root and the leaves are black.
• A red node has no red child.
• Every path from a node down to a leaf passes the same number of black nodes.

B-trees: the shape disks want

Every tree so far assumed that following a pointer is cheap. On disk it is not: reading one 4 KB page costs the same as reading one byte, so the structure should read a page at a time.

A B-tree puts hundreds of keys in each node, which makes the branching factor hundreds instead of two, which makes the height 3 or 4 instead of 30. A million rows is three page reads. That is why every relational database index, every filesystem and every key-value store on disk is a B-tree or a B⁺-tree.

The same principle applies in memory, one level down: a node that fits one cache line is read as fast as a single number, which is why modern in-memory trees are wide too.

[ 17 | 42 ]                          one node, many keys
   /     |     \
[…<17]  […17–42]  […>42]            hundreds of children per node

What to actually use

The honest advice for this lesson: know what rotations are and never write them. A balanced tree is one of the few structures where the standard implementation is so much better tested than yours that writing your own is a defect, not an achievement. What you do need is to recognise when order matters — because that is the decision no library makes for you.