An AVL tree is a balanced binary search tree where the height of the two subtrees (children) of a node differs by at most one. Look-up, insertion, and deletion are $O( \ln{n})$ where $n$ is the number of nodes in the tree.

The structure is named for the inventors, Adelson-Velskii and Landis (1962).