AVL Tree

Trees O(log n) O(n)

A self-balancing BST: after each insert it checks balance factors and rotates so the height stays O(log n).

Insert

1/35

Insert 10 as a new leaf.

InvariantEvery node's subtree heights differ by at most 1, which keeps the height O(log n) and the search path short.

currentcompareinsertremoverotate

avl.c

int height(Node *n) { return n ? n->height : 0; }
int bf(Node *n) {
    return n ? height(n->left) - height(n->right) : 0;
}
 
Node *rotateRight(Node *y) {
    Node *x = y->left;
    y->left = x->right;
    x->right = y;
    fixHeight(y); fixHeight(x);
    return x;
}
 
Node *rotateLeft(Node *x) {
    Node *y = x->right;
    x->right = y->left;
    y->left = x;
    fixHeight(x); fixHeight(y);
    return y;
}
 
Node *insert(Node *n, int key) {
    if (!n) return newNode(key);
    if (key < n->key) n->left = insert(n->left, key);
    else n->right = insert(n->right, key);
    fixHeight(n);
    int b = bf(n);
    if (b > 1 && key < n->left->key)
        return rotateRight(n);
    if (b < -1 && key > n->right->key)
        return rotateLeft(n);
    if (b > 1 && key > n->left->key) {
        n->left = rotateLeft(n->left);
        return rotateRight(n);
    }
    if (b < -1 && key < n->right->key) {
        n->right = rotateRight(n->right);
        return rotateLeft(n);
    }
    return n;
}

How AVL Tree works

A BST that measures each node's balance factor after insertions and repairs any ±2 tilt with one or two rotations. Height stays within 1.44·log n, so walks stay logarithmic.

When to use it

Read-heavy ordered maps where strict O(log n) lookups matter more than cheap writes.