Balanced trees

Binary search trees are a fine idea, but they only work if they are balanced—if moving from a tree to its left or right subtree reduces the size by a constant fraction. Balanced binary trees add some extra mechanism to the basic binary search tree to ensure balance. Finding efficient ways to balance a tree has been studied for decades, and several good mechanisms are known. We’ll try to hit the high points of all of them.

Tree rotations

The problem is that as we insert new nodes, some paths through the tree may become very long. So we need to be able to shrink the long paths by moving nodes elsewhere in the tree.

But how do we do this? The idea is to notice that there may be many binary search trees that contain the same data, and that we can transform one into another by a local modification called a rotation:

    y            x
   / \   <==>   / \
  x   C        A   y
 / \              / \
A   B            B   C

Single rotation on x-y edge

If A < x < B < y < C, then both versions of this tree have the binary search tree property. By doing the rotation in one direction, we move A up and C down; in the other direction, we move A down and C up. So rotations can be used to transfer depth from the leftmost grandchild of a node to the rightmost and vice versa.

But what if it’s the middle grandchild B that’s the problem? A single rotation as above doesn’t move B up or down. To move B, we have to reposition it so that it’s on the end of something. We do this by splitting B into two subtrees B₁ and B₂, and doing two rotations that split the two subtrees while moving both up. For this we need to do two rotations:

    z              z                y
   / \   ===>     / \     ===>     / \
  x   C          y   C            x   z
 / \            / \              /|   |\
A   y          x  B2            A B1 B2 C
   / \        / \
  B1 B2      A  B1

Double rotation: rotate xy then zy

Rotations in principle let us rebalance a tree, but we still need to decide when to do them. If we try to keep the tree in perfect balance (all paths nearly the same length), we’ll spend so much time rotating that we won’t be able to do anything else. So we need a scheme that keeps a tree balanced enough that we get paths of length O(log n) while still doing O(log n) rotations per operations.