АВЛ-дерево

АВЛ-дерево
Тип	дерево поиска
Изобретено в	1962 году
Изобретено	Адельсон-Вельский Георгий Максимович и Ландис Евгений Михайлович
Временная сложность в О-символике
	В среднем	В худшем случае
Расход памяти	O(n)	O(n)
Поиск	O(log n)	O(log n)
Вставка	O(log n)	O(log n)
Удаление	O(log n)	O(log n)

АВЛ-дерево — сбалансированное по высоте двоичное дерево поиска: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.

АВЛ — аббревиатура, образованная первыми буквами создателей (советских учёных) Адельсон-Вельского Георгия Максимовича и Ландиса Евгения Михайловича.

Максимальная высота

Максимальная высота АВЛ-дерева при заданном числе узлов :

<math>h \; \leq \; \lfloor 1.45 \log_2 (n + 2)\rfloor \;</math>

Количество возможных высот на практике сильно ограничено (при 32-битной адресации максимальная высота равна 45, при 48-битной — 68), поэтому лучше заранее подсчитать все возможные значения минимального количества узлов для каждой высоты с помощью рекуррентной формулы для дерева Фибоначчи:

<math>n_0=0</math>,

<math>n_1=1</math>,

<math>n_h=n_{h-2}+n_{h-1}+1</math>.

Промежуточные значения количества узлов будут соответствовать предыдущей (меньшей) высоте.

Балансировка

Относительно АВЛ-дерева балансировкой вершины называется операция, которая в случае разницы высот левого и правого поддеревьев = 2, изменяет связи предок-потомок в поддереве данной вершины так, что разница становится <= 1, иначе ничего не меняет. Указанный результат получается вращениями поддерева данной вершины.

Используются 4 типа вращений:

Малое левое вращение		Данное вращение используется тогда, когда высота b-поддерева — высота L = 2 и высота С <= высота R.
Большое левое вращение		Данное вращение используется тогда, когда высота b-поддерева — высота L = 2 и высота c-поддерева > высота R.
Малое правое вращение		Данное вращение используется тогда, когда высота b-поддерева — высота R = 2 и высота С <= высота L.
Большое правое вращение		Данное вращение используется тогда, когда высота b-поддерева — высота R = 2 и высота c-поддерева > высота L.

В каждом случае достаточно просто доказать то, что операция приводит к нужному результату и что полная высота уменьшается не более чем на 1 и не может увеличиться. Также можно заметить, что большое вращение это комбинация правого и левого малого вращения. Из-за условия балансированности высота дерева О(log(N)), где N- количество вершин, поэтому добавление элемента требует O(log(N)) операций.

Алгоритм добавления вершины

Показатель сбалансированности в дальнейшем будем интерпретировать как разность между высотой левого и правого поддерева, а алгоритм будет основаться на типе TAVLTree, описанном выше. Непосредственно при вставке (листу) присваивается нулевой баланс. Процесс включения вершины состоит из трех частей (данный процесс описан Никлаусом Виртом в «Алгоритмы и структуры данных»):

1. Прохода по пути поиска, пока не убедимся, что ключа в дереве нет.
2. Включения новой вершины в дерево и определения результирующих показателей балансировки.
3. «Отступления» назад по пути поиска и проверки в каждой вершине показателя сбалансированности. Если необходимо — балансировка.

Будем возвращать в качестве результата функции, уменьшилась высота дерева или нет. Предположим, что процесс из левой ветви возвращается к родителю (рекурсия идет назад), тогда возможны три случая: { h_l — высота левого поддерева, h_r — высота правого поддерева } Включение вершины в левое поддерево приведет к

1. h_l < h_r: выравняется h_l = h_r. Ничего делать не нужно.
2. h_l = h_r: теперь левое поддерево будет больше на единицу, но балансировка пока не требуется.
3. h_l > h_r: теперь h_l — h_r = 2, — требуется балансировка.

В третьей ситуации требуется определить балансировку левого поддерева. Если левое поддерево этой вершины (Tree^.left^.left) выше правого (Tree^.left^.right), то требуется большое правое вращение, иначе хватит малого правого. Аналогичные (симметричные) рассуждения можно привести и для включение в правое поддерево.

Алгоритм удаления вершины

Для простоты опишем рекурсивный алгоритм удаления. Если вершина — лист, то удалим её и вызовем балансировку всех её предков в порядке от родителя к корню. Иначе найдём самую близкую по значению вершину в поддереве наибольшей высоты (правом или левом) и переместим её на место удаляемой вершины, при этом вызвав процедуру её удаления.

Докажем, что данный алгоритм сохраняет балансировку. Для этого докажем по индукции по высоте дерева, что после удаления некоторой вершины из дерева и последующей балансировки высота дерева уменьшается не более, чем на 1. База индукции: Для листа очевидно верно. Шаг индукции: Либо условие балансированности в корне (после удаления корень может изменится) не нарушилось, тогда высота данного дерева не изменилась, либо уменьшилось строго меньшее из поддеревьев => высота до балансировки не изменилась => после уменьшится не более чем на 1.

Очевидно, что в результате указанных действий процедура удаления вызывается не более 3 раз, так как у вершины, удаляемой по второму вызову, нет одного из поддеревьев. Но поиск ближайшего каждый раз требует O(N) операций. Становится очевидной возможность оптимизации: поиск ближайшей вершины может быть выполнен по краю поддерева, что сокращает сложность до O(log(N)).

Нерекурсивная вставка в АВЛ-дерево сверху-вниз

Нерекурсивный алгоритм сложнее рекурсивного.

1. Находится место вставки и вершина, высота которой не изменится при вставке (это вершина, у которой высота левого поддерева не равна высоте правого; будем называть её PrimeNode)
2. Выполняется спуск от PrimeNode до места вставки с изменением балансов
3. Выполняется ребалансировка PrimeNode при наличии переполнения

Нерекурсивное удаление из АВЛ-дерева сверху вниз

Для реализации удаления будем исходить из того же принципа, что и при вставке: найдём вершину, удаление из которой не приведёт к изменению её высоты. Существует два случая:

1. высота левого поддерева равна высоте правого поддерева (исключая случай, когда у листа нет поддеревьев)
2. высота дерева по направлению движения меньше противоположной(«брат» направления) и баланс «брата» равен 0 (разбор этого варианта довольно сложен, так что пока без доказательства)

Для облегчения понимания приведённый алгоритм не содержит каких-либо оптимизаций. В отличие от рекурсивного алгоритма, найденная удаляемая вершина заменяется значением из левой подветви. Этот алгоритм можно оптимизировать так же, как и рекурсивный (за счёт того, что после нахождения удаляемой вершины известно направление движения):

1. ищем удаляемый элемент и попутно находим нашу замечательную вершину
2. производим изменение балансов, в случае необходимости делаем ребалансировку
3. удаляем наш элемент (в действительности не удаляем, а заменяем его ключ и значение, учёт перестановок вершин будет немного сложнее)

Расстановка балансов при удалении

Как уже говорилось, если удаляемая вершина — лист, то она удаляется, и обратный обход дерева происходит от родителя удалённого листа. Если не лист — ей находится «замена», и обратный обход дерева происходит от родителя «замены». Непосредственно после удаления элемента — «замена» получает баланс удаляемого узла.

При обратном обходе: если при переходе к родителю пришли слева — баланс увеличивается на 1, если же пришли справа — уменьшается на 1.

Это делается до тех пор, пока при изменении баланса он не станет равным −1 или 1 (обратите внимание на различие с вставкой элемента!): в данном случае такое изменение баланса будет гласить о неизменной дельта-высоте поддеревьев. Повороты происходят по тем же правилам, что и при вставке.

Расстановка балансов при одинарном повороте

Обозначим:

• «Current» — узел, баланс которого равен −2 или 2: то есть тот, который нужно повернуть (на схеме — элемент a)
• «Pivot» — ось вращения. +2: левый сын Current’а, −2: правый сын Current’а (на схеме — элемент b)

Если поворот осуществляется при вставке элемента, то баланс Pivot’а равен либо 1, либо −1. В таком случае после поворота балансы обоих устанавливаются равными 0. При удалении всё иначе: баланс Pivot’а может стать равным 0 (в этом легко убедиться).

Приведём сводную таблицу зависимости финальных балансов от направления поворота и исходного баланса узла Pivot:

Направление поворота	Old Pivot.Balance	New Current.Balance	New Pivot.Balance
Левый или Правый	-1 или +1	0	0
Правый	0	-1	+1
Левый	0	+1	-1

Расстановка балансов при двойном повороте

Pivot и Current — те же самые, но добавляется третий участник поворота. Обозначим его за «Bottom»: это (при двойном правом повороте) левый сын Pivot’а, а при двойном левом — правый сын Pivot’а.

При данном повороте — Bottom в результате всегда приобретает баланс 0, но от его исходного баланса зависит расстановка балансов для Pivot и Current.

Приведём сводную таблицу зависимости финальных балансов от направления поворота и исходного баланса узла Bottom:

Направление	Old Bottom.Balance	New Current.Balance	New Pivot.Balance
Левый или Правый	0	0	0
Правый	+1	0	-1
Правый	-1	+1	0
Левый	+1	-1	0
Левый	-1	0	+1

Оценка эффективности

Из формулы, приведённой выше, высота АВЛ-дерева никогда не превысит высоту идеально сбалансированного дерева более, чем на 45%. Для больших <math>n</math> имеет место оценка <math>1.04\log_2 {n}</math>. Таким образом, выполнение основных операций требует порядка <math>\log_2 {n}</math> сравнений. Экспериментально выяснено, что одна балансировка приходится на каждые 2 включения и на каждые 5 исключений.

См. также

Сбалансированные (самобалансирующиеся) деревья:

• Красно-чёрное дерево
• Матричное дерево
• Идеально сбалансированное дерево
• Расширяющееся дерево

Литература

• Вирт Н. Алгоритмы и структуры данных. — М.: Мир, 1989. — С. 272—286.
• Адельсон-Вельский Г. М., Ландис Е. М. Один алгоритм организации информации // Доклады АН СССР. — 1962. — Т. 146, № 2. — С. 263—266.
• Ben Pfaff. [adtinfo.org/ GNU libavl]

Отрывок, характеризующий АВЛ-дерево

«Вы, спокойные московские жители, мастеровые и рабочие люди, которых несчастия удалили из города, и вы, рассеянные земледельцы, которых неосновательный страх еще задерживает в полях, слушайте! Тишина возвращается в сию столицу, и порядок в ней восстановляется. Ваши земляки выходят смело из своих убежищ, видя, что их уважают. Всякое насильствие, учиненное против их и их собственности, немедленно наказывается. Его величество император и король их покровительствует и между вами никого не почитает за своих неприятелей, кроме тех, кои ослушиваются его повелениям. Он хочет прекратить ваши несчастия и возвратить вас вашим дворам и вашим семействам. Соответствуйте ж его благотворительным намерениям и приходите к нам без всякой опасности. Жители! Возвращайтесь с доверием в ваши жилища: вы скоро найдете способы удовлетворить вашим нуждам! Ремесленники и трудолюбивые мастеровые! Приходите обратно к вашим рукодельям: домы, лавки, охранительные караулы вас ожидают, а за вашу работу получите должную вам плату! И вы, наконец, крестьяне, выходите из лесов, где от ужаса скрылись, возвращайтесь без страха в ваши избы, в точном уверении, что найдете защищение. Лабазы учреждены в городе, куда крестьяне могут привозить излишние свои запасы и земельные растения. Правительство приняло следующие меры, чтоб обеспечить им свободную продажу: 1) Считая от сего числа, крестьяне, земледельцы и живущие в окрестностях Москвы могут без всякой опасности привозить в город свои припасы, какого бы роду ни были, в двух назначенных лабазах, то есть на Моховую и в Охотный ряд. 2) Оные продовольствия будут покупаться у них по такой цене, на какую покупатель и продавец согласятся между собою; но если продавец не получит требуемую им справедливую цену, то волен будет повезти их обратно в свою деревню, в чем никто ему ни под каким видом препятствовать не может. 3) Каждое воскресенье и середа назначены еженедельно для больших торговых дней; почему достаточное число войск будет расставлено по вторникам и субботам на всех больших дорогах, в таком расстоянии от города, чтоб защищать те обозы. 4) Таковые ж меры будут взяты, чтоб на возвратном пути крестьянам с их повозками и лошадьми не последовало препятствия. 5) Немедленно средства употреблены будут для восстановления обыкновенных торгов. Жители города и деревень, и вы, работники и мастеровые, какой бы вы нации ни были! Вас взывают исполнять отеческие намерения его величества императора и короля и способствовать с ним к общему благополучию. Несите к его стопам почтение и доверие и не медлите соединиться с нами!»
В отношении поднятия духа войска и народа, беспрестанно делались смотры, раздавались награды. Император разъезжал верхом по улицам и утешал жителей; и, несмотря на всю озабоченность государственными делами, сам посетил учрежденные по его приказанию театры.
В отношении благотворительности, лучшей доблести венценосцев, Наполеон делал тоже все, что от него зависело. На богоугодных заведениях он велел надписать Maison de ma mere [Дом моей матери], соединяя этим актом нежное сыновнее чувство с величием добродетели монарха. Он посетил Воспитательный дом и, дав облобызать свои белые руки спасенным им сиротам, милостиво беседовал с Тутолминым. Потом, по красноречивому изложению Тьера, он велел раздать жалованье своим войскам русскими, сделанными им, фальшивыми деньгами. Relevant l'emploi de ces moyens par un acte digue de lui et de l'armee Francaise, il fit distribuer des secours aux incendies. Mais les vivres etant trop precieux pour etre donnes a des etrangers la plupart ennemis, Napoleon aima mieux leur fournir de l'argent afin qu'ils se fournissent au dehors, et il leur fit distribuer des roubles papiers. [Возвышая употребление этих мер действием, достойным его и французской армии, он приказал раздать пособия погоревшим. Но, так как съестные припасы были слишком дороги для того, чтобы давать их людям чужой земли и по большей части враждебно расположенным, Наполеон счел лучшим дать им денег, чтобы они добывали себе продовольствие на стороне; и он приказал оделять их бумажными рублями.]
В отношении дисциплины армии, беспрестанно выдавались приказы о строгих взысканиях за неисполнение долга службы и о прекращении грабежа.

Х
Но странное дело, все эти распоряжения, заботы и планы, бывшие вовсе не хуже других, издаваемых в подобных же случаях, не затрогивали сущности дела, а, как стрелки циферблата в часах, отделенного от механизма, вертелись произвольно и бесцельно, не захватывая колес.
В военном отношении, гениальный план кампании, про который Тьер говорит; que son genie n'avait jamais rien imagine de plus profond, de plus habile et de plus admirable [гений его никогда не изобретал ничего более глубокого, более искусного и более удивительного] и относительно которого Тьер, вступая в полемику с г м Феном, доказывает, что составление этого гениального плана должно быть отнесено не к 4 му, а к 15 му октября, план этот никогда не был и не мог быть исполнен, потому что ничего не имел близкого к действительности. Укрепление Кремля, для которого надо было срыть la Mosquee [мечеть] (так Наполеон назвал церковь Василия Блаженного), оказалось совершенно бесполезным. Подведение мин под Кремлем только содействовало исполнению желания императора при выходе из Москвы, чтобы Кремль был взорван, то есть чтобы был побит тот пол, о который убился ребенок. Преследование русской армии, которое так озабочивало Наполеона, представило неслыханное явление. Французские военачальники потеряли шестидесятитысячную русскую армию, и только, по словам Тьера, искусству и, кажется, тоже гениальности Мюрата удалось найти, как булавку, эту шестидесятитысячную русскую армию.
В дипломатическом отношении, все доводы Наполеона о своем великодушии и справедливости, и перед Тутолминым, и перед Яковлевым, озабоченным преимущественно приобретением шинели и повозки, оказались бесполезны: Александр не принял этих послов и не отвечал на их посольство.
В отношении юридическом, после казни мнимых поджигателей сгорела другая половина Москвы.
В отношении административном, учреждение муниципалитета не остановило грабежа и принесло только пользу некоторым лицам, участвовавшим в этом муниципалитете и, под предлогом соблюдения порядка, грабившим Москву или сохранявшим свое от грабежа.
В отношении религиозном, так легко устроенное в Египте дело посредством посещения мечети, здесь не принесло никаких результатов. Два или три священника, найденные в Москве, попробовали исполнить волю Наполеона, но одного из них по щекам прибил французский солдат во время службы, а про другого доносил следующее французский чиновник: «Le pretre, que j'avais decouvert et invite a recommencer a dire la messe, a nettoye et ferme l'eglise. Cette nuit on est venu de nouveau enfoncer les portes, casser les cadenas, dechirer les livres et commettre d'autres desordres». [«Священник, которого я нашел и пригласил начать служить обедню, вычистил и запер церковь. В ту же ночь пришли опять ломать двери и замки, рвать книги и производить другие беспорядки».]
В торговом отношении, на провозглашение трудолюбивым ремесленникам и всем крестьянам не последовало никакого ответа. Трудолюбивых ремесленников не было, а крестьяне ловили тех комиссаров, которые слишком далеко заезжали с этим провозглашением, и убивали их.
В отношении увеселений народа и войска театрами, дело точно так же не удалось. Учрежденные в Кремле и в доме Познякова театры тотчас же закрылись, потому что ограбили актрис и актеров.
Благотворительность и та не принесла желаемых результатов. Фальшивые ассигнации и нефальшивые наполняли Москву и не имели цены. Для французов, собиравших добычу, нужно было только золото. Не только фальшивые ассигнации, которые Наполеон так милостиво раздавал несчастным, не имели цены, но серебро отдавалось ниже своей стоимости за золото.
Но самое поразительное явление недействительности высших распоряжений в то время было старание Наполеона остановить грабежи и восстановить дисциплину.
Вот что доносили чины армии.
«Грабежи продолжаются в городе, несмотря на повеление прекратить их. Порядок еще не восстановлен, и нет ни одного купца, отправляющего торговлю законным образом. Только маркитанты позволяют себе продавать, да и то награбленные вещи».
«La partie de mon arrondissement continue a etre en proie au pillage des soldats du 3 corps, qui, non contents d'arracher aux malheureux refugies dans des souterrains le peu qui leur reste, ont meme la ferocite de les blesser a coups de sabre, comme j'en ai vu plusieurs exemples».
«Rien de nouveau outre que les soldats se permettent de voler et de piller. Le 9 octobre».
«Le vol et le pillage continuent. Il y a une bande de voleurs dans notre district qu'il faudra faire arreter par de fortes gardes. Le 11 octobre».
[«Часть моего округа продолжает подвергаться грабежу солдат 3 го корпуса, которые не довольствуются тем, что отнимают скудное достояние несчастных жителей, попрятавшихся в подвалы, но еще и с жестокостию наносят им раны саблями, как я сам много раз видел».
«Ничего нового, только что солдаты позволяют себе грабить и воровать. 9 октября».
«Воровство и грабеж продолжаются. Существует шайка воров в нашем участке, которую надо будет остановить сильными мерами. 11 октября».]
«Император чрезвычайно недоволен, что, несмотря на строгие повеления остановить грабеж, только и видны отряды гвардейских мародеров, возвращающиеся в Кремль. В старой гвардии беспорядки и грабеж сильнее, нежели когда либо, возобновились вчера, в последнюю ночь и сегодня. С соболезнованием видит император, что отборные солдаты, назначенные охранять его особу, долженствующие подавать пример подчиненности, до такой степени простирают ослушание, что разбивают погреба и магазины, заготовленные для армии. Другие унизились до того, что не слушали часовых и караульных офицеров, ругали их и били».