AVL Tree

AVL tree is a height-balanced, self-balancing binary search tree (BST) data structure within computation and algorithms that maintains the invariant that for every internal node v, the heights of its left and right subtrees differ by at most 1. Invented in 1962 by Soviet mathematicians Georgy Adelson-Velsky and Evgenii Landis and published in the Proceedings of the USSR Academy of Sciences, the AVL tree is the earliest dynamically balanced search tree in computer science, predating both the B-tree (1970) and the red-black tree (1972/1978).

Whereas an unbalanced binary search tree degenerates into a linear chain of height n − 1 when keys are inserted in sorted order—degrading search, insertion, and deletion to O(n) time—an AVL tree restores its height-balance invariant after every modification via local pointer tree rotations (Left, Right, Left–Right, and Right–Left). These structural invariants bound the worst-case height of an n-key AVL tree to h < 1.4405 log₂(n + 2) − 0.3277, ensuring worst-case O(log n) time for point lookups, predecessor/successor queries, order-statistic rank queries, insertions, deletions, and tree joins within computational complexity theory.

Balance Factor Definition and Height Recurrence

Let T be a binary search tree where every node u stores an ordered key k(u). The height h(u) of the subtree rooted at u is h(u) = 1 + max(h(u.left), h(u.right)), with h(NIL) = −1 and leaf height 0. The balance factor BF(u) = h(u.right) − h(u.left) satisfies the AVL balance condition at every node:

Minimal AVL Trees (Fibonacci Trees) and the Golden Ratio Upper Bound

To bound the maximum height h of an n-node AVL tree, let N(h) denote the minimum number of nodes in a valid AVL tree of height h. With N(−1) = 0, N(0) = 1, and N(1) = 2, a minimal AVL tree of height h ≥ 1 combines subtrees of heights h − 1 and h − 2:

where F_k is the k-th Fibonacci number (F₃ = 2, F₄ = 3, F₅ = 5). By Binet's formula, F_h+3 > φ^h+3/√5 − 1/2 for the golden ratio φ = (1 + √5)/2 ≈ 1.618034. Since n ≥ N(h) = F_h+3 − 1, solving for h yields:

Thus, an AVL tree is at most 44.04% taller than a complete binary tree—shallower than a red-black tree (≤ 2 log₂(n + 1)).

Single and Double Rotations

Whenever an insertion or deletion causes a lowest ancestor z to reach |BF(z)| = 2, let y be the taller child of z and x the taller child of y. The imbalance is resolved in O(1) pointer updates via four rotation cases:

1. Right–Right (RR, BF(z) = +2, BF(y) ≥ 0): Single Left Rotation at z promoting y above z.
2. Left–Left (LL, BF(z) = −2, BF(y) ≤ 0): Single Right Rotation at z promoting y above z.
3. Right–Left (RL, BF(z) = +2, BF(y) = −1): Double Right–Left Rotation (Right at y, then Left at z) promoting inner grandchild x above z and y.
4. Left–Right (LR, BF(z) = −2, BF(y) = +1): Double Left–Right Rotation (Left at y, then Right at z) promoting inner grandchild x above y and z.

Rebalancing Propagation: Insertion vs. Deletion

• Insertion (O(1) Rotations): Inserting a new leaf increases the height of the lowest unbalanced ancestor z from h + 2 to h + 3. Executing the single or double rotation at z restores the subtree height to h + 2, so ancestors above z observe zero height change and at most one single or double rotation is ever needed per Insert.
• Deletion (Up to O(log n) Rotations Worst-Case, O(1) Amortized): Deleting a node can reduce the height of a balanced subtree from h + 3 to h + 2, which may propagate upward along the root path and trigger up to O(log n) rotations in the worst case (though O(1) amortized).

Two AVL trees T₁ and T₂ separated by a pivot key k can be merged via Join(T₁, k, T₂) in O(|h(T₁) − h(T₂)| + 1) time by descending the spine of the taller tree to match the height of the shorter tree, linking under k, and rebalancing upward. Using Join and its inverse Split(T, k), Blelloch, Ferizovic, and Sun (2016) showed that parallel set union, intersection, and difference on two AVL trees of sizes m ≤ n execute in optimal O(m log(1 + n/m)) work. In computational geometry and bioinformatics, AVL trees maintain the active y-status line in Bentley–Ottmann plane-sweep algorithms and underpin dynamic augmented interval trees (complementing static segment trees and Fenwick trees) for querying overlapping genomic intervals in O(log n + k) time.

When should an AVL tree be chosen over a red-black tree?

Because an AVL tree enforces a tighter height bound (1.44 log₂ n vs. 2.00 log₂ n for a red-black tree), it has shorter average and worst-case search paths and outperforms red-black trees in read-dominated workloads, whereas red-black trees are favored in mutation-heavy workloads where bounding deletion rotations to at most 3 is desirable.

Why does a double rotation succeed where a single rotation fails?

When the tallest grandchild x sits on the inside of the zig-zag path (z → y → x), a single rotation at z moves the inner subtree x intact to the other side of the pivot without decreasing its depth. A double rotation splits x's subtrees across z and y while lifting x two levels upward, reducing subtree height by 1.

1. Adelson-Velsky, G. M., & Landis, E. M. (1962). "An algorithm for the organization of information." Soviet Mathematics Doklady, 3, 1259–1263. https://mathscinet.ams.org/mathscinet-getitem?mr=0156719
2. Foster, C. C. (1965). "Information storage and retrieval using AVL trees." Proceedings of the 1965 20th National Conference of the ACM, 192–205. https://doi.org/10.1145/800197.806043
3. Mehlhorn, K., & Tsakalidis, A. (1986). "An amortized analysis of insertions into AVL-trees." SIAM Journal on Computing, 15(1), 22–33. https://doi.org/10.1137/0215002
4. Haeupler, B., Sen, S., & Tarjan, R. E. (2015). "Rank-balanced trees." ACM Transactions on Algorithms, 11(4), Article 30, 1–26. https://doi.org/10.1145/2689412
5. Blelloch, G. E., Ferizovic, D., & Sun, Y. (2016). "Just join for parallel ordered sets." Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 253–264. https://doi.org/10.1145/2935764.2935768