AVL trees and rotations

Keys that arrive in order turn a plain search tree into a chain. Watch a tree that turns itself back into shape.

⋯35static struct avl *rotate_left(struct avl *x)36{37    struct avl *y = x->right;38    x->right = y->left;39    y->left = x;40    update(x);41    update(y);42    rotations++;43    return y;44}⋯46static struct avl *rebalance(struct avl *t)47{48    update(t);49    int bf = h(t->left) - h(t->right);50    if (bf > 1) {51        if (h(t->left->left) < h(t->left->right))52            t->left = rotate_left(t->left);53        return rotate_right(t);54    }55    if (bf < -1) {56        if (h(t->right->right) < h(t->right->left))57            t->right = rotate_right(t->right);58        return rotate_left(t);59    }60    return t;61}⋯102    struct avl *root = NULL;103    for (int k = 1; k <= 15; k++)104        root = avl_insert(root, k);105    preorder(root);

A lean of two, then a turn

In Binary search trees, the keys 20 30 40 50 60 70 80 inserted in sorted order made a chain, and every search walked all of it. An AVL tree (named after Adelson-Velsky and Landis, who described it in 1962) is a search tree that refuses to become a chain. Each node stores its height. After every insertion, on the way back up, it checks each node on the path: if the node’s two subtrees differ in height by two, it rotates there.

Follow the clip. Insert 1, then 2: 2 hangs to the right of 1, which is allowed. Insert 3 and node 1 has nothing on its left (height −1) and a subtree of height 1 on its right. They differ by two, so the tree rotates left at 1: 2 is lifted to the top, 1 becomes its left child, and 3 stays as its right child. The tree is 2 over 1 and 3, height 1 instead of 2.

Each further key goes in at the far right, and each time a node leans right by two the same rotation fixes it. Some rotations happen low down, some at the root: inserting 12 rotates at 4, the root, and lifts 8 above it. After 15 keys the tree is perfect, height 3, after 11 rotations. Without rotations, the same keys would make a chain of height 14.

The code and its cost

Heights in the nodes

The full program, avl.c, keeps each node’s height in the node:

struct avl {
    int key;
    int height;
    struct avl *left, *right;
};

static int h(const struct avl *t)
{
    return t == NULL ? -1 : t->height;
}

static void update(struct avl *t)
{
    int hl = h(t->left);
    int hr = h(t->right);
    t->height = 1 + (hl > hr ? hl : hr);
}

Height counts edges on the longest path down, as in Binary trees: a leaf has height 0, and h gives an empty subtree −1, so that update works for every node: one more than the taller child.

The balance factor of a node is the height of its left subtree minus the height of its right: h(t->left) - h(t->right). An AVL tree keeps it at −1, 0 or 1 at every node. Just after an insertion, a node on the path can reach 2 or −2, and that is where a rotation goes.

A rotation

static struct avl *rotate_left(struct avl *x)
{
    struct avl *y = x->right;
    x->right = y->left;
    y->left = x;
    update(x);
    update(y);
    rotations++;
    return y;
}

rotate_left lifts x’s right child y above it. Three pointers change: x->right takes y’s old left subtree, y->left becomes x, and the pointer that used to lead to x (its parent’s, or the root) must now lead to y. The function can’t reach that last pointer, so it returns y and the caller stores it, as bst_insert did in Binary search trees.

The order survives. Before, x was smaller than y and everything in y’s left subtree was between them. After, x is y’s left child, so it is still smaller, and that middle subtree hangs on x’s right, so it is still between them. Read the keys from left to right before and after: they are the same. Then update fixes the two heights that changed, x’s first, because it is now below y.

rotate_right is the mirror image: it lifts the left child.

The four cases

static struct avl *rebalance(struct avl *t)
{
    update(t);
    int bf = h(t->left) - h(t->right);
    if (bf > 1) {
        if (h(t->left->left) < h(t->left->right))
            t->left = rotate_left(t->left);
        return rotate_right(t);
    }
    if (bf < -1) {
        if (h(t->right->right) < h(t->right->left))
            t->right = rotate_right(t->right);
        return rotate_left(t);
    }
    return t;
}

A node that leans by two leans either through the outside of its heavy child or through the inside:

Keys arriving in increasing order always make the right-right case, which is why the clip shows only left rotations. A single rotation can’t fix an inside lean: it would only move the lean to the other side. The first rotation turns it into an outside lean, and the second fixes that.

Inserting

struct avl *avl_insert(struct avl *t, int key)
{
    if (t == NULL) {
        struct avl *n = malloc(sizeof *n);
        if (n == NULL)
            exit(1);
        n->key = key;
        n->height = 0;
        n->left = NULL;
        n->right = NULL;
        return n;
    }
    if (key < t->key)
        t->left = avl_insert(t->left, key);
    else
        t->right = avl_insert(t->right, key);
    return rebalance(t);
}

The way down is the search tree’s insertion, written recursively. On the way back up each call runs rebalance on its own node, and the call above stores whatever comes back, the same node or the one a rotation lifted. After an insertion, at most one rebalance actually rotates (a single or a double rotation), because the rotated subtree gets back the height it had before the key arrived, so nothing above it changes.

What it costs

The rotations are cheap: a few pointers and two heights each. What they buy is the height. Let N(h) be the fewest nodes an AVL tree of height h can have. Such a tree has one subtree of height h − 1 and, at the least, one of height h − 2, so

This grows like the Fibonacci numbers, by a factor of about 1.618 per level, and turning it round gives the bound: an AVL tree with n nodes has height below about 1.44 log₂ n. So a search, an insertion or a removal follows one path of about log₂ n steps, never n.

An AVL tree is not perfectly balanced. Sibling subtrees may differ by one at every node, so it can be up to about 44% taller than the shortest tree for its keys. That is the price of fixing it with a few pointer changes instead of rebuilding.

Removing

Removal starts as in Deleting from a binary search tree, then runs rebalance at every node on the way back up. Unlike insertion, a removal can need a rotation at every level up to the root, because a rotation after a removal can leave its subtree one shorter, and the node above may then lean by two in turn. That is still one single or double rotation per level, so the cost stays about log₂ n.

Running it yourself

avl.c inserts 1 to 15, prints the tree in preorder, then the root’s height and the number of rotations (the static counter rotations):

gcc -std=c11 -Wall -Wextra -pedantic avl.c -o avl
./avl

It prints 8 4 2 1 3 6 5 7 12 10 9 11 14 13 15 and height 3, 11 rotations.

Worked example

A double rotation. Insert 30, 10, 20 (the file avl-double.c: the functions of avl.c unchanged, and a main inserting these three keys). After 20, node 30 has a left subtree of height 1 and an empty right: bf 2, leaning left. Its left child 10 leans right (nothing on its left, 20 on its right). That is the left-right case: rotate 10 left, which lifts 20 above 10, then rotate 30 right, which lifts 20 above 30. The root is 20, with 10 and 30 under it. The program prints 20 10 30 and height 1, 2 rotations.

The fewest nodes for each height. From the recurrence: N(0) = 1, N(1) = 2, N(2) = 4, N(3) = 7, N(4) = 12, N(5) = 20. An AVL tree of height 5 needs at least 20 nodes; a chain of height 5 needs only 6.

A million keys. 1.44 × log₂ 1,000,000 ≈ 1.44 × 19.9 ≈ 28.7. Counting exactly with the recurrence, N(27) = 832,039 and N(28) = 1,346,268, so a million-node AVL tree has height at most 27. A perfect tree needs height 19 (2²⁰ − 1 = 1,048,575 nodes fill height 19). Either way a search visits a few dozen nodes at most, against up to a million for a chain.

Two checks. How many rotations does inserting 1 to 7 in order take? (4: on inserting 3, 5, 6 and 7. That is 7 − 3, as the clip’s 11 was 15 − 4: the number of keys minus the number of levels.) Does a rotation change the inorder list? (No: it moves pointers, and the middle subtree keeps its place between the two nodes.)

Where it’s used

In-memory indexes. When lookups far outnumber updates, an AVL tree’s tighter height makes each search a little shorter than in looser balanced trees.

Ordered sets. Some libraries implement ordered sets and maps as AVL trees; others use red–black trees, which allow a little more lean in exchange for fewer rotations.

The idea of a rotation. Rotations are how most balanced binary trees repair themselves; red–black trees use them too. B-trees take the other route: nodes with many keys that split and merge.

Reference card

Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.