AVL trees

The AVL tree (Adelson-Velsky and Landis, 1962) was the first balanced search tree. It asks every node to be nearly balanced, and repairs the tree with at most one single or double rotation after each insert.

The AVL rule

The balance of a node is the height of its left subtree minus the height of its right subtree. An empty subtree has height −1, so a leaf has balance 0. A balance of +1 means the left side is one level taller; −1 means the right side is.

The rule holds at every node, not only the root. A tree whose root has two subtrees of equal height can still be badly unbalanced lower down. Practice BALT-P1 checks this rule for a whole tree in one pass.

Each node stores its own height, so a balance can be worked out in O(1) from its two children. After a change, only the heights of nodes on the changed path can be wrong, and they are fixed on the way back up.

Insert and the four cases

Insert the key as in a plain search tree, as a new leaf. That can only change the heights of the nodes on the path from the root to the new leaf. Walk back up that path, updating each height. Stop at the first node whose balance has become +2 or −2; call it z. Step through the figure: the first variant inserts 1 to 7 in order, and the second needs a double rotation.

The new key went into one of z’s subtrees, then into one of that child’s subtrees. That gives four cases, named by the two directions:

After the fix, the subtree that z used to be the top of has exactly the height it had before the insert. So no node above it changes height, and the walk up can stop. An insert therefore does at most one single or one double rotation, plus O(h) work to walk down and back up.

Why that height? In the left-left case, before the insert, z’s left subtree had height k + 1 and its right subtree height k. The insert raised the left side to k + 2. The rotation lifts the left child to the top with two subtrees of height k + 1, so the top has height k + 2: the same as before the insert. The other cases work the same way.

Why the height is O(log n)

Let N(h) be the smallest number of nodes an AVL tree of height h can have. The thinnest such tree has a root, one subtree of height h − 1 and, as the rule allows, the other of height h − 2. Both subtrees are as thin as possible too, so:

N(0) = 1,   N(1) = 2,   N(h) = 1 + N(h - 1) + N(h - 2)
N:  1, 2, 4, 7, 12, 20, 33, 54, 88, ...

Add 1 to each number and you get 2, 3, 5, 8, 13, 21, 34, 55, 89: the Fibonacci numbers, where each number is the sum of the two before it. Fibonacci numbers grow by a factor of about φ ≈ 1.618 (the golden ratio) at each step, so N(h) + 1 ≥ φ^h (h copies of φ multiplied together). Taking logarithms of both sides gives:

For a million keys, that is a height of at most 28, against 19 for a perfect tree and up to 999,999 for a plain search tree. Search, insert and delete are all O(log n) in the worst case.

The code

A recursive insert is the easiest to get right. Each call returns the new top of its subtree, so the parent’s link is fixed by the assignment in the caller. The recursion is as deep as the tree, which is at most about 28 for a million keys.

def h(node):
    return node.height if node is not None else -1

def update(node):  # height from the two children
    node.height = 1 + max(h(node.left), h(node.right))

def rotate_right(y):
    x = y.left
    y.left = x.right
    x.right = y
    update(y)  # y first: it is now below x
    update(x)
    return x

def rebalance(node):
    update(node)
    balance = h(node.left) - h(node.right)
    if balance > 1:  # left side too tall
        if h(node.left.left) < h(node.left.right):
            # inside: make it outside
            node.left = rotate_left(node.left)
        return rotate_right(node)
    if balance < -1:  # right side too tall (mirror)
        if h(node.right.right) < h(node.right.left):
            node.right = rotate_right(node.right)
        return rotate_left(node)
    return node

rotate_left is the mirror of rotate_right. Insert then goes down as in TREE-4, and on the way back calls rebalance on every node of the path: node.left = insert(node.left, key), then return rebalance(node). Calling rebalance on nodes that are fine just updates their height. Practice BALT-P3 asks you to write the whole insert.

Deleting

Delete as in a plain search tree (TREE-5), then walk back up from the node that was actually removed, calling rebalance at each node. One difference: after a delete, a rotation can make the subtree one level shorter than before, so the node above may now be out of balance too. A delete can need a rotation at every level of the path: O(log n) rotations, still O(log n) time.