AVL trees and rotations

Why it exists

A binary search tree is fast only if it is shallow. Insert the keys 1, 2, 3, ... in order and it becomes a chain: height $n - 1$ and every operation takes $O(n)$. An AVL tree (Adelson-Velsky and Landis) never lets that happen. It is a binary search tree that checks itself after every insertion and deletion and repairs any imbalance with a few pointer changes called rotations. The result is a height of $O(\log n)$ in the worst case, so search, insert and delete are all $O(\log n)$ in the worst case. It is the first self-balancing tree and the standard answer to "how can a search tree guarantee logarithmic time?".

Prerequisites

You need the binary search tree: the ordering rule, insertion and deletion (including the case of a node with two children and its in-order successor), and the fact that the shape depends on the insertion order. The size bound uses a recurrence solved like those in recurrences.

Precise definitions

Height. The height of a node is the number of edges on the longest downward path to a leaf. The height of an empty tree is $-1$, of a single node $0$. (Some books say 1 for a single node and 0 for the empty tree; all heights then shift by one. A GATE question states its convention: read it.)

Balance factor of a node: $bf = h(\text{left}) - h(\text{right})$.

AVL tree. A binary search tree in which every node has $bf \in \{-1, 0, +1\}$: the heights of its two subtrees differ by at most 1. (This is a condition on every node, not only on the root.)

Rotation. A local change of three pointers that keeps the in-order sequence of the keys unchanged and changes the heights:

• Right rotation at $y$ (with left child $x$): $x$ becomes the root of the subtree, $y$ becomes its right child, and the old right subtree of $x$ becomes the left subtree of $y$.
• Left rotation at $x$ (with right child $y$): the mirror image.

The four cases. After an insertion (or deletion) let $z$ be the lowest node with $|bf| = 2$.

After an insertion the child's balance factor is never 0 in this situation; after a deletion it can be 0, and then a single rotation is correct (the cases LL and RR with the child at 0).

How it works

Insertion

Insert like in an ordinary search tree, then walk back up to the root, recompute heights and balance factors, and repair the first node that is out of balance.

Each row is a node (the table fills as the keys arrive). Inserting 30 makes 10 right-heavy by two: the case RR, a single left rotation, and 20 becomes the root. Inserting 50 does the same at 30. Inserting 25 puts a node in the left subtree of the right child of 20: the case RL, which one rotation cannot fix, so there is a double rotation (a right rotation at 40, which lifts 30, then a left rotation at 20). The result has the root 30, with 20 (children 10 and 25) on the left and 40 (right child 50) on the right. Watch the Left and Right columns change at every rotation.

Insertion needs at most one repair. After the repair the subtree has the height it had before the insertion, so no ancestor sees a change. The check over all insertion orders of up to 8 keys found one rebalancing step at most (a double rotation is one step with two rotations).

The four cases

In each case the middle key of the three becomes the root of the subtree, and the other two become its children; the pictures differ only in how the smaller subtrees are reattached. A double rotation is needed when the new node lies in the inner subtree (LR, RL) and a single one when it lies in the outer subtree (LL, RR).

Deletion

Delete like in an ordinary search tree (a node with two children is replaced by its in-order successor, which is then removed), then walk up from the place of the removal and repair every node that is out of balance. Unlike the insertion, the repair can shrink the subtree, so the parent may become unbalanced in turn:

This is the smallest AVL tree of height 4 (12 nodes). Removing key 11 leaves 12 left-heavy by two; the repair shortens that subtree; now 8 is out of balance by two, and a second rotation is needed. In the worst case a deletion repairs at every level up to the root, so it may need $O(\log n)$ rotations:

(The table is a measurement of the smallest trees, not a proof of the worst case, but it shows the pattern: about half the height.)

How tall can an AVL tree be?

Let $N(h)$ be the fewest nodes of an AVL tree of height $h$. The sparsest such tree has a root, a subtree of height $h - 1$ and a subtree of height $h - 2$ (any shorter and the condition fails; any smaller subtree would shorten the whole tree):

This gives 1, 2, 4, 7, 12, 20, 33, 54, ... for $h = 0, 1, 2, \dots$, which is the Fibonacci sequence minus one: $N(h) = F_{h+3} - 1$ (with $F_1 = F_2 = 1$). The most nodes of height $h$ is $2^{h+1} - 1$ (a perfect tree).

Read the table from the right: an AVL tree with $n$ nodes has height at most the largest $h$ with $N(h) \le n$. The exercise "what is the largest height of an AVL tree with 7 nodes?" is answered by the row for $N(3) = 7$: 3. Because $N(h)$ grows like $\varphi^{h}$ with $\varphi \approx 1.618$ (the golden ratio), $h < 1.44 \log_2 (n + 2)$ for every AVL tree, and $h \ge \lfloor \log_2 n \rfloor$ for every binary tree. So the height is $\Theta(\log n)$, between $\log_2 n$ and about $1.44 \log_2 n$.

Sorted input

The plain tree becomes a chain, the AVL tree has the smallest possible height for every size shown. Inserting $1, \dots, n$ in order for $n = 2^k - 1$ costs $n - k$ rotations, all single, and ends in a perfect tree. The program below does the insertions with the exact rotation rules of this page.

#include <stdio.h>
#include <stdlib.h>
 
struct node {
    int key, height;
    struct node *left, *right;
};
 
static int rotations = 0;
 
static int height(const struct node *n) { return n ? n->height : -1; }
static int max(int a, int b) { return a > b ? a : b; }
static void update(struct node *n) { n->height = 1 + max(height(n->left), height(n->right)); }
 
static struct node *rotate_right(struct node *y) {
    struct node *x = y->left;
    y->left = x->right;
    x->right = y;
    update(y);
    update(x);
    rotations++;
    return x;
}
 
static struct node *rotate_left(struct node *x) {
    struct node *y = x->right;
    x->right = y->left;
    y->left = x;
    update(x);
    update(y);
    rotations++;
    return y;
}
 
static struct node *rebalance(struct node *n) {
    update(n);
    int balance = height(n->left) - height(n->right);
    if (balance > 1) {
        if (height(n->left->left) < height(n->left->right)) n->left = rotate_left(n->left);   /* case LR */
        return rotate_right(n);
    }
    if (balance < -1) {
        if (height(n->right->right) < height(n->right->left)) n->right = rotate_right(n->right);   /* case RL */
        return rotate_left(n);
    }
    return n;
}
 
static struct node *insert(struct node *n, int key) {
    if (n == NULL) {
        n = calloc(1, sizeof *n);
        if (n == NULL) exit(1);
        n->key = key;
        return n;
    }
    if (key < n->key) n->left = insert(n->left, key);
    else if (key > n->key) n->right = insert(n->right, key);
    else return n;
    return rebalance(n);
}
 
static void show(const struct node *n) {
    if (n == NULL) { printf("."); return; }
    if (n->left == NULL && n->right == NULL) { printf("%d", n->key); return; }
    printf("(");
    show(n->left);
    printf(" %d ", n->key);
    show(n->right);
    printf(")");
}
 
static void release(struct node *n) {
    if (n == NULL) return;
    release(n->left);
    release(n->right);
    free(n);
}
 
int main(void) {
    int keys[] = {10, 20, 30, 40, 50, 25};
    struct node *root = NULL;
    for (int i = 0; i < 6; i++) {
        root = insert(root, keys[i]);
        printf("insert %d: ", keys[i]);
        show(root);
        printf("   rotations so far: %d\n", rotations);
    }
    release(root);
    for (int n = 7; n <= 1023; n = 2 * n + 1) {
        rotations = 0;
        root = NULL;
        for (int k = 1; k <= n; k++) root = insert(root, k);
        printf("keys 1..%d in order: height %d, %d rotations\n", n, root->height, rotations);
        release(root);
    }
    return 0;
}

insert 10: 10   rotations so far: 0
insert 20: (. 10 20)   rotations so far: 0
insert 30: (10 20 30)   rotations so far: 1
insert 40: (10 20 (. 30 40))   rotations so far: 1
insert 50: (10 20 (30 40 50))   rotations so far: 2
insert 25: ((10 20 25) 30 (. 40 50))   rotations so far: 4
keys 1..7 in order: height 2, 4 rotations
keys 1..15 in order: height 3, 11 rotations
keys 1..31 in order: height 4, 26 rotations
keys 1..63 in order: height 5, 57 rotations
keys 1..127 in order: height 6, 120 rotations
keys 1..255 in order: height 7, 247 rotations
keys 1..511 in order: height 8, 502 rotations
keys 1..1023 in order: height 9, 1013 rotations

The rotation counts of the table are the counts of this program, and the shapes are the ones of the node table. (A double rotation counts as two rotations here.)

Cost

Search, insertion and deletion each follow one path from the root and do a constant amount of work per node (a deletion may repair at every level), so each takes $\Theta(\log n)$ in the worst case. Building a tree by $n$ insertions takes $O(n \log n)$. Inserting $m$ keys into a tree that already has $n$ nodes costs $\Theta(m \log (n + m))$ in total in the worst case (every new node is a leaf, and every leaf of an AVL tree with $s$ nodes lies at a depth of at least about half its height, so each insertion walks $\Theta(\log s)$ nodes). Sorting by inserting into an AVL tree and reading it in order takes $\Theta(n \log n)$, a worst-case guarantee that a plain search tree does not give. The extra cost is one height (or balance factor) stored in every node and the code for the rotations.

Worked examples

Cheat box

Traps and GATE patterns

Connections

The AVL tree repairs the weakness of the binary search tree, the dependence of the height on the insertion order. The B-tree solves the same problem differently, by allowing many keys per node and splitting nodes, which suits disks. Unlike the binary heap, an AVL tree keeps all keys sorted, so it can answer range queries and find a successor in $O(\log n)$.

PYQs

What is the worst case time complexity of inserting
n2 elements into an AVL-tree with n elements
initially?

What is the maximum height of any AVL-tree with 7
nodes ? Assume that the height of a tree with a single
node is 0.

Self-check

Revision card

References