The AVL Tree

A binary search tree places smaller keys in a node’s left subtree and larger keys in its right subtree. Search and updates follow one root-to-leaf path, so their cost depends on the tree’s height.

An unrestricted tree can become a chain after sorted insertions. An AVL tree, introduced by Georgy Adelson-Velsky and Evgenii Landis in 1962, repairs height differences after every insertion and deletion. Single-key queries and updates therefore take O(log n) time in the worst case.

For each node x, define balance(x) = height(left) − height(right). An AVL tree requires every balance factor to be −1, 0, or +1. This convention assigns an empty subtree height −1 and a leaf height 0; a convention shifted by one gives the same balance factors.

An update changes heights only along the path from the modified position to the root. The algorithm walks upward, recomputes each height or balance factor, and rotates when the absolute value reaches 2.

Let N(h) be the minimum number of stored nodes in an AVL tree of height h. The sparsest valid tree has child heights h − 1 and h − 2, so N(h) = 1 + N(h − 1) + N(h − 2), with N(−1) = 0 and N(0) = 1.

This Fibonacci recurrence grows exponentially: N(h) = Fₕ₊₃ − 1. Consequently, height is O(log n); more precisely, it is less than about 1.44 log₂(n + 2). AVL’s stricter condition gives a tighter worst-case height bound than a red-black tree.

Search does not inspect heights or balance factors. Compare the target with the current key, descend left for a smaller target, and descend right for a larger target. Reaching an absent child proves that the key is not present.

The balance invariant limits the number of comparisons. Minimum, maximum, predecessor, successor, lower-bound, and upper-bound queries each take O(log n) worst-case time. A complete in-order traversal still visits all n nodes and takes O(n) time.

Insertion first adds the key at the position chosen by ordinary binary-search-tree order. Starting at its parent, recompute heights while walking toward the root. The first ancestor with balance factor +2 or −2 is the lowest unbalanced node.

The direction from that ancestor to the new key identifies one of four cases: left-left, right-right, left-right, or right-left. A single or double rotation restores the subtree to its height before insertion, so insertion needs no further rotations above that repaired subtree.

A left-left imbalance has a node z with balance factor +2 and a left child y whose left side is at least as tall as its right. Rotate right at z. Node y becomes the subtree root, z becomes its right child, and y’s former right subtree moves to z’s left.

The right-right case is the mirror image: rotate left at the unbalanced node. Each repair changes a constant number of pointers and then recomputes metadata for the demoted node before the promoted node.

A left-right imbalance bends in two directions. First rotate left at the heavy left child, converting the path into a left-left configuration. Then rotate right at the unbalanced ancestor. The middle key becomes the root of the repaired three-node region.

A right-left imbalance uses the mirrored sequence. A double rotation is two primitive rotations, but it still performs constant work. AVL insertion therefore uses at most two primitive rotations.

Deletion begins with the ordinary binary-search-tree splice. If the target has two children, replace it with its in-order successor or transplant that successor, reducing the structural removal to a node with at most one child.

Removing a node can shorten one subtree. Walk from the splice position toward the root, recomputing metadata and repairing any node whose balance factor becomes +2 or −2. The same single- and double-rotation shapes apply, but the child’s balance factor determines the exact case.

An insertion stops rotating after the lowest imbalance is repaired because that subtree regains its previous height. Deletion differs: a repaired subtree can remain one level shorter than it was before removal.

That height decrease can unbalance another ancestor. Deletion may therefore rotate at multiple levels on the path to the root, using O(log n) rotations in the worst case. The search, metadata walk, and all repairs together remain O(log n).

A rotation changes ancestry without changing in-order key order. For a right rotation, the keys remain in the sequence A < y < B < z < C before and after the pointer changes. Subtree B moves from the right of y to the left of z.

Because every key stays between the same lower and upper bounds, rotations preserve the binary-search-tree invariant. Recomputing heights afterward restores the AVL metadata for the new local shape.

An implementation can store each node’s full height or only its balance factor. A balance factor has three valid steady-state values and can fit in two bits, although object layout and alignment often consume more space. Storing heights makes recomputation direct; storing factors can reduce metadata.

Parent pointers simplify the upward repair walk but are optional when insertion and deletion retain an explicit stack or use recursion. Augmented AVL trees may also store subtree sizes, interval maxima, or other summaries, provided every rotation updates those fields.

AVL trees enforce a tighter height bound than red-black trees, which can reduce comparisons in lookup-heavy workloads. Their invariant also makes performance deterministic, unlike the expected bounds of a treap or skip list.

The stricter condition requires height or balance metadata and can make deletion rebalance at several ancestors. Pointer-based nodes also have weaker cache locality than sorted arrays and page-oriented B-trees. Workloads with frequent updates may prefer a red-black tree’s looser balance and bounded rotation counts.

AVL trees fit lookup-heavy ordered maps and sets, where their tighter height bound can reduce comparison depth. With additional subtree summaries, the same structure can support rank and select queries or interval-overlap searches while keeping updates logarithmic.

OpenZFS uses an AVL tree inside its space allocator. Each metaslab group orders candidate metaslabs by allocation state, weight, and start offset; when a metaslab’s weight changes, the allocator removes and reinserts it to restore that order. The tree therefore supports selecting and reprioritizing storage regions as free space changes.

An AVL tree is a binary search tree in which every node’s left and right subtree heights differ by at most one. The resulting Fibonacci height bound gives worst-case O(log n) single-key search, insertion, and deletion.

Insertion repairs its first imbalance with one single or double rotation. Deletion may continue repairing ancestors after the first rotation. The structure trades additional metadata and stricter update work for a tighter height bound than other common balanced binary search trees.