Editing AVL tree (section)

===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>