Editing AVL tree (section)

==Definition==

===Balance factor===
In a [[binary tree]] the ''balance factor'' of a node X is defined to be the height difference

:<math> \text{BF}(X) := \text{Height}(\text{LeftSubtree}(X)) - \text{Height}(\text{RightSubtree}(X)) </math><ref name="Knuth">{{Cite book |last=Knuth |first=Donald E. |title=Sorting and searching |publisher=Addison-Wesley |year=2000 |isbn=0-201-89685-0 |edition=2. ed., 6. printing, newly updated and rev. |location=Boston [u.a.] |author-link=Donald Knuth}}</ref>{{rp|459}}

of its two child sub-trees rooted by node X.

A node X with <math>\text{BF}(X)<0</math> is called "left-heavy", one with <math>\text{BF}(X)>0</math> is called "right-heavy", and one with <math>\text{BF}(X)=0</math> is sometimes simply called "balanced".

===Properties===
Balance factors can be kept up-to-date by knowing the previous balance factors and the change in height – it is not necessary to know the absolute height. For holding the AVL balance information, two bits per node are sufficient.<ref>However, the balance information can be kept in the child nodes as one bit indicating whether the parent is higher by 1 or by 2; thereby higher by 2 cannot occur for both children. This way the AVL tree is a [[WAVL tree|"rank balanced" tree]], as coined by [[#Haeupler|Haeupler, Sen and Tarjan]].</ref>

The height <math>h</math> (counted as the maximal number of levels) of an AVL tree with <math>n</math> nodes lies in the interval:<ref name="Knuth" />{{rp|460}}
:<math>\log_2(n+1) \le h < \log_\varphi(n+2) + b</math> 
where <math>\varphi := \tfrac{1+\sqrt 5}2 \approx 1.618</math>&nbsp; is the [[golden ratio]] and <math>b := \frac{\log_2 5}{2 \log_2 \varphi} - 2 \approx \; -0.3277 .</math>
This is because an AVL tree of height <math>h</math> contains at least <math>F_{h+2}-1</math> nodes where <math>\{F_n\}_{n\in\N}</math> is the [[Fibonacci number|Fibonacci sequence]] with the seed values <math>F_1=F_2=1 .</math>