AVL tree

In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, an AVL tree (named after inventors Adelson-Velsky and Landis) is a <a href="/facts/Self-balancing_binary_search_tree/W7WAsES0">self-balancing binary search tree</a>. In an AVL tree, the heights of the two <a href="/facts/Child_nodes/RcXz9noF">child</a> 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 <a href="/facts/Big_O_notation/weFFjSWg">O</a>(log n) time in both the average and worst cases, where 
 
 
 
 n
 
 
 {\displaystyle 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 <a href="/facts/Tree_rotation/R3SlGyI0">tree rotations</a>.
The AVL tree is named after its two <a href="/facts/Soviet_Union/m7wWsPto">Soviet</a> inventors, <a href="/facts/Georgy_Adelson-Velsky/1CpLURAR">Georgy Adelson-Velsky</a> and <a href="/facts/Evgenii_Landis/FPlw09va">Evgenii Landis</a>, who published it in their 1962 paper "An algorithm for the organization of information". It is the first self-balancing binary search tree <a href="/facts/Data_structure/yNsNvL1I">data structure</a> to be invented.
AVL trees are often compared with <a href="/facts/Red%25E2%2580%2593black_tree/ckgWTV7G">red–black trees</a> because both support the same set of operations and take 
 
 
 
 
 O
 
 (
 log
 ⁡
 n
 )
 
 
 {\displaystyle {\text{O}}(\log n)}
 
 time for the basic operations. For lookup-intensive applications, AVL trees are faster than red–black trees because they are more strictly balanced. Similar to red–black trees, AVL trees are height-balanced. Both are, in general, neither <a href="/facts/Weight-balanced_tree/Per0DBtr">weight-balanced</a> nor 
 
 
 
 μ
 
 
 {\displaystyle \mu }
 
-balanced for any 
 
 
 
 μ
 ≤
 
 
 
 1
 2
 
 
 
 
 
 {\displaystyle \mu \leq {\tfrac {1}{2}}}
 
; that is, sibling nodes can have hugely differing numbers of descendants.

AVL tree open-in-new

AVL tree