AVL tree

Lore & Background

Georgy Adelson-Velsky and Evgenii Landis were Soviet inventors who published the AVL tree in their 1962 paper 'An algorithm for the organization of information'. The tree is named after the initials of their surnames. It was the first self-balancing binary search tree data structure to be invented.

The AVL tree maintains balance by ensuring that for every node, the heights of its left and right subtrees differ by no more than one. This balance factor is defined as the height of the right subtree minus the height of the left subtree, and must be -1, 0, or 1 for every node. Insertions and deletions may require rebalancing via one or more tree rotations.

Lookup, insertion, and deletion all take O(log n) time in both average and worst cases, where n is the number of nodes prior to the operation. The height h of an AVL tree with n nodes lies between log₂(n+1) and log_φ(n+2)+b, where φ is the golden ratio and b is approximately -0.3277.

Reader's Guide

The AVL tree is significant as the first self-balancing binary search tree, establishing a foundation for efficient data structures that maintain logarithmic time complexity for basic operations. Its strict balancing property—ensuring subtree heights differ by at most one—makes it particularly suitable for lookup-intensive applications, where it outperforms red–black trees due to its more stringent balance. The tree's balance factors require only two bits per node to maintain, and can be updated without knowing absolute heights. The AVL tree's invention in 1962 by Soviet scientists Adelson-Velsky and Landis marked a milestone in computer science, providing a practical solution for dynamic sets where frequent insertions and deletions occur. Its operations—search, insertion, and deletion—all run in O(log n) time, and the tree's height is bounded by the Fibonacci sequence, with a minimum node count of F_{h+2}-1 for height h. The AVL tree remains a standard reference in data structure education and is often compared with red–black trees, though it is not weight-balanced or μ-balanced for μ ≤ 1/2.

Did You Know?

• The AVL tree is named after its two Soviet inventors, Georgy Adelson-Velsky and Evgenii Landis.
• It was the first self-balancing binary search tree data structure to be invented.
• The balance factor of a node is defined as the height of its right subtree minus the height of its left subtree.
• For lookup-intensive applications, AVL trees are faster than red–black trees because they are more strictly balanced.