Изменения

Пусть <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>m_h = F_{h+2} - 1</tex> докажем по индукции.  База индукции <tex>m_1 = F_3 - 1</tex> {{---}} верно, <tex>m_1 = 1, F_3 = 2</tex>.  Допустим <tex>m_h = F_{h+2} - 1</tex> {{---}} верно. Тогда <tex>m_{h+1} = F_{h+3} - 1</tex>.Так как <tex>m_h = m_{h-1} + m_{h-2} + 1, m_{h+1} = m_h + m_{h-1} + 1</tex>, то:  <tex>m_{h+1} - m_h = m_h - m_{h-2}</tex>, <tex>m_{h+1} - m_h = F_{h+3} - F_{h+2}</tex>, <tex>m_h - m_{h-2} = F_{h+3} - F_{h+2}</tex>, <tex>F_{h+2} - F_h = F_{h+1}</tex>, <tex>F_{h+1} = F_{h+1}</tex>.  Таким образом, равенство <tex>m_h = F_{h+2} - 1</tex> {{---}} доказано. <tex>F_h = \Omega(\varphi^h)</tex>, <tex>\varphi = \frac{ \sqrt{5}+1}{2}</tex>. Делая замену То есть <tex>n \geqslant \varphi^{h = }</tex> Логарифмируя по основанию <tex>\varphi</tex>, получаем <tex>\log_{\varphi{}n}\geqslant h</tex> Таким образом, получаем, что высота AVL-дерева из n вершин {{---}} <tex>O(\log{n})</tex>..