AVL tree
Árbol AVL
- Date
- 1962 · confidence high
- Place
- Moscow, Soviet Union (present-day Russia)
- Credited to
- Georgy Adelson-Velsky and Evgenii Landis
- Field
- Knowledge & symbols
What it is
Adelson-Velsky and Landis published the first self-balancing binary search tree: a structure where the heights of a node's two subtrees differ by at most one, restored through rotations after every insertion or deletion, guaranteeing logarithmic-time operations.
What it led to
- Later self-balancing data structures (red-black trees, B-trees)
- In-memory databases and indexes with guaranteed access times