AVL tree
≈ 5 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In computer science, an AVL tree (named after inventors Adelson-Velsky and Landis) is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by not more than one; if at any time they differ by more than one, rebalancing is done to restore this property. Lookup, insertion, and deletion all take 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, Georgy Adelson-Velsky and Evgenii Landis, who published it in their 19621 paper "An algorithm for the organization of information". It is the first self-balancing binary search tree data structure to be invented. AVL trees are often compared with red–black trees because both support the same set of operations and take \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 weight-balanced nor \mu -balanced for any \mu\leq\tfrac{1}{2} ; that is, sibling nodes can have hugely differing numbers of descendants.
In computer science, an AVL tree (named after inventors Adelson-Velsky and Landis) is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by not more than one; if at any time they differ by more than one, rebalancing is done to restore this property. Lookup, insertion, and deletion all take 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, Georgy Adelson-Velsky and Evgenii Landis, who published it in their 1962 paper "An algorithm for the organization of information". It is the first self-balancing binary search tree data structure to be invented. AVL trees are often compared with red–black trees because both support the same set of operations and take \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 weight-balanced nor \mu -balanced for any \mu\leq\tfrac{1}{2} ; but there are RB trees which are not AVL balanced. For maintaining the AVL (or RB) tree's invariants, rotations play an important role. In the worst case, even without rotations, AVL or RB insertions or deletions require inspections and/or updates to AVL balance factors (or RB colors). RB insertions and deletions and AVL insertions require from zero to three tail-recursive rotations and run in amortized time, thus equally constant on average. AVL deletions requiring rotations in the worst case are also on average. RB trees require storing one bit of information (the color) in each node, while AVL trees mostly use two bits for the balance factor, although, when stored at the children, one bit with meaning «lower than sibling» suffices. The bigger difference between the two data structures is their height limit. For a tree of size an AVL tree's height is at most \begin{array}{ll} h & \leqq \; c \log_2 (n + d) + b \\ & where \varphi := \tfrac{1+\sqrt 5}2 \approx 1.618 the golden ratio, c := \tfrac 1{\log_2 \varphi} \approx 1.440, b := \tfrac{c}2 \log_2 5 - 2 \approx \; -0.328, and d:=1+\tfrac{1}{\varphi^4\sqrt{5}} \approx 1.065 . a RB tree's height is at most \begin{array}{ll} h & \leqq \; 2\log_2(n+1) \end{array} . AVL trees are more rigidly balanced than RB trees with an asymptotic relation AVL/RB ≈0.720 of the maximal heights. For insertions and deletions, Ben Pfaff shows in 79 measurements a relation of AVL/RB between 0.677 and 1.077 with median ≈0.947 and geometric mean ≈0.910.
See also
WAVL tree Weight-balanced tree Splay tree Scapegoat tree B-tree T-tree List of data structures
References
Further reading
Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. . Pages 458–475 of section 6.2.3: Balanced Trees. .
External links
Text derived from https://en.wikipedia.org/w/index.php?oldid=1361768886 under CC BY-SA 4.0; modifications have been made.
References
- ↩Wikipedia “AVL tree” publication date (×1) · confidence 0.95 revision URL