Изменения
→Высота дерева
== Высота дерева ==
{{Теорема
|statement=АВЛ-дерево с <tex>n</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.
||proof=
Высоту поддерева с корнем <tex>x</tex> будем обозначать как <tex>h(x)</tex>, высоту поддерева <tex>T</tex> {{---}} как <tex>h(T)</tex>.
Пусть <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>. Тогда, как легко видеть, <tex>m_{h+2} = m_{h+1} + m_h + 1</tex>, откуда <tex>m_h = F_{h+2} - 1</tex>, где <tex>F_h - h</tex>-ое число Фибоначчи. <tex>F_h = \Omega(\varphi^h)</tex>, <tex>\varphi = \frac{ \sqrt{5}+1}{2}</tex>. Делая замену <tex>h = \log_\varphi{n}</tex>, получаем, что высота AVL-дерева из n вершин {{---}} <tex>O(\log{n})</tex>.
}}
== Балансировка ==
