AVL tree

For people who check facts

In computer science, an AVL tree is a self-balancing binary search tree where the height of the two child subtrees of any node 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).

An example of a non-AVL tree

The same tree after being height-balanced

See also: B-tree, red-black tree, splay tree

This article is a stub. You can help Wikipedia by expanding it.