# 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:
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 <ggrubb@sr.hp.com>.

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

Author: PEB

## Implementation

Ben Pfaff's explanations and code (C). Maksim Goleta's Collections (C#) implementing stacks, queues, linked lists, binary search trees, AVL trees, and dictionaries. Bro. David Carlson's tutorial and code (C++). Richard McGraw's Navl-latest.tar.bz2 (C#). Worst-case behavior of traversal, annotated for real time (WOOP/ADA).
## More information

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.)

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

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

Entry modified 23 May 2011.

HTML page formatted Mon Nov 18 10:44:09 2013.

Cite this as:

Paul E. Black, "AVL tree", in
*Dictionary of Algorithms and Data Structures* [online], Vreda Pieterse and Paul E. Black, eds. 23 May 2011. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/avltree.html