Definition: 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(log n), where n is the number of nodes in the tree.
Generalization (I am a kind of ...)
height-balanced tree, balanced binary tree, binary search tree, red-black tree (when colored).
Aggregate child (... is a part of or used in me.)
left rotation, right rotation.
See also B-tree, threaded tree, Fibonacci tree.
Note: The structure is named for the inventors, Adelson-Velskii and Landis. If necessary, the tree is rebalanced after insertions or deletions using rotations.
After Gary Grubb <firstname.lastname@example.org>.
An AVL tree is at least as balanced as a red-black tree.
explanation and example.
Georgii M. Adelson-Velskii and Evgenii M. Landis, An algorithm for the organization of information, Doklady Akademii Nauk SSSR, 146:263-266, 1962 (Russian). English translation by Myron J. Ricci in Soviet Math. Doklady, 3:1259-1263, 1962.
(Doklady is Russian for "Report". Sometimes transliterated in English as Doclady or Dokladi.)
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 7 July 2014.
HTML page formatted Mon Feb 2 13:10:39 2015.
Cite this as:
Paul E. Black, "AVL tree", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 7 July 2014. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/avltree.html