AVL trees: self-balancing search trees

Introduction

A binary search tree finds a key in O(height). Insert the keys 1, 2, 3, 4, 5, 6, 7 in that order and every new key goes to the right of the last: the "tree" is a linked list of height 7, and a search is O(n).

#include <stdio.h>
#include <stdlib.h>

struct node {
    int key;
    struct node *left, *right;
};

struct node *insert(struct node *n, int key) {   // a plain BST: no balancing
    if (!n) {
        n = calloc(1, sizeof(struct node));
        n->key = key;
        return n;
    }
    if (key < n->key) n->left = insert(n->left, key);
    else n->right = insert(n->right, key);
    return n;
}

int height(struct node *n) {
    if (!n) return 0;
    int l = height(n->left), r = height(n->right);
    return 1 + (l > r ? l : r);
}

int main(void) {
    struct node *root = NULL;
    for (int k = 1; k <= 7; k++) root = insert(root, k);   // sorted input
    printf("height: %d\n", height(root));
    return 0;
}

Sorted or nearly sorted input is common in real data (dates, IDs), so a search tree must protect itself. An AVL tree (Adelson-Velsky and Landis, 1962) does it with one rule:

At every node, the heights of the left and right subtrees differ by at most 1.

The difference height(left) − height(right) is the node's balance factor: −1, 0 or +1 is fine. The rule keeps the height below about 1.44 · log₂ n, so search, insert and delete are all O(log n). The same seven keys give a tree of height 3.

A binary search tree is only as fast as its height, and an unlucky input order can make it as slow as a list. A self-balancing tree notices when it starts to lean, and repairs itself with a few pointer changes.

How it works

Other balanced trees

• Red-black trees allow a little more imbalance (height up to 2 log₂ n) but need fewer rotations when keys are inserted and deleted often. C++ std::map and Java TreeMap use them.
• B-trees keep many keys per node, so one disk read brings in a whole node. Almost every database index is a B-tree or B+ tree (see the DBMS course).
• Treaps and skip lists balance themselves with random numbers instead of rules.

Syntax

struct node *rotate_right(struct node *y) {
    struct node *x = y->left;
    y->left = x->right;
    x->right = y;
    fix(y);
    fix(x);
    return x;
}

Example

After an insert, walk back up the path. Fix each node's height; if a balance factor becomes +2 or −2, a rotation repairs it. A rotation moves three pointers and keeps the search order (smaller keys on the left).

  right rotation at y            left rotation at x

        y              x            x                  y
       / \            / \          / \                / \
      x   C   --->   A   y        A   y     --->     x   C
     / \                / \          / \            / \
    A   B              B   C        B   C          A   B

There are four cases, named by where the new key went below the unbalanced node:

#include <stdio.h>
#include <stdlib.h>

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

int height(struct node *n) { return n ? n->height : 0; }
int bigger(int a, int b) { return a > b ? a : b; }
void fix(struct node *n) { n->height = 1 + bigger(height(n->left), height(n->right)); }
int balance(struct node *n) { return height(n->left) - height(n->right); }

struct node *rotate_right(struct node *y) {
    struct node *x = y->left;
    y->left = x->right;
    x->right = y;
    fix(y);                   // y is now below x: fix it first
    fix(x);
    return x;                 // x is the new top of this subtree
}

struct node *rotate_left(struct node *x) {
    struct node *y = x->right;
    x->right = y->left;
    y->left = x;
    fix(x);
    fix(y);
    return y;
}

struct node *insert(struct node *n, int key) {
    if (!n) {
        n = malloc(sizeof(struct node));
        n->key = key;
        n->height = 1;
        n->left = n->right = NULL;
        return n;
    }
    if (key < n->key) n->left = insert(n->left, key);
    else n->right = insert(n->right, key);
    fix(n);
    int b = balance(n);
    if (b > 1 && key < n->left->key) return rotate_right(n);     // left-left
    if (b < -1 && key > n->right->key) return rotate_left(n);    // right-right
    if (b > 1) {                                                 // left-right
        n->left = rotate_left(n->left);
        return rotate_right(n);
    }
    if (b < -1) {                                                // right-left
        n->right = rotate_right(n->right);
        return rotate_left(n);
    }
    return n;
}

void preorder(struct node *n) {
    if (!n) return;
    printf("%d ", n->key);
    preorder(n->left);
    preorder(n->right);
}

int main(void) {
    struct node *root = NULL;
    int keys[] = {10, 20, 30, 40, 50, 25};
    for (int i = 0; i < 6; i++) root = insert(root, keys[i]);
    preorder(root);
    printf("\nheight: %d\n", height(root));
    return 0;
}

Inserting 10, 20, 30 makes 10 lean right by 2: a left rotation lifts 20 to the top. After 40 and 50 the same happens lower down, and 25 then causes a right-left case at the root. The DSA Lab's AVL tool shows every case with your own keys.

Line by line

1. Each node stores its own height, and fix recomputes it from its children.
2. balance is the height of the left subtree minus the height of the right.
3. rotate_right lifts the left child above y, and rotate_left does the mirror image.
4. insert works like a plain search tree insert, then fixes the node's height.
5. If the balance is outside -1 to +1, the four if statements pick the rotation by comparing the new key with the child's key.
6. Each rotation returns the subtree's new top, and insert returns that to the parent.
7. main inserts six keys and prints them in preorder, with the height of the final tree.

Expected result

30 20 10 25 40 50 
height: 3

In the real world

Balanced trees sit behind sorted collections in language libraries and behind many in-memory database indexes. The rotation you see here is the same basic move used by red-black trees, which C++'s std::map commonly uses.

Common mistakes

• Forgetting to update heights after a rotation, or updating the new top before the old one (the old top is now its child).
• Not returning the new subtree root from insert, so the parent still points at the old one.
• Mixing up the cases: compare the new key with the child's key to tell left-left from left-right.

Best practices

• Fix the lower node's height before the upper node's.
• Return the new top of a subtree from every function that can change it.
• After each insert in testing, check that the inorder output is still sorted.

Summary

An AVL tree keeps every node's subtree heights within one of each other. After each insert it updates heights on the way up, and restores balance with one or two rotations, so operations stay O(log n).

Mark lesson complete