An
AVL tree is a balanced
binary search tree where the height of the two
child subtrees differ by at most one, otherwise known as
height-balanced[?]. Look-up, insertion and deletion are all
O(log(
n)) in both the average and worst cases. Additions and deletions may require the tree to be rebalanced by one or more
tree rotations. The AVL tree is named after its inventors,
Adelson-Velskii[?] and
Landis[?] (
1962).
See also: B-tree, Red-Black tree