AVL tree
An AVL tree is a balanced binary search tree where the height of the twosubtrees (children) of a node differs by at most one. Look-up, insertion, anddeletion are , where is the number of nodes in the tree.
The structure is named for the inventors, Adelson-Velskii and Landis (1962).