DSA Series · Trees · Part 4

AVL Trees: Self-Balancing BSTs

March 2026 · 15 min read

Binary search trees are elegant, but they have a fatal flaw: if you insert elements in sorted order (like 1, 2, 3, 4, 5), the tree degenerates into a linked list. Every operation becomes O(n) instead of O(log n). The entire point of using a tree is lost.

AVL trees fix this. Named after Adelson-Velsky and Landis (1962), they were the first self-balancing BST ever invented. The idea: after every insert or delete, check if the tree became lopsided, and if so, perform a local restructuring (called a rotation) to restore balance.

The Degeneration Problem

A BST's performance depends entirely on its height. A balanced tree with n nodes has height ~log₂(n). But insert 1, 2, 3, 4, 5 into an empty BST:

Same 5 elements, but insertion order determines shape. The degenerate case is just a linked list wearing a tree costume.

bf=0 3 bf=0

The AVL Invariant

An AVL tree is a BST with one extra rule: at every node, the heights of the left and right subtrees can differ by at most 1. We capture this with the balance factor:

balance(node) = height(left) - height(right)
// Valid: -1, 0, or +1
// Invalid: anything else triggers a rotation

Left tree: every node has bf in {-1, 0, +1}. Right tree: root has bf = 2 (left subtree is 2 taller than right). This violates the AVL invariant.

Why This Guarantees O(log n)

It's not obvious that limiting the balance factor to ±1 keeps the height logarithmic. The proof relies on a beautiful connection to the Fibonacci sequence.

The "worst case" (tallest possible) AVL tree with the fewest nodes satisfies N(h) = N(h-1) + N(h-2) + 1. Since Fibonacci grows exponentially (roughly φ^h where φ ≈ 1.618), we get:

AVL height bound: h ≤ 1.44 · log₂(n). An AVL tree is never more than 44% taller than a perfectly balanced tree. For n = 1,000,000, that's at most height 29 vs the ideal 20.

How Rotations Fix Imbalances

When an insert or delete pushes a node's balance factor to ±2, we restructure that local neighborhood of 2-3 nodes. This restructuring is called a rotation. It changes the shape (which node is the parent vs child) without changing the in-order sequence.

There are four cases depending on which path is too tall:

Case	Imbalance Path	Fix
LL	Left child, left grandchild too tall	Single right rotation
RR	Right child, right grandchild too tall	Single left rotation
LR	Left child, right grandchild (zig-zag)	Double: left then right rotation
RL	Right child, left grandchild (zig-zag)	Double: right then left rotation

Each rotation is O(1): just a few pointer swaps and height updates. The walk to find the imbalance is O(log n). So insert and delete are both O(log n) total.

The AVL Node

An AVL node is a BST node with one extra field: the height of its subtree.

struct AVLNode {
    int key;
    AVLNode* left;
    AVLNode* right;
    int height;   // height of the subtree rooted here

    AVLNode(int k) : key(k), left(nullptr), right(nullptr), height(1) {}
};

int height(AVLNode* n) { return n ? n->height : 0; }
int balance(AVLNode* n) { return n ? height(n->left) - height(n->right) : 0; }

Some implementations store the balance factor directly instead of the height. Either works; storing height makes the update logic slightly simpler.

Complexity Summary

Operation	Plain BST (worst)	AVL Tree
Search	O(n)	O(log n)
Insert	O(n)	O(log n)
Delete	O(n)	O(log n)
Min / Max	O(n)	O(log n)
Space	O(n)	O(n) + 1 int per node

The guarantee: AVL trees give you O(log n) worst-case for every operation. No input ordering can degenerate the tree. The balance invariant prevents it by construction.

What's Next

Now that we understand what AVL trees guarantee and why, the next post dives deep into the four rotation cases, with visual walkthroughs showing exactly how nodes move, which subtrees transfer, and why the in-order sequence is preserved.