689
правок
Изменения
м
Нет описания правки
== Высота дерева ==
Высоту поддерева с корнем <tex>x</tex> будем обозначать как <tex>h(x)</tex>, высоту поддерева <tex>T</tex> {{---}} как <tex>h(T)</tex>.
Можно показать, что в AVL-дереве высоты <tex>h</tex> не менее, чем <tex>F_h = \Omega(\varphi^h)</tex> вершин, где <tex>F_h - 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>, иначе ничего не меняет.
}}
Указанный результат получается вращениями поддерева данной вершины. Используются Для балансировки вершины используются один из 4 типа типов вращений:
{| border="1" cellpadding="5" cellspacing="0"
В каждом случае можно показать, что операция приводит к нужному результату и что полная высота уменьшается не более чем на 1 и не может увеличиться.
Все операции балансировкивращения, очевидно, требуют <tex>O(1)</tex> операций.
== Добавление вершины ==
В результате указанных действий процедура удаления вызывается не более 3 раз, так как у вершины, удаляемой по 2-му вызову, нет хотя бы одного из поддеревьев. На балансировку суммарно тратится, как и ранее, <tex> O(h) </tex> операций. Таким образом, требуемое количество действий {{---}} <tex> O(\log{n}) </tex>.
== Поиск вершины, минимум/максимум в дереве, etc. ==
Остальные операции не меняют структуры дерева, поэтому выполняются так же, как и в наивной реализации дерева поиска.
