AVL Trees

Imagine a phone-book application built on a plain binary search tree. It only ever inserts contacts in alphabetical order. Every new name attaches as the right child of the previous one. The tree degenerates into a linked list of depth $n$ . A lookup that should take microseconds now scans thousands of entries. The asymptotic promise of $O(\log n)$ search silently collapses to $O(n)$ . AVL trees were introduced by Georgy Adelson-Velsky and Evgenii Landis in 1962. They fix this by attaching a simple invariant to every ordinary BST. At each node, the heights of the left and right subtrees may differ by at most one. This "height-balance" condition is checked after every insertion and deletion. It is restored using local restructuring operations called rotations. The result is the first data structure ever proven to guarantee logarithmic height. This means logarithmic-time search, insertion, and deletion. It holds no matter what order the keys arrive in. The idea matters because unordered or adversarial input is the norm in real systems. This is true, not the exception. Sorted feeds, timestamped logs, and sequential IDs are all common sources of trouble. They produce the worst-case insertion order that cripples a naive BST. AVL trees were the historical proof-of-concept that self-balancing search trees are possible at all. They opened the door to the entire family of balanced trees. This includes Red-Black Trees, B-trees, and beyond. These now underlie databases, language runtimes, and operating-system kernels. This article gives the precise definition of the balance invariant. It covers the four rotation cases that restore it. It includes complete pseudocode for insertion and deletion. It gives a rigorous derivation of the $O(\log n)$ height bound. This uses a Fibonacci-style recurrence. It also provides a fully worked insertion trace. Finally, it discusses where AVL trees are used. It notes where their stricter balancing gives way to the more relaxed but faster-to-update Red-Black trees.

Key takeaways

An AVL tree is a BST where every node's left and right subtree heights differ by at most 1 (the balance factor is in $\{-1,0,1\}$ ).
Insertions and deletions can violate this invariant at ancestors of the changed node; it is restored using rotations (single or double).
There are exactly four imbalance shapes — Left-Left, Right-Right, Left-Right, Right-Left — each fixed by one or two rotations in $O(1)$ time.
The height-balance invariant forces $h = O(\log n)$ : the minimum node count for height $h$ grows like Fibonacci numbers, giving $h \le 1.44 \log_2 n$ .
Search, insert, and delete are all $O(\log n)$ worst case; insert needs at most one rebalancing rotation (pair), delete may need $O(\log n)$ rotations up the path.
AVL trees are more rigidly balanced than Red-Black Trees, giving faster lookups but slower updates — a classic read/write tradeoff.

The core insight

Bounding the height-difference between sibling subtrees to at most 1, and restoring that bound with $O(1)$ -time rotations after every update, forces the tree's height — and hence every operation's cost — to stay $O(\log n)$ .

The idea

An AVL tree is a binary search tree augmented with one extra structural rule: for every node $x$ , define its balance factor

\mathrm{bf}(x) = \mathrm{height}(x.\text{left}) - \mathrm{height}(x.\text{right}),

where the height of an empty subtree is defined as $-1$ (or equivalently, treat a missing child as height $-1$ and a leaf as height $0$ ). The AVL invariant requires

\mathrm{bf}(x) \in \{-1, 0, +1\} \quad \text{for every node } x.

A tree satisfying this for all nodes is called height-balanced. Note this is strictly weaker than requiring the tree be a complete or perfect binary tree — an AVL tree can have subtrees whose sizes differ by a large amount, as long as their heights are close. This distinction is the whole reason AVL trees achieve logarithmic height with only local, $O(1)$ -time repair operations, rather than needing global rebuilding. Because BST search cost is proportional to the depth of the node found, and depth is bounded by tree height, the entire performance story reduces to one question: how tall can a height-balanced tree with $n$ nodes possibly be? The answer — proven below — is $h = O(\log n)$ , with a small constant close to $\log_\varphi 2 \approx 1.44$ . Every insertion or deletion is followed by a bottom-up walk that recomputes balance factors and applies a rotation — a local pointer-rearrangement that preserves the BST ordering property while reducing a subtree's height back to what it was before the update, or leaving it unchanged. Because a single rotation is $O(1)$ , and at most $O(\log n)$ ancestors must be checked, each update runs in $O(\log n)$ time — matching the cost of the search that locates the update point.

How it works

Rotations: the repair mechanism

A rotation re-roots a locally unbalanced subtree without breaking the BST ordering invariant (left-subtree keys $<$ node key $<$ right-subtree keys). There are two elementary rotations, mirror images of each other:

Right rotation at node $y$ with left child $x$ : $x$ becomes the new subtree root, $y$ becomes $x$ 's right child, and $x$ 's original right subtree ( $T_2$ ) becomes $y$ 's new left subtree.
Left rotation is the mirror: rotate around a node whose right child is the new root.

These are combined to fix four imbalance shapes that can arise after an insertion or deletion makes some node's balance factor reach $\pm 2$ :

Case	Shape of imbalance	Fix
LL	left child's left subtree too tall	single right rotation at the unbalanced node
RR	right child's right subtree too tall	single left rotation at the unbalanced node
LR	left child's right subtree too tall	left rotation at the left child, then right rotation at the node
RL	right child's left subtree too tall	right rotation at the right child, then left rotation at the node

Insertion

Insertion proceeds exactly as in an ordinary BST — walk down comparing keys, attach the new node as a leaf — and then walks back up the search path, recomputing heights and balance factors, and rotating at the first (deepest) node found unbalanced. ``` function INSERT(root, key): if root is null: return new Node(key, height = 0) if key < root.key: root.left = INSERT(root.left, key) else if key > root.key: root.right = INSERT(root.right, key) else: return root // duplicate key: no-op (policy choice) UPDATE_HEIGHT(root) return REBALANCE(root) function REBALANCE(node): balance = HEIGHT(node.left) - HEIGHT(node.right) if balance > 1: // left-heavy if HEIGHT(node.left.left) >= HEIGHT(node.left.right): return ROTATE_RIGHT(node) // LL case else: node.left = ROTATE_LEFT(node.left) // LR case return ROTATE_RIGHT(node) if balance < -1: // right-heavy if HEIGHT(node.right.right) >= HEIGHT(node.right.left): return ROTATE_LEFT(node) // RR case else: node.right = ROTATE_RIGHT(node.right) // RL case return ROTATE_LEFT(node) return node // already balanced function ROTATE_RIGHT(y): x = y.left T2 = x.right x.right = y y.left = T2 UPDATE_HEIGHT(y) UPDATE_HEIGHT(x) return x function ROTATE_LEFT(x): y = x.right T2 = y.left y.left = x x.right = T2 UPDATE_HEIGHT(x) UPDATE_HEIGHT(y) return y function HEIGHT(node): if node is null: return -1 return node.height function UPDATE_HEIGHT(node): node.height = 1 + max(HEIGHT(node.left), HEIGHT(node.right)) ```

A key fact used implicitly above: after a single insertion, at most one rotation (or one double rotation, which is still $O(1)$ pointer work) is ever needed to restore the whole tree's balance. Once the first unbalanced ancestor on the path back to the root is fixed, the height of that subtree returns to its pre-insertion value, so no ancestor further up can have become unbalanced. This is why the `REBALANCE` call can `return` immediately after one fix at each level, and correctness only requires walking upward recomputing balance factors, stopping the rotation search once satisfied (the recursive pseudocode above still visits every ancestor to update heights, but performs at most one rotation total).

Deletion

Deletion also starts as standard BST deletion (splice out a leaf, or a node with one child, or replace a two-child node by its in-order predecessor/successor and delete that instead), then rebalances every ancestor on the path back to the root — because unlike insertion, a single deletion can require rotations at $O(\log n)$ different levels. ``` function DELETE(root, key): if root is null: return null if key < root.key: root.left = DELETE(root.left, key) else if key > root.key: root.right = DELETE(root.right, key) else: if root.left is null: return root.right if root.right is null: return root.left successor = MIN_NODE(root.right) // in-order successor root.key = successor.key root.right = DELETE(root.right, successor.key) UPDATE_HEIGHT(root) return REBALANCE(root) // may trigger at every level ```

Figure

The four rotation cases, restoring balance factor to {-1,0,1}

Complexity & correctness

Height bound — the central theorem. Let $N(h)$ be the minimum number of nodes in an AVL tree of height $h$ . A tree of minimum size achieving height $h$ has a root whose two subtrees have heights $h-1$ and $h-2$ (the largest imbalance the invariant permits), and each of those subtrees is itself minimum-sized for its height. This gives the recurrence

N(h) = 1 + N(h-1) + N(h-2), \qquad N(-1) = 0,\ N(0) = 1.

This is Fibonacci-like. Substituting $N(h) + 1 = F(h+3)$ one can check it satisfies the Fibonacci recurrence exactly, so $N(h) = F_{h+3} - 1$ where $F_k$ is the $k$ -th Fibonacci number. Since $F_k$ grows as $\varphi^k/\sqrt5$ with $\varphi = (1+\sqrt5)/2 \approx 1.618$ ,

N(h) \ge \varphi^h - 1 \quad \Rightarrow \quad n \ge \varphi^h - 1 \quad \Rightarrow \quad h \le \log_\varphi(n+1) \approx 1.4405 \log_2 n.

So the height of any $n$ -node AVL tree is $O(\log n)$ — at most about 44% more than the information-theoretic minimum $\lceil \log_2(n+1)\rceil$ of a perfectly balanced tree. This is the whole payoff: search, insert, and delete all cost $O(h) = O(\log n)$ because each walks a single root-to-node path.

Why rotations preserve the BST property. A right rotation at $y$ (with left child $x$ ) only reassigns three pointers: $x$ becomes the new local root, $y$ becomes $x$ 's right child, and $x$ 's old right subtree $T_2$ becomes $y$ 's new left child. In-order traversal order is unchanged — check the key ranges: everything in $x$ 's left subtree is $< x.key$ , everything in $T_2$ satisfies $x.key < T_2 < y.key$ (true both before and after, since $T_2$ was $x$ 's right subtree, hence $> x.key$ , and was part of $y$ 's left subtree, hence $< y.key$ ), and everything in $y$ 's right subtree is $> y.key$ . The new arrangement $x(\ldots, y(T_2, \ldots))$ respects all these bounds, so the BST invariant is preserved. The mirror argument holds for left rotation.

Why rotations restore height-balance. Take the LL case: node $z$ has $\mathrm{bf}(z) = +2$ , and its left child $y$ has $\mathrm{bf}(y) \ge 0$ (this is guaranteed because the imbalance was just created by an insertion into $y$ 's left subtree). Before the insertion, suppose $z$ 's right subtree $T_4$ had height $h$ ; then $y$ had height $h+1$ , and (being itself balanced) $y$ 's two children $x$ and $T_3$ had heights in $\{h, h-1\}$ . A single right rotation at $z$ makes $y$ the new root with children $x$ (height $h$ or $h-1$ ) and the rebuilt $z$ (whose children are now $T_3$ and $T_4$ , both height $h$ or $h-1$ ) — a height-balanced configuration whose overall height equals $y$ 's height before the insertion. This is the crux of the one-rotation argument for insertion: the rotation restores not just balance but the exact pre-insertion height of the subtree rooted there, so no ancestor further up needs to change, and only one rotation (or one LR/RL double-rotation) is ever required per insertion.

Deletion is asymmetric. Removing a node can decrease a subtree's height even after rebalancing (unlike insertion, where the rotated subtree's height is restored exactly to its old value). That height decrease can propagate: an ancestor that was fine before may now have a $\pm2$ imbalance, requiring another rotation, whose result may again shrink height and propagate further. In the worst case this cascades all the way to the root, so deletion may perform $\Theta(\log n)$ rotations — still $O(\log n)$ total time, since each is $O(1)$ work along an $O(\log n)$ -length path, but structurally different from insertion's single-fix guarantee.

Complexity summary.

Operation	Time	Space	Justification
Search	$O(\log n)$	$O(1)$ extra	bounded by height $h = O(\log n)$
Insert	$O(\log n)$	$O(\log n)$ recursion (or $O(1)$ iterative)	search path + at most one rotation
Delete	$O(\log n)$	$O(\log n)$ recursion	search/splice path + up to $O(\log n)$ rotations
Build from $n$ sorted/unsorted items	$O(n \log n)$	$O(n)$	$n$ insertions
In-order traversal	$O(n)$	$O(\log n)$ stack	visits each node once

The tradeoff: AVL's tight balance ( $\mathrm{bf} \in \{-1,0,1\}$ ) gives a smaller constant on lookup height than looser schemes, at the cost of more frequent/expensive rebalancing on updates — the exact motivation for the more relaxed invariant used by Red-Black Trees.

Worked example

Insert the keys $10, 20, 30, 25, 5, 15$ into an initially empty AVL tree, one at a time.

Step	Action	Resulting shape / imbalance	Fix applied
1	insert 10	single node 10	none
2	insert 20	10 (right: 20) — bf(10) = $-1$	none needed
3	insert 30	10→20→30 chain; bf(10) becomes $-2$ (RR case)	left rotation at 10 → new root 20, children 10 and 30
4	insert 25	25 attaches as left child of 30; bf(20)= $-1$ , bf(30)= $+1$	none needed, tree balanced
5	insert 5	5 attaches as left child of 10; bf(20)=0 overall	none needed
6	insert 15	15 attaches as right child of 10; check bf(10): left=5(h0), right=15(h0) → bf=0; bf(20): left subtree height 1, right subtree(30,25) height 1 → bf=0	none needed

Final tree after all six insertions: ``` 20 / \ 10 30 / \ / 5 15 25 ``` Every node's balance factor is in $\{-1,0,1\}$ (root: left height 1, right height 1, bf=0; node 10: bf=0; node 30: left height 0, no right, bf=+1). Height is 2 for $n=6$ nodes, comfortably within the bound $h \le 1.44\log_2 6 \approx 3.7$ . Now delete key 30. Standard BST deletion: 30 has one child (25), so splice it out, promoting 25 into 30's place. ``` 20 / \ 10 25 / \ 5 15 ``` Recompute balance factors bottom-up: node 25 (leaf) bf=0; node 10 bf=0 (heights 0,0); node 20: left height 1, right height 0 → bf = $+1$ . Still within $\{-1,0,1\}$ — no rotation needed here, illustrating that not every deletion triggers rebalancing, even though the algorithm always checks.

Common pitfalls & traps

Pitfall	Why it happens	Fix
Forgetting to update heights before checking balance factor	Rotation logic reads stale height fields	Always call `UPDATE_HEIGHT` immediately after recursive insert/delete, before computing `bf`
Choosing the wrong rotation direction (single vs. double)	Confusing which grandchild is taller in the LR/RL cases	Explicitly compare `HEIGHT(node.left.left)` vs `HEIGHT(node.left.right)` (and mirror) rather than guessing from key values
Treating deletion like insertion (stopping after first rotation)	Insertion needs only one fix; deletion can cascade	Always continue rebalancing checks up to the root on delete
Off-by-one in height of empty subtree	Some implementations use height $0$ for null instead of $-1$ , shifting all balance-factor arithmetic	Fix a single convention (this article uses height( $\text{null}$ ) $=-1$ ) and use it consistently everywhere
Ignoring duplicate keys	Naively inserting an equal key can create infinite loops or silently duplicate structure	Decide a policy up front: reject duplicates, count them, or route equals into a fixed side
Rebuilding the whole tree on every update instead of local rotation	Misunderstanding that rotations are $O(1)$ , not $O(n)$	Only three pointers change per rotation; never traverse a rotated subtree to "fix" it

Pioneers & history

Origins · 1 minGeorgy Maximovich Adelson-Velsky and how this was discovered

Georgy Maximovich Adelson-Velsky

1922–2014 · Soviet mathematician and computer scientist, Moscow

Adelson-Velsky worked at the Institute for Theoretical and Experimental Physics and later became a leading figure in Soviet computer science, contributing to chess-playing programs (his team's Kaissa won the first World Computer Chess Championship in 1974) and to foundational data-structure theory. With his student Evgenii Landis, he published the 1962 paper "An algorithm for the organization of information," introducing the first self-balancing binary search tree — now universally called the AVL tree in honor of both authors.

History

1962

— Adelson-Velsky and Landis publish the AVL tree, the first self-balancing binary search tree with proven

O(\log n)

height.

1972

— Rudolf Bayer introduces the "symmetric binary B-tree," the structure later formalized as the red-black tree, offering looser balance for cheaper updates.

1978

— Leonidas Guibas and Robert Sedgewick formalize red-black tree insertion/deletion algorithms, cementing them as the standard library choice.

1980

s–1990s — AVL and red-black trees become textbook staples; AVL trees see continued use where lookup-heavy workloads dominate (e.g., in-memory indexes, some language runtime maps).

2000

s–present — Balanced trees underpin database indexes, filesystem metadata, and standard-library ordered containers, with AVL's stricter balance still favored in read-dominated applications.

Where this matters

AVL trees are the canonical teaching example for self-balancing search trees, but their strict height-balance also makes them attractive whenever lookups vastly outnumber updates: because AVL height is provably closer to the optimal $\log_2 n$ than a red-black tree's (whose height bound is $2\log_2(n+1)$ ), AVL trees give faster worst-case search at the price of costlier rebalancing. This tradeoff shows up in:

In-memory database indexes and caches that are built once (or rarely updated) but queried millions of times, where the tighter height bound directly reduces average query latency.
Language and library implementations of ordered maps/sets in some ecosystems (certain STL-like libraries, and historically some Linux kernel data structures) choose AVL-style balancing for read-heavy internal tables.
Educational and reference implementations of interval trees, order-statistics trees, and other augmented BSTs, where AVL's simpler, more local proof of correctness makes it a cleaner base to build augmentation logic on top of.
Foreshadowing further structures: the same balance-and-rotate idea, relaxed to permit looser invariants for faster amortized updates, produces Red-Black Trees — the structure underlying most production ordered containers (C++'s `std::map`, Java's `TreeMap`, the Linux kernel's `rbtree`) — and generalizes further to weight-balanced trees, treaps, and B-trees used in on-disk indexes.

Ask the tutor: Can you show why a red-black tree's looser invariant still guarantees $O(\log n)$ height, and compare its rotation cost to AVL's?

Why is the AVL invariant based on height rather than the number of nodes in each subtree?

Balancing by subtree size (equal node counts on both sides) is much harder to maintain with cheap local operations — a single insertion can shift the "ideal" split point for the whole path to the root, requiring expensive restructuring. Balancing by height is far more forgiving: two subtrees can differ wildly in node count yet still have nearly equal height, since a subtree can be sparse-but-tall or dense-but-short. AVL's insight is that height, not size, is what actually determines search cost, and height differences of at most 1 can be restored with a single $O(1)$ rotation. This locality is what makes logarithmic-time rebalancing possible at all.

How does an AVL tree compare to a red-black tree in practice?

AVL trees maintain a tighter balance ( $\mathrm{bf}\in\{-1,0,1\}$ ), giving height at most about $1.44\log_2 n$ , versus red-black trees' looser bound of about $2\log_2(n+1)$ . That means AVL trees have faster worst-case lookups. However, red-black trees need fewer rotations per update on average (insertion needs at most 2 rotations, deletion at most 3, both with more color-flip-only fast paths), making them cheaper for write-heavy workloads. Most general-purpose library maps (Java's `TreeMap`, C++'s `std::map`) use red-black trees as a better all-around default, while AVL trees are chosen when reads dominate.

Can an AVL tree become unbalanced without anyone noticing, if rotations are implemented incorrectly?

Yes — this is one of the most common bugs. If a buggy rebalancing routine misses a case or stops checking ancestors too early (especially in deletion, which can require rebalancing at every level), the tree can silently accumulate a taller-than-guaranteed shape. There's no runtime crash; operations simply get slower as $n$ grows, often only noticeable under production-scale load. This is why implementations should include an invariant-checking assertion (verify $|\mathrm{bf}(x)|\le 1$ for all $x$ ) during testing.

Do AVL trees support order-statistics operations like "find the k-th smallest element"?

Not out of the box, but they are an excellent base for augmentation. By storing a subtree-size field at each node (updated alongside height during rotations and insertions/deletions, still $O(1)$ per rotation), an AVL tree becomes an order-statistics tree supporting `select(k)` and `rank(x)` in $O(\log n)$ time. The same augmentation technique generalizes to interval trees (storing max endpoint) and other range-query structures, since AVL rotations only touch $O(1)$ nodes, so any per-node aggregate that can be recomputed in $O(1)$ from a node's children survives rotation cheaply.

Why is the height bound derived using Fibonacci numbers?

The recurrence for the minimum node count at height $h$ , $N(h) = 1 + N(h-1) + N(h-2)$ , is structurally identical to the Fibonacci recurrence because the AVL invariant permits the two subtrees of the "worst-case" (sparsest) balanced tree to differ in height by exactly 1 — mirroring how Fibonacci numbers are defined as sums of the two preceding terms. Solving this recurrence shows $N(h)$ grows like $\varphi^h$ where $\varphi$ is the golden ratio, and inverting that relationship gives the height bound $h = O(\log_\varphi n) = O(\log_2 n)$ . It's a clean example of how a combinatorial recurrence directly yields an asymptotic bound.

What happens if I insert keys in already-sorted order into an AVL tree — does it still stay balanced?

Yes, and this is exactly the scenario AVL trees are designed to handle. In a plain BST, inserting $1,2,3,\dots,n$ in order produces a degenerate linked list of height $n-1$ . In an AVL tree, the same insertion sequence triggers a rotation roughly every other insertion (alternating LL/RR-style fixes), and the invariant guarantees the resulting height never exceeds about $1.44\log_2 n$ regardless of insertion order. You can verify this by tracing insertions of $1,2,3,4,5$ : after inserting 3, a left rotation at 1 already restores a shape resembling a balanced ternary structure, and the pattern continues self-correcting.

Is deletion in an AVL tree ever more expensive, asymptotically, than insertion?

Not asymptotically — both remain $O(\log n)$ — but deletion has a worse constant factor in the number of rotations performed. Insertion provably needs at most one rotation (or one double rotation) because the fix restores the exact pre-insertion height of the affected subtree. Deletion can shrink a subtree's height even after rebalancing, so the imbalance can propagate and trigger a rotation at every level up to the root, in the worst case $\Theta(\log n)$ rotations. Since each rotation is still $O(1)$ , the total work remains $O(\log n)$ , just with a larger hidden constant than insertion.