Why balance matters

A binary search tree finds, inserts and deletes a key by walking one path down from the root. So its speed depends on one number: its height. This station is about trees that keep their height small, whatever order the keys arrive in.

The height is the cost

Recall from TREE-4: search, insert, delete, smallest, largest and successor each walk one path down the tree. Each step down costs O(1), and a path has at most h + 1 nodes, where h is the height (the number of edges on the longest path from the root down). So every one of these jobs costs O(h).

How small can h be? Level 0 holds at most 1 node, level 1 at most 2, level 2 at most 4, and level d at most 2^d (d twos multiplied together). A tree of height h therefore holds at most 1 + 2 + 4 + … + 2^h = 2^h+1 − 1 nodes. Turned around: a tree with n nodes has height at least log₂(n + 1) − 1, rounded up. Here log₂ n is the number of times you can halve n before you reach 1. For a million keys the smallest possible height is 19.

So the best a binary search tree can do is O(log n) per job. The question is how to stay close to that best.

The worst case is common

Step through the figure. The first variant inserts the keys 1 to 7 in sorted order; the second builds a tree from the same keys by always taking the middle key first.

Sorted order gives the worst possible tree: a path. Each new key is bigger than all the others, so it goes right at every node. The height is n − 1, and inserting all n keys costs 0 + 1 + 2 + … + (n − 1) comparisons, which is about n²/2 (n times n, halved). For 100,000 keys that is 5 billion comparisons.

Sorted input is not rare. Order numbers, timestamps, roll numbers and dates usually arrive in increasing order. Nearly sorted input is almost as bad. Keys that arrive in a random order give a short tree on average (height about 4.3 ln n, TREE-4), but a program cannot choose the order of its input.

Perfect balance is too strict

The second variant shows how to build the shortest tree from a sorted list: take the middle key as the root, then build the left half and the right half the same way. Each key is placed once, so this costs O(n).

def build(keys, lo, hi):  # keys[lo..hi] is sorted
    if lo > hi:
        return None
    mid = (lo + hi) // 2
    node = TreeNode(keys[mid])
    node.left = build(keys, lo, mid - 1)
    node.right = build(keys, mid + 1, hi)
    return node

So why not keep the tree perfect after every insert? Because one insert can force a change everywhere. Call a tree complete when every level is full except the last, and the last fills from the left. Take the complete tree of 1 to 7 from the figure and insert 8. The complete tree of 1 to 8 has 5 at the root and 3 and 7 below it: every one of the old seven nodes now holds a different key. That is O(n) work for a single insert.

The way out is to ask for less. A tree is balanced if its height is at most a fixed number times log₂ n, for example 2 log₂ n. That small amount of slack is enough to repair the tree in O(log n) time after each change.

Three ways to stay short

The rest of this station shows the three main ideas.

A fourth idea, rebuilding only the part of the tree that has become too lopsided, gives scapegoat trees. It is less common, so this course leaves it out.