AVL Trees

Definitions

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.

Height

Claim: AVL trees are balanced.

Proof. Let N_h 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

Hence,

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 ₂(n + 2).

 Rotations

LL
RR
LR
RL
LL & LR LL

Insertions and Deletions

Insertions and deletions are performed as in binary search trees, and followed by rotations to correct imbalances in the outcome trees. In the case of insertions, one rotation is sufficient. In the case of deletions, O(log n) rotations at most are needed from the first point of discrepancy going up toward the root.

Delete 4
Imbalance at ‘3’ implies a LL rotation with ‘2’
Imbalance at ‘5’ implies a RR rotation with ‘8’.