Bytebook Compiler

Trees

AVL Trees

Self-balancing BSTs: balance factors, the four rotation cases (LL, RR, LR, RL), and an insertion that stays O(log n) whatever order the keys arrive in.

5 min read1 runnable example4-question quiz

An AVL tree (named after Adelson-Velsky and Landis, 1962) is a BST that keeps itself balanced. After every insertion or deletion it checks each node's balance factor and fixes any imbalance with rotations.

Balance factor

balance factor = height(left subtree) − height(right subtree)

In an AVL tree, every node's balance factor must be −1, 0 or +1. If an insertion makes some node's balance factor +2 or −2, that node is rebalanced. This keeps the height at most about 1.44 log₂ n, so search, insert and delete are all O(log n) guaranteed.

The four imbalance cases

Let Z be the lowest unbalanced node on the path from the inserted key up to the root.

Case Inserted into Fix
LL left subtree of Z's left child one right rotation at Z
RR right subtree of Z's right child one left rotation at Z
LR right subtree of Z's left child left rotation at the child, then right rotation at Z
RL left subtree of Z's right child right rotation at the child, then left rotation at Z

LL case: right rotation

Inserting 30, 20, 10 makes 30 left-heavy (balance factor +2):

102030
Before: 30 has balance factor +2 (left-heavy).

Rotate right at 30: the left child 20 moves up to become the root, 30 moves down to become 20's right child, and 20's old right subtree (empty here) becomes 30's new left subtree.

103020
After one right rotation the tree is balanced.

RR case: left rotation

Inserting 10, 20, 30 is the mirror image: rotate left at 10 and 20 becomes the root.

LR case: double rotation

Inserting 30, 10, 20: the imbalance is at 30 (left-heavy), but the new key went into the right of the left child. A single right rotation would not fix it. First rotate left at 10 (turning it into the LL case), then rotate right at 30. The result is again 20 with children 10 and 30.

Insertion in C

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

typedef struct Node { int key, height; struct Node *left, *right; } Node;

int h(Node *n) { return n ? n->height : 0; }
int max(int a, int b) { return a > b ? a : b; }
void update(Node *n) { n->height = 1 + max(h(n->left), h(n->right)); }
int balance(Node *n) { return n ? h(n->left) - h(n->right) : 0; }

Node *rotateRight(Node *z) {
    Node *y = z->left, *t = y->right;
    y->right = z;
    z->left = t;
    update(z); update(y);
    return y;
}

Node *rotateLeft(Node *z) {
    Node *y = z->right, *t = y->left;
    y->left = z;
    z->right = t;
    update(z); update(y);
    return y;
}

Node *insert(Node *n, int key) {
    if (!n) { n = malloc(sizeof(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 if (key > n->key) n->right = insert(n->right, key);
    else return n;

    update(n);
    int b = balance(n);
    if (b > 1 && key < n->left->key)  { printf("  LL at %d\n", n->key); return rotateRight(n); }
    if (b < -1 && key > n->right->key) { printf("  RR at %d\n", n->key); return rotateLeft(n); }
    if (b > 1 && key > n->left->key)  { printf("  LR at %d\n", n->key); n->left = rotateLeft(n->left); return rotateRight(n); }
    if (b < -1 && key < n->right->key) { printf("  RL at %d\n", n->key); n->right = rotateRight(n->right); return rotateLeft(n); }
    return n;
}

void preorder(Node *r) { if (r) { printf("%d ", r->key); preorder(r->left); preorder(r->right); } }

int main(void) {
    int keys[] = {10, 20, 30, 40, 50, 25};
    Node *root = NULL;
    for (int i = 0; i < 6; i++) {
        printf("insert %d\n", keys[i]);
        root = insert(root, keys[i]);
    }
    printf("Preorder: ");
    preorder(root);
    printf("\nHeight: %d (a plain BST built from the same keys has height 5)\n", h(root));
    return 0;
}
Output
insert 10
insert 20
insert 30
  RR at 10
insert 40
insert 50
  RR at 30
insert 25
  RL at 20
Preorder: 30 20 10 25 40 50 
Height: 3 (a plain BST built from the same keys has height 5)
Try it Yourself

The final AVL tree for 10, 20, 30, 40, 50, 25:

102520504030
Sorted-ish input that would make a plain BST a chain stays balanced with height 3 (counting nodes).

Test yourself

4 questions · pick an answer to check it instantly

  1. 1

    What balance factors are allowed in an AVL tree?

  2. 2

    Insert 10, 20, 30 into an empty AVL tree. Which rotation happens?

  3. 3

    Inserting 30, 10, 20 creates which case?

  4. 4

    Why are AVL operations O(log n) in the worst case?

Esc
↑↓ move↵ open