In computer science, an AVL tree is a self-balancing binary search tree, and it was the first such data structure to be invented. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.
The AVL tree is named after its two Soviet inventors, G. M. Adelson-Velskii and E. M. Landis, who published it in their 1962 paper "An algorithm for the organization of information".
AVL trees are often compared with red-black trees because they support the same set of operations and because red-black trees also take O(log n) time for the basic operations. Because AVL trees are more rigidly balanced, they are faster than red-black trees for lookup-intensive applications. Similar to red-black trees, AVL trees are in general not weight-balanced; that is, sibling nodes can have hugely differing numbers of descendants.
Read more about AVL Tree: Operations, Comparison To Other Structures
Famous quotes containing the word tree:
“A tree is beautiful, but what’s more, it has a right to life; like water, the sun and the stars, it is essential. Life on earth is inconceivable without trees. Forests create climate, climate influences peoples’ character, and so on and so forth. There can be neither civilization nor happiness if forests crash down under the axe, if the climate is harsh and severe, if people are also harsh and severe.... What a terrible future!”
—Anton Pavlovich Chekhov (1860–1904)