Изменения

Перейти к: навигация, поиск

АВЛ-дерево

143 байта добавлено, 19:05, 22 марта 2012
→‎Высота дерева
Высоту поддерева с корнем <tex>x</tex> будем обозначать как <tex>h(x)</tex>, высоту поддерева <tex>T</tex> {{---}} как <tex>h(T)</tex>.
Можно показать, что Пусть <tex>m_h</tex> {{---}} минимальное число вершин в AVL-дереве высоты <tex>h</tex> не менее. Тогда, как легко видеть, чем <tex>F_h m_{h+2} = m_{h+1} + m_h + 1</tex>, откуда <tex>m_h = \Omega(\varphi^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>. 
== Балансировка ==
'''Балансировкой вершины''' называется операция, которая в случае разницы высот левого и правого поддеревьев <tex>|h(L) - h(R)| = 2</tex>, изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева <tex>|h(L) - h(R)| \le 1</tex>, иначе ничего не меняет.
Georgy Konoplich
59
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/19766»

Навигация