AVL Tree
An AVL tree is a self-balancing binary search tree named after its inventors Adelson-Velsky and Landis. The key invariant is that for every node, the heigh...
Self-Balancing via Height Invariant
An AVL tree is a self-balancing binary search tree named after its inventors Adelson-Velsky and Landis. The key invariant is that for every node, the heights of its left and right subtrees differ by at most one. This difference is called the balance factor. A balance factor of minus one, zero, or plus one is acceptable. Any insertion or deletion that causes a balance factor outside this range triggers a rotation to restore balance.
The height of an AVL tree with N nodes is guaranteed to be O(log N). Specifically, the minimum number of nodes in an AVL tree of height h follows the Fibonacci recurrence, which means the height is at most about 1.44 times log base 2 of N. In practice, AVL trees stay very close to optimal balance, making them excellent for read-heavy workloads where search speed is paramount.
Each node in an AVL tree stores its height (or balance factor) as an additional integer field. After every insertion or deletion, you update heights bottom-up along the path from the modified node to the root and rebalance wherever necessary.
The Four Rotation Cases
When the balance factor of a node becomes plus two or minus two, a rotation is performed. There are four distinct cases. In a left-left imbalance, the inserted node is in the left subtree of the left child — a single right rotation at the unbalanced node fixes it. In a right-right imbalance, a single left rotation fixes it.
In a left-right imbalance, the inserted node is in the right subtree of the left child — a left rotation on the left child followed by a right rotation on the unbalanced node (a double rotation) is required. In a right-left imbalance, a right rotation on the right child followed by a left rotation on the unbalanced node is required.
A rotation involves reassigning three pointers and takes O(1) time. At most two rotations are needed per insertion and O(log N) rotations per deletion. After a rotation, heights of affected nodes are recomputed in O(1) time.
Worked Example and When to Choose AVL
Worked example: insert the values 30, 20, 10 into an empty AVL tree. After inserting 30 and 20 the tree is balanced. Inserting 10 makes the node 30 have balance factor plus two (left-left case). A single right rotation at 30 promotes 20 to the root with 10 as its left child and 30 as its right child. The resulting tree is balanced and has height one.
Time complexity for search, insertion, and deletion in an AVL tree is O(log N) in all cases (worst, average, best). Space complexity is O(N). The constant factor is slightly higher than a plain BST because of the rotation overhead, but the guaranteed O(log N) bound is the payoff.
Interview tip: when asked to compare AVL trees and Red-Black trees, note that AVL trees are more strictly balanced (shorter average path length) and therefore faster for lookups, while Red-Black trees perform fewer rotations on insertion and deletion and are preferred in write-heavy workloads. Most standard library sorted sets (such as those in C++ and Java) use Red-Black trees for this reason.