AVL Trees: Correct Definition, Self-Balancing Mechanism, and Uses

AVL stands for Adelson-Velsky and Landis—the Soviet mathematicians who invented this self-balancing binary search tree in 1962. It does not stand for "Adaptive Variable-Length."

How AVL Trees Work

• Each node stores a balance factor = height(left subtree) – height(right subtree).
• Allowed balance factors: –1, 0, +1.
• After insertion/deletion, rotations (single/double) restore balance in O(log n) time.

Key Properties

• Height always O(log n) → guaranteed O(log n) search, insert, delete.
• More strictly balanced than red-black trees → faster lookups, slightly slower writes.

Common Applications

• In-memory databases and indexes
• Compiler symbol tables
• Real-time systems requiring predictable latency