689
правок
Изменения
м
Высоту поддерева с корнем <tex>x</tex> будем обозначать как <tex>h(x)</tex>, высоту поддерева <tex>T</tex> {{---}} как <tex>h(T)</tex>
# Включения новой вершины в дерево и определения результирующих показателей балансировки.# "Отступления" назад по пути поиска , вплоть до корня и проверки пересчета высот в каждой вершине показателя сбалансированности. Если необходимо - балансировка.Расширим список параметров обычной процедуры вставки параметром-переменной flag, означающим, что высота дерева увеличилась.Предположим, что процесс из левой ветви возвращается к родителю (рекурсия идет назад), тогда возможны три случая:{ h<sub>l</sub> - высота левого поддерева, h<sub>r</sub> - высота правого поддерева }Включение вершины в левое поддерево приведет к# h<sub>l</sub> < h<sub>r</sub>: выравняется h<sub>l</sub> = h<sub>r</sub>. Ничего делать не нужно.# h<sub>l</sub> = h<sub>r</sub>: теперь левое поддерево будет больше на единицу, но балансировка пока не требуетсяобратном пути.# h<sub>l</sub> > h<sub>r</sub>: теперь h<sub>l</sub> - h<sub>r</sub> = 2, - требуется При необходимости осуществляется балансировка.В третьей ситуации требуется определить балансировку левого поддерева. Если левое поддерево этой вершины выше правого, то требуется двойной правый поворот, иначе хватит и малого.Аналогичные (симметричные) рассуждения можно привести и для включение в правое поддерево.
Очевидно, в В результате указанных действий процедура удаления вызывается не более 3 раз, так как у вершины, удаляемой по 2-му вызову, нет хотя бы одного из поддеревьев. Но поиск ближайшего каждый раз требует На балансировку суммарно тратится, как и ранее, <tex> O(Nh) </tex> операций. Таким образом, отсюда видна очевидная оптимизация: поиск ближайшей вершины производится по краю поддерева. Отсюда требуемое количество действий {{---}} <tex> O(\log(N){n})</tex>.
Нет описания правки
АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.
== Высота дерева ==
Высоту поддерева с корнем <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>.
== Балансировка ==
{{Определение|definition=
'''Балансировкой вершины''' называется операция, которая в случае разницы высот левого и правого поддеревьев <tex>|h(L) - h(R)| = 2</tex>, изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева <tex>|h(L) - h(R)| \le 1</tex>, иначе ничего не меняет.
|<tex>h(b) - h(R) = 2</tex> и <tex>h(c) > h(L)</tex>.
|}
В каждом случае достаточно просто можно показать, что операция приводит к нужному результату и что полная высота уменьшается не более чем на 1 и не может увеличиться. Все операции балансировки, очевидно, требуют <tex>O(1)</tex> операций.
== Алгоритм добавления Добавление вершины ==Показатель сбалансированности в дальнейшем будем интерпретировать как разность между высотой левого и правого поддерева, а алгоритм будет основаться на типе TAVLTree, описанном выше. Непосредственно при вставке (листу) присваивается нулевой баланс. Процесс включения вершины состоит из трех двух частей:
# Прохода по пути поиска, пока не убедимся, что ключа в дереве нет.
Так как в процессе добавления вершины мы рассматриваем не более, чем <tex> O(h) </tex> вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет <tex> O(\log{n}) </tex> операций. == Алгоритм удаления Удаление вершины ==
Для простоты опишем рекурсивный алгоритм удаления.
Если вершина - лист, то удалим её и вызовем балансировку всех её предков в порядке от родителя к корню.
Иначе найдём самую близкую по значению вершину в поддереве наибольшей высоты (правом или левом) и переместим её на место удаляемой вершины, при этом вызвав процедуру её удаления. Докажем, что данный алгоритм сохраняет балансировку. Для этого докажем по индукции по высоте дерева, что после удаления некоторой вершины из дерева и последующей балансировки высота дерева уменьшается не более, чем на 1. База индукции: Для листа очевидно верно. Шаг индукции: Либо условие балансированности в корне (после удаления корень может изменится) не нарушилось, тогда высота данного дерева не изменилась, либо уменьшилось строго меньшее из поддеревьев => высота до балансировки не изменилась => после уменьшится не более чем на 1.
