AVL Trees: Self-Balancing BSTs

March 2026 · 7 min read

The AVL Invariant

An AVL tree maintains the invariant: for every node, the heights of the left and right subtrees differ by at most 1. This guarantees O(log n) height.

Balance Factor

balance(node) = height(node.left) - height(node.right)
// Must be -1, 0, or +1 for a valid AVL tree

Rotations

When an insertion or deletion causes a balance factor of +2 or -2, we fix it with rotations. There are four cases:

C++ Implementation

TreeNode* rotateLeft(TreeNode* x) {
    TreeNode* y = x->right;
    x->right = y->left;
    y->left = x;
    x->height = 1 + std::max(height(x->left), height(x->right));
    y->height = 1 + std::max(height(y->left), height(y->right));
    return y;
}

TreeNode* rotateRight(TreeNode* y) {
    TreeNode* x = y->left;
    y->left = x->right;
    x->right = y;
    y->height = 1 + std::max(height(y->left), height(y->right));
    x->height = 1 + std::max(height(x->left), height(x->right));
    return x;
}

TreeNode* avlInsert(TreeNode* node, int val) {
    if (!node) return new TreeNode(val);
    if (val < node->val) node->left = avlInsert(node->left, val);
    else if (val > node->val) node->right = avlInsert(node->right, val);
    else return node;

    node->height = 1 + std::max(height(node->left), height(node->right));
    int bf = balance(node);

    if (bf > 1 && val < node->left->val) return rotateRight(node);
    if (bf < -1 && val > node->right->val) return rotateLeft(node);
    if (bf > 1 && val > node->left->val) {
        node->left = rotateLeft(node->left);
        return rotateRight(node);
    }
    if (bf < -1 && val < node->right->val) {
        node->right = rotateRight(node->right);
        return rotateLeft(node);
    }
    return node;
}

Summary

• AVL trees guarantee O(log n) height by maintaining balance factors in {-1, 0, +1}.
• Four rotation cases: LL (right rotate), RR (left rotate), LR (left then right), RL (right then left).
• Rotations are O(1); insert and delete remain O(log n).