Named after Adelson, Velskii, and Landis.
Trees of height O(log n) are said to be balanced. AVL trees consist of a special case in which the subtrees of each node differ by at most 1 in their height.
Balanced trees can be used to search, insert, and delete arbitrary keys in O(log n) time. In contrast, height-biased leftist trees rely on non-balanced trees to speed-up insertions and deletions in priority queues.
Claim: AVL trees are balanced.
Proof. Let Nh denote the number of nodes in an AVL tree of depth h
|Nh||> Nh-1 + Nh-2 + 1|
|> 2Nh-2 + 1|
|> 1 + 2(1 + 2Nh-4)|
|= 1 + 2 + 22N h-4|
|> 1 + 2 + 22 + 23N h-6|
|> 1 + 2 + 22 + 23 + ... + 2h/2|
|= 2h/2 - 1|
|2h/2 - 1||< n|
|h/2||< log 2(n + 1)|
|h||< 2 log 2(n + 1)|
A more careful analysis, based on Fibonacci numbers theory, implies the tighter bound of 1.44 log 2(n + 2).