Editing AVL tree (section)

{{Short description|Self-balancing binary search tree}}
{{Cleanup MOS|date=November 2021}}
{{Infobox data structure-amortized
| name = AVL tree
| type = [[Tree (data structure)|Tree]]
| invented_by = [[Georgy Adelson-Velsky]] and [[Evgenii Landis]]
| invented_year = 1962|
| space_avg = <math>\text{O}(n)</math>
| search_avg = <math>\text{O}(\log n)</math><ref name="wiscurl">{{Cite web |last=Eric Alexander |title=AVL Trees |url=http://pages.cs.wisc.edu/~ealexand/cs367/NOTES/AVL-Trees/index.html |archive-url=https://web.archive.org/web/20190731124716/https://pages.cs.wisc.edu/~ealexand/cs367/NOTES/AVL-Trees/index.html |archive-date=July 31, 2019}}</ref>
| search_worst = <math>\text{O}(\log n)</math><ref name="wiscurl" />
| insert_avg = <math>\text{O}(\log n)</math><ref name="wiscurl" />
| insert_worst = <math>\text{O}(\log n)</math><ref name="wiscurl" />
| delete_avg = <math>\text{O}(\log n)</math><ref name="wiscurl" />
| delete_worst = <math>\text{O}(\log n)</math><ref name="wiscurl" />
}}
[[File:AVL Tree Example.gif|thumb|Animation showing the insertion of several elements into an AVL tree. It includes left, right, left-right and right-left rotations.]]
[[Image:AVL-tree-wBalance_K.svg|thumb|right|262px|Fig. 1: AVL tree with balance factors (green)]]

In [[computer science]], an '''AVL tree''' (named after inventors '''A'''delson-'''V'''elsky and '''L'''andis) is a [[self-balancing binary search tree]]. In an AVL tree, the heights of the two [[child nodes|child]] 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 {{math|[[big O notation|O]](log ''n'')}} time in both the average and worst cases, where <math>n</math> 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 rotation]]s.

The AVL tree is named after its two [[Soviet Union|Soviet]] inventors, [[Georgy Adelson-Velsky]] and [[Evgenii Landis]], who published it in their 1962 paper "An algorithm for the organization of information".<ref>{{Cite journal |last1=Adelson-Velsky |first1=Georgy |last2=Landis |first2=Evgenii |year=1962 |title=An algorithm for the organization of information |journal=[[Proceedings of the USSR Academy of Sciences]] |language=ru |volume=146 |pages=263–266}} [https://zhjwpku.com/assets/pdf/AED2-10-avl-paper.pdf English translation] by Myron J. Ricci in ''Soviet Mathematics - Doklady'', 3:1259–1263, 1962.</ref>  It is the first self-balancing binary search tree [[data structure]] to be invented.<ref>{{Cite book |last=Sedgewick |first=Robert |title=Algorithms |publisher=Addison-Wesley |year=1983 |isbn=0-201-06672-6 |page=[https://archive.org/details/algorithms00sedg/page/199 199] |chapter=Balanced Trees |author-link=Robert Sedgewick (computer scientist) |chapter-url=https://archive.org/details/algorithms00sedg/page/199 |chapter-url-access=registration}}</ref>

AVL trees are often compared with [[red–black tree]]s because both support the same set of operations and take <math>\text{O}(\log n)</math> time for the basic operations. For lookup-intensive applications, AVL trees are faster than red–black trees because they are more strictly balanced.<ref name="Pfaff1">{{Cite web |last=Pfaff |first=Ben |date=June 2004 |title=Performance Analysis of BSTs in System Software |url=http://www.stanford.edu/~blp/papers/libavl.pdf |publisher=[[Stanford University]]}}</ref> Similar to red–black trees, AVL trees are height-balanced. Both are, in general, neither [[Weight-balanced tree|weight-balanced]] nor <math>\mu</math>-balanced for any <math>\mu\leq\tfrac{1}{2}</math>;<ref>[https://cs.stackexchange.com/q/421 AVL trees are not weight-balanced? (meaning: AVL trees are not μ-balanced?)] <br />Thereby: A Binary Tree is called <math>\mu</math>-balanced, with <math>0 \le\mu\leq\tfrac12</math>, if for every node <math>N</math>, the inequality

:<math>\tfrac12-\mu\le\tfrac{|N_l|}{|N|+1}\le \tfrac12+\mu</math>
holds and <math>\mu</math> is minimal with this property. <math>|N|</math> is the number of nodes below the tree with <math>N</math> as root (including the root) and <math>N_l</math> is the left child node of <math>N</math>.</ref> that is, sibling nodes can have hugely differing numbers of descendants.