AdelsonVelsky

Adelson-Velsky is a surname associated with Georgy Adelson-Velsky, a Soviet mathematician who, together with Evgenii Landis, introduced the data structure now known as the AVL tree in 1962. The acronym AVL stands for Adelson-Velsky and Landis. The AVL tree is a self-balancing binary search tree designed to preserve fast ordered operations during dynamic updates.

An AVL tree maintains a balance property in which the difference in heights between the left and right subtrees of any node, called the balance factor, is restricted to -1, 0, or +1. To restore balance after insertions or deletions, the tree performs rotations—single rotations (left or right) and double rotations (left-right or right-left)—as needed. These rebalancing steps are integrated into standard tree operations.

Because of the balance constraint, the height of an AVL tree with n nodes is limited to about 1.44 log2(n+2), ensuring that search, insertion, and deletion operations run in O(log n) time in the worst case. This strict balance incurs additional overhead during updates compared with unbalanced binary search trees, but yields consistently efficient lookup performance.

Historically, AVL trees were the first self-balancing BST to be widely studied and used, influencing later designs such as red-black trees. They remain a foundational concept in computer science and appear in various software libraries and systems that require reliable logarithmic-time performance for ordered data operations.