A plain BST is only fast on average. Insert 1, 2, 3, 4, 5 in order and you get a tree shaped like a linked list: search, insert, and delete all degrade to O(n).

An AVL tree is the first historical answer to it. Invented in 1962 by Adelson-Velsky and Landis, it was the first self-balancing binary search tree. The idea is simple: after every insertion or deletion, check whether any node has become "too lopsided" and fix it with a local rotation. The shape of the tree stays close to a perfectly balanced one, and every operation stays at O(log n).

In this chapter, we'll cover:

An AVL tree is a BST with one extra invariant:

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

That difference, height(left) - height(right), is called the node's balance factor. An AVL tree allows only three values: -1, 0, +1. Anything outside that range is a violation that must be fixed.

The height of a node is the number of edges on the longest path from that node down to a leaf. By convention the height of an empty subtree is -1, so a leaf has height 0.

Look at the difference between a plain BST and an AVL tree after inserting 1, 2, 3, 4, 5:

Plain BST:

Height is 4. Search for 5 walks every node.

AVL tree (same keys, same order):

Height is 2. Search for 5 walks 3 nodes. The AVL tree did extra work during the inserts (it performed rotations as the tree leaned), but every future query is fast.

Every node carries enough information to detect imbalance locally. To compute its own balance factor, a node only needs to look at the heights stored in its two children. So whenever a subtree's height changes, the parent can check itself in O(1) and decide whether action is needed.

The two operations that change subtree heights are insert and delete. Both follow the same pattern:

The fix is always one of four cases, picked by looking at where the imbalance came from.

When a node N ends up with balance factor +2 (left-heavy) or -2 (right-heavy), the trouble is in one of the four directions: Left-Left, Left-Right, Right-Right, or Right-Left. Each has a fixed rotation pattern.

The naming reads off the path from the offending ancestor: "the imbalance came from the Left child's Left subtree" gives Left-Left.

Case 1: Left-Left (Right Rotation)

N is left-heavy, and its left child L is also left-heavy (or balanced). The fix is a single right rotation around N.

Before rotation:

After right rotation around N:

L becomes the new root of the subtree. The middle subtree (formerly L's right) becomes N's left. The BST ordering is preserved: everything in LL is still less than L, everything between L and N is in the middle, and everything greater than N is on the right.

Case 2: Right-Right (Left Rotation)

The mirror image of Case 1. N is right-heavy, and its right child is also right-heavy. The fix is a single left rotation around N. R becomes the new subtree root, N becomes R's left child, and R's old left subtree slides over to be N's new right child.

Case 3: Left-Right (Left rotation on child, then Right rotation on N)

N is left-heavy, but its left child L is right-heavy. A single right rotation would not balance the tree because the heavy subtree is in the wrong corner. The fix is two rotations:

Before:

After the double rotation, LR ends up at the top, with L and N as its children, and the four subtrees distributed left-to-right in BST order.

Case 4: Right-Left (Right rotation on child, then Left rotation on N)

The mirror image of Case 3. Rotate right around the right child first, then rotate left around N.

Choosing the Right Case

Once a node's balance factor reaches ±2, the case is determined by the sign of the child's balance factor:

The "or 0" rows happen only during deletion, never during insertion. After an insert, the child causing the imbalance can never be perfectly balanced.

AVL insertion is exactly the same as BST insertion until the new node is in place. Then, as recursion unwinds, each ancestor:

A single insertion can change heights along the path from the new node to the root. But there is a useful property: one rotation always suffices for insert. The first time you fix an imbalance on the way up, the subtree's overall height returns to what it was before the insert, so no ancestor's balance factor changes after that point.

Walkthrough: Insert 10, 20, 30

Start empty. Insert 10, then 20. The tree is still balanced:

Now insert 30. After the BST insert:

Recursion unwinds:

The child 20 has balance factor -1, so this is Right-Right. One left rotation around 10:

Balanced again. Future inserts of 25, 5, 15 will trigger a mix of single and double rotations following the same rule.

Deletion follows the BST deletion algorithm (replace with successor, recurse), then rebalances ancestors on the way up just like insert. Two differences matter:

Each rotation is still O(1), and the path is O(log n), so delete remains O(log n) overall.

The AVL invariant guarantees a tight height bound. Let N(h) be the minimum number of nodes in any AVL tree of height h. The most lopsided AVL tree of height h has one subtree of height h - 1 and one of height h - 2 (any larger gap would break the invariant). So:

N(h) = 1 + N(h - 1) + N(h - 2)

with N(0) = 1 and N(1) = 2. This is the Fibonacci recurrence plus 1. Solving it gives:

N(h) ≈ φ^h / √5, where φ = (1 + √5) / 2 ≈ 1.618.

Inverting, h ≤ log_φ(n) ≈ 1.44 · log_2(n). The height is at most about 44% taller than a perfectly balanced binary tree. Every operation that walks one root-to-leaf path costs O(log n).

The class stores height on each node so that balance-factor lookups are O(1). Insert and delete both return the new root of the subtree, so rotations and rebalancing can be expressed as pure substitutions rather than pointer surgery on the parent.

A few implementation notes that come up in production code:

AVL trees give the tightest height bound of any standard balanced BST. That makes them a good fit when reads dominate writes:

Their downside is rebalancing cost on writes. A delete can trigger O(log n) rotations, and the constant factors are higher than a red-black tree because the invariant is stricter.

The two structures both guarantee O(log n) per operation but make different trade-offs.

The rule of thumb most production systems follow: use red-black trees when writes are frequent, AVL when reads dominate. Both end up at O(log n), but the constants and pause times differ.