AVL tree

(data structure)

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: If necessary, the tree is rebalanced after insertions or deletions using rotations.

After Gary Grubb <ggrubb@sr.hp.com>.

An AVL tree is at least as balanced than a red-black tree.

Author: PEB

Implementation

Ben Pfaff's explanations and code (C), Kaz Kylheku's Austin (C) implementing sorted list, binary search tree, AVL, red-black and splay trees and conversions from any of these to any other. Worst-case behavior of traversal, annotated for real time (WOOP/ADA).

More information

explanation and example.

The structure is named for the inventors, 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.)

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.

Entry modified Thu Oct 27 09:59:08 2005.
HTML page formatted Thu Oct 27 10:13:08 2005.

Cite this as:
Paul E. Black, "AVL tree", from Dictionary of Algorithms and Data Structures, Paul E. Black, ed., NIST.
http://www.nist.gov/dads/HTML/avltree.html