59
правок
Изменения
→Высота дерева
Высоту поддерева с корнем <tex>x</tex> будем обозначать как <tex>h(x)</tex>, высоту поддерева <tex>T</tex> {{---}} как <tex>h(T)</tex>.
{{Лемма|statement= Пусть <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex>. Тогда, как легко видеть, тогда <tex>m_m_h = F_{h+2} = m_{h+1} + m_h + - 1</tex>, откуда где <tex>F_h - h</tex>-ое число Фибоначчи. |proof=Если <tex>m_h = F_</tex> {{h+2---}} минимальное число вершин в AVL- 1дереве высоты <tex>h</tex>. Тогда, как легко видеть, где <tex>F_h - m_{h+2} = m_{h+1} + m_h + 1</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>F_h = \Omega(\varphi^h)</tex>, <tex>\varphi = \frac{ \sqrt{5}+1}{2}</tex>. То есть
