AVL Tree Rotations

Visualize self-balancing binary search trees through balance factors and rotations.

Concept Overview

An AVL tree (named after inventors Adelson-Velsky and Landis) is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. This strict balancing ensures that operations such as insertion, deletion, and search take O(log n) time in both the average and worst cases.

Mathematical Definition

The balance factor of a node in an AVL tree is defined as the height difference between its left and right subtrees:

BalanceFactor(N) = Height(N.left) - Height(N.right)

For any node N in an AVL tree:
BalanceFactor(N) ∈ {-1, 0, 1}

Height h of an AVL tree with n nodes satisfies:
h < 1.44 log₂(n + 2) - 0.328

Key Concepts

Left-Left (LL) Rotation: Occurs when a node is inserted into the left subtree of a left child, causing a balance factor of +2. A single right rotation restores balance.
Right-Right (RR) Rotation: Occurs when a node is inserted into the right subtree of a right child, causing a balance factor of -2. A single left rotation restores balance.
Left-Right (LR) Rotation: Occurs when a node is inserted into the right subtree of a left child. It requires a double rotation: a left rotation on the child followed by a right rotation on the unbalanced node.
Right-Left (RL) Rotation: Occurs when a node is inserted into the left subtree of a right child. It requires a right rotation on the child followed by a left rotation on the unbalanced node.

Historical Context

Invented in 1962 by Soviet computer scientists Georgy Adelson-Velsky and Evgenii Landis, the AVL tree was the very first dynamically balancing tree to be proposed. The structure laid the theoretical groundwork for subsequent balanced search tree designs, ensuring reliable worst-case performance for data retrieval systems.

Real-world Applications

Databases: Highly useful in read-intensive applications, as its strict balancing guarantees faster lookup times than Red-Black trees.
In-Memory Dictionaries: Frequently used for implementing dictionaries, sets, and mappings where elements are strictly ordered and need rapid retrieval.
Filesystem Indexing: Some filesystem implementations leverage balanced tree variants derived from AVL to quickly traverse block locations.

Related Concepts

Red-Black Tree — another popular self-balancing BST which allows looser height conditions.
B-Trees — a multi-way balanced tree used heavily in disk storage systems.
Splay Tree — a self-adjusting search tree that moves frequently accessed elements near the root.

AVL Tree Rotations