Editing AVL tree (section)

==Comparison to other structures==
Both AVL trees and red–black (RB) trees are self-balancing binary search trees and they are related mathematically. Indeed, every AVL tree can be colored red–black,<ref>{{Cite web |last=Paul E. Black |date=2015-04-13 |title=AVL tree |url=https://xlinux.nist.gov/dads/HTML/avltree.html |access-date=2016-07-02 |publisher=[[National Institute of Standards and Technology]] |periodical=Dictionary of Algorithms and Data Structures}}</ref> 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 {{math|O(log ''n'')}} inspections and/or updates to AVL balance factors (or RB colors). RB insertions and deletions and AVL insertions require from zero to three [[Tail call|tail-recursive]] rotations and run in [[Amortized analysis|amortized]] {{math|O(1)}} time,<ref>{{Cite book |last1=Mehlhorn |first1=Kurt |url=http://link.springer.com/10.1007/978-3-540-77978-0 |title=Algorithms and Data Structures |last2=Sanders |first2=Peter |date=2008 |publisher=Springer Berlin Heidelberg |isbn=978-3-540-77977-3 |location=Berlin, Heidelberg |language=en |doi=10.1007/978-3-540-77978-0}}</ref>{{rp|pp.165,158}} <ref name="Dinesh">{{Cite book |url=https://www.taylorfrancis.com/books/edit/10.1201/9781315119335/handbook-data-structures-applications-dinesh-mehta-sartaj-sahni |title=Handbook of Data Structures and Applications |journal=Taylor & Francis |date=2017-12-15 |publisher=Chapman and Hall/CRC |isbn=978-1-315-11933-5 |editor=Dinesh P. Mehta |editor2=Sartaj Sahni |edition=2 |location=New York |doi=10.1201/9781315119335}}</ref> thus equally constant on average. AVL deletions requiring {{math|O(log ''n'')}} rotations in the worst case are also {{math|O(1)}} 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 {{math|''n'' ≥ 1}}
*an AVL tree's height is at most
*:<math>
\begin{array}{ll}
h & \leqq \; c \log_2 (n + d) + b \\
& < \; c \log_2 (n + 2) + b
\end{array}
</math>
:where <math>\varphi := \tfrac{1+\sqrt 5}2 \approx 1.618</math>&nbsp; the [[golden ratio]], <math>c := \tfrac 1{\log_2 \varphi} \approx 1.440,</math> &nbsp; <math>b := \tfrac{c}2 \log_2 5 - 2 \approx \; -0.328,</math> and&nbsp; <math>d:=1+\tfrac{1}{\varphi^4\sqrt{5}} \approx 1.065</math>.
*a RB tree's height is at most 
*:<math>
\begin{array}{ll}
h & \leqq \; 2\log_2(n+1)
\end{array}
</math>&nbsp;.<ref>[[Red–black tree#Proof of bounds]]</ref>

AVL trees are more rigidly balanced than RB trees with an [[Asymptotic analysis|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.<ref name="Pfaff1" />