Keeping the Tree Balanced

The last chapter ended with a problem. A binary search tree follows one rule: smaller values go left, larger values go right. That rule keeps the values in order, but it does nothing to control the tree’s shape. Insert 50, 30, 70, 20, 40, 60, 80 and you get a short, perfect tree. Insert the same values in sorted order, 20, 30, 40, 50, 60, 70, 80, and each new value is larger than everything before it, so the tree degenerates into a single chain, and search slows from $O(\log n)$ to $O(n)$.

A perfect tree is the ideal, but we rarely need it. What matters is that the tree stays roughly even. At every node the left and right sides hold about the same number of values, so no path runs much longer than the others. A tree shaped like that is called balanced, and a balanced tree of $n$ nodes keeps its height close to $\log n$. The degenerate tree is the opposite: everything is on one side.

Random or mixed orders usually give a tree that is roughly balanced. Sorted and reverse-sorted orders give the worst case. That is a problem, because sorted input is common. Data often arrives already ordered by time, ID, score, or name.

What we want is a search tree that keeps itself balanced as values are inserted and removed, so the height stays $O(\log n)$ no matter what order the values arrive in. That kind of structure is a self-balancing search tree. The AVL tree, the subject of this chapter, is one.

“Roughly even” is something we can check visually on small or medium trees. We need to turn this into a quantifiable measure so the program can check it automatically. This is where the balance factor comes in.