Что такое сбалансированное дерево

Сбалансированное бинарное дерево из отсортированного массива

Бинарное дерево поиска — дерево в котором узлы располагаются таким образом, что каждый узел с меньшим значением (относительно родителя) находится в левой части дерева, соответственно с большим — в правой.

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

Сбалансированное оно, видимо, потому что в таком дереве в среднем требуется наименьшее количество операций для поиска.

Чтобы дерево имело минимальную высоту, количество узлов левого и правого поддеревьев должны максимально приближаться друг к другу. Построим дерево по этому принципу: середина каждого подраздела массива становится корневым узлом, а левая и правая части — соответствующими для него поддеревьями. Т.к. массив отсортирован, то полученное дерево соответствует определению бинарного дерева поиска.

�� Веду телеграм-канал с еженедельными разборами задач для собеседований.

Каким образом реализовать алгоритм?

Можно каждый раз начинать вставку нового элемента с корня, рекурсивно обходя все дерево для поиска места для нового узла.

Этот способ не слишком эффективен — обход дерева требует O(log N) операций, чтобы вставить каждый узел потребуется O(n * log N) времени.

Можно исключить дополнительные проходы если рекурсивно создавать поддеревья, выбирая в качестве корня середину соответствующей части массива.

Алгоритм получился примерно такой:

• выбрать средний элемент массива в качестве корня
• начинать создавать левое поддерево из левой части массива
• начинать создавать правое поддерево из правой части массива
• повторить рекурсивно, пока не закончатся элементы в массиве

Реализация получилась довольно простой. Единственное на что нужно обратить внимание — смещение на единицу при выборе границ частей массива.

Это решения задач из книги Cracking the Coding Interview. Все опубликованные мною решения можно найти по фильтру.

АВЛ-дерево

�� В этом разделе мы на примерах разбираем сложные айтишные термины. Если вы хотите почитать вдохновляющие и честные истории о карьере в IT, переходите в другие разделы.

АВЛ-дерево, или AVL tree, — древовидная структура данных с быстрым доступом к информации. Она представляет собой бинарное дерево — иерархическую схему из вершин и путей между ними, где у одной вершины может быть не более двух потомков. АВЛ-дерево – модифицированное, у него оптимизирована структура.

АВЛ-деревья придумали еще в 60-х годах советские ученые Адельсон-Вельский и Ландис. По первым буквам их фамилий и названа структура данных — АВЛ. Это модификация классического бинарного дерева поиска, благодаря которой структура лучше сбалансирована и практически не может выродиться. Вырождением называют ситуацию, когда у каждого узла оказывается только по одному потомку и структура фактически становится линейной — это неоптимально.

Благодаря сбалансированности и борьбе с вырождением дерева информация в нем хранится более эффективно. Поэтому доступ к данным оказывается быстрее и найти их становится легче.

Кто пользуется АВЛ-деревьями

• Разработчики, которые работают с алгоритмами сортировки, хранения и поиска информации, реализуют те или иные сложные структуры. Сфера применения деревьев довольно широка, и про умение ими пользоваться могут спрашивать на собеседованиях в соответствующих отраслях.
• Аналитики данных, для которых работа с информацией — профессиональная сфера деятельности. АВЛ-деревья же — это один из методов эффективно хранить информацию и быстро получать из структуры конкретные данные. Также они могут пригодиться при реализации алгоритмов работы с данными.
• Математики, которые решают фундаментальные и практические задачи. АВЛ-деревья — подвид бинарных деревьев поиска, которые, в свою очередь, являются своеобразными графами. Все это относится к области дискретной математики: она частично пересекается с Computer Science и схожими направлениями.

Для чего нужны АВЛ-деревья

Для хранения данных. Эта структура позволяет хранить информацию в «узлах» дерева и перемещаться по ней с помощью путей, которые соединяют между собой узлы. Благодаря особому алгоритму данные хранятся относительно эффективно и с ними довольно удобно работать. Мы подробнее поговорим об этом ниже.

Для поисковых алгоритмов. АВЛ-деревья и бинарные деревья поиска в принципе — важная составная часть разнообразных алгоритмов поиска информации. Их применяют при построении поисковых систем и интеллектуальных сервисов.

Для сортировки. Хранение информации в АВЛ-дереве позволяет быстрее отсортировать данные, а задача сортировки часто встречается в IT. С помощью деревьев можно хранить и сортировать информацию в базах данных, в особых участках памяти, в хэшах и других структурах.

Для программных проверок. АВЛ-дерево может использоваться для решения некоторых стандартных задач, например для быстрой проверки существования элемента в структуре.

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

Для других задач. Деревья могут понадобиться везде, где нужны связные структуры данных, оптимизированные под определенные операции. Например, они могут быть более функциональной альтернативой связанному списку — линейной структуре данных, где в каждом элементе есть ссылка на предыдущий и/или следующий.

Как устроено двоичное дерево поиска

АВЛ-дерево — модификация двоичного, или бинарного дерева поиска. Чтобы понять, в чем его особенность, нужно сначала разобраться с бинарными деревьями в целом.

Структура. Дерево представляет собой структуру, состоящую из узлов и путей между ними, — по сути, подвид графа. Особенность в том, что дерево иерархично: у всех узлов, кроме начального, есть «родитель» и сколько-либо «потомков». Получается древовидная структура — отсюда и название.

Распределение узлов. В двоичном дереве каждый узел имеет не больше двух потомков. А двоичное дерево поиска имеет еще несколько важных характеристик. Это дерево, в котором по-особому структурированы узлы:

• все левые потомки любого узла должны иметь значения, меньшие, чем значение самого этого узла;
• все правые потомки должны быть равны или больше по значению, чем родительский узел.

Это правило должно выполняться для любого поддерева в структуре.

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

Есть и промежуточные варианты между сбалансированными и вырожденными деревьями. Чем лучше сбалансировано дерево, тем оно эффективнее. Сбалансированное дерево — такое, в котором все узлы, кроме конечных, имеют по два потомка, а все поддеревья одного уровня имеют одинаковую длину. Идеально сбалансированное дерево — как можно более широкое и низкое. Так его использование будет максимально продуктивным.

Особенности АВЛ-деревьев

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

• оно сбалансировано по высоте. Поддеревья, которые образованы левым и правым потомками каждого из узлов, должны различаться длиной не более чем на один уровень;
• из первой особенности вытекает еще одна — общая длина дерева и, соответственно, скорость операций с ним зависят от числа узлов логарифмически и гарантированно;
• вероятность получить сильно несбалансированное АВЛ-дерево крайне мала, а риск, что оно выродится, практически отсутствует.

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

Что такое балансировка

Балансировкой называют операцию, которая делает дерево более сбалансированным. В случае с АВЛ-деревьями ее применяют, если нарушается главное правило структуры: поддеревья-потомки одного узла начинают различаться больше чем на один уровень. Если разница в количестве уровней становится равна 2 или –2, запускается балансировка: связи между предками и потомками изменяются и перестраиваются так, чтобы сохранить правильную структуру.

Обычно для этого какой-либо из узлов «поворачивается» влево или вправо, то есть меняет свое расположение. Поворот может быть простым, когда расположение изменяет только один узел, или большим: при нем два узла разворачиваются в разные стороны. Большой поворот эффективен там, где не сработает обычный.

Вставка узлов в дерево

Если в структуру данных нужно добавить новую информацию, это нужно сделать по определенному алгоритму. Он такой во всех бинарных деревьях поиска, но в случае с АВЛ-деревом алгоритм несколько дополняется: за вставкой следует обязательная балансировка.

Вставка. Чтобы вставить узел в дерево, нужно пройти от его начала вниз, на каждом шаге сравнивая значение нового узла с текущими. Алгоритм доходит до конца какого-либо поддерева и делает новый узел правым или левым его потомком в зависимости от значения. Так сохраняется главное правило двоичного дерева поиска — требование к расположению элементов по значению.

Балансировка. Особенность АВЛ-деревьев тут в том, что после вставки надо проверить соотношение длин поддеревьев и, если нужно, провести балансировку. Причем балансировку может понадобиться проводить для нескольких уровней дерева — это нормально. Алгоритм для балансирования может спускаться вниз из начального узла или подниматься вверх от свежедобавленного, по ходу движения пересчитывать разницу высот и совершать повороты, если где-то обнаружилась разница в два уровня. Балансировка продолжается, пока все значения высот не пересчитаются, а дисбаланс не будет устранен.

Удаление узлов из дерева

Удалить узел также можно по стандартным правилам, принятым для бинарного дерева поиска, но опять же с несколькими нюансами.

Сначала в дереве ищется узел, который нужно удалить. Если такого узла нет, ничего не делается, а вот если он находится, все куда интереснее. Надо пройти по правому поддереву удаляемого узла и найти в нем узел с самым маленьким значением — назовем его min. После этого удаляемый узел нужно заменить на узел min, и структура дерева перестроится.

Если правого поддерева у удаляемого узла нет, вместо min на место узла подставляется его левый потомок. Если левого потомка тоже нет, значит, удаляемый узел — лист, то есть потомки у него отсутствуют в принципе. Тогда его можно просто удалить и ничего не подставлять на его место.

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

Как реализовать АВЛ-дерево

Реализация деревьев обычно сложнее, чем умозрительная структура. Но возможности для создания AVL trees есть практически в любых современных языках программирования: Java, C/C++, Python и других.

Сначала разработчик описывает структуру одного узла. Это может быть сущность, способная содержать в себе несколько переменных: в C++ для этого есть тип данных struct (структура), в Python для узла обычно создают свой класс, и так далее.

Программно описанный узел содержит в себе:

• какие-то данные, от значения которых, как говорилось выше, зависит расположение элемента — слева или справа от родителя;
• ссылки на левого и правого потомка;
• высота поддерева, которое начинается в этом узле, или разница высот между левым и правым поддеревьями.

Затем прописываются отдельные функции для определения высоты, разницы между поддеревьями и т.д.

Как сбалансировать АВЛ-дерево

Балансировка, добавление и удаление элементов — функции, которые прописываются отдельно. Обычно сначала разработчик реализует код, который совершает обычный поворот, а потом эта функция используется в другой, более крупной, отвечающей за балансировку.

Код функции балансировки сводится к проверке условий и выполнению поворотов, если проверка обнаружила дисбаланс. Сначала выполняется один простой поворот, потом, если это не помогло, — второй для другого потомка и в противоположную сторону. Так реализуется большой поворот.

Программная реализация поворота сводится к перестановке ссылок, соединяющих между собой элементы дерева. После этого пересчитываются числовые значения, которые показывают разницу между высотами.

Реализация вставки и удаления

Вставка. Функция, вставляющая элемент, обычно рекурсивная, то есть вызывает сама себя. Ее можно реализовать довольно изящно:

• вызываем функцию в начальном узле;
• если значение, которое надо вставить, меньше значения узла, где мы находимся, идем налево — вызываем ту же функцию для левого потомка;
• если значение равно или больше тому, где мы сейчас, идем направо — вызываем функцию для правого потомка;
• если мы попали в точку, где еще нет узла, создаем там узел и помещаем туда новое значение;
• вызываем функцию балансировки. Так как вставка рекурсивная, балансировка выполнится начиная с последнего открытого экземпляра функции вставки и заканчивая первым.

Удаление. Функция удаления также рекурсивная, но она сложнее. Сначала надо найти удаляемый элемент, затем перейти в его правого потомка, если он есть, и найти там минимальный узел. А потом начинаются нюансы:

• по логике структуры бинарного дерева поиска у минимального узла может быть максимум один потомок — справа. Поэтому функция, «удаляющая» минимальный узел, возвращает его правого потомка — он пригодится при замене;
• минимальный узел не удаляется безвозвратно, а подставляется на место удаляемого — опять же происходит замена ссылок;
• слева к минимальному узлу присоединяется левый потомок удаляемого узла, справа — то, что осталось от правого потомка после вычленения минимального;
• происходит балансировка.

Операции могут выглядеть сложными, особенно в части реализации. Но если вы разберетесь с тем, как работает логика деревьев, все станет понятнее. Чтобы узнать больше, можете воспользоваться нашим глоссарием или туториалами. А можете записаться на курсы и получить актуальные знания от профессионалов.

19. Сбалансированные деревья (общее понятие). Виды деревьев.

В программировании используют достаточно много видов деревьев:

N-арное дерево — это дерево, в котором каждая вершина имеет не более чем N детей.

2-3 дерево — сбалансированное дерево поиска, такое, что каждый узел может иметь два или три сына и глубина всех листьев одинакова.

А еще В-деревья, деревья цифрового поиска, нагруженные деревья, patricia-деревья, синтаксические деревья и другие.

Но все-таки чаще всего используется бинарное дерево поиска, рассмотренное нами на предыдущем занятии. Но есть одно но…
Время выполнения базовых операций в дереве поиска линейно зависит от его высоты. Но из одного и того же набора ключей можно построить разные деревья поиска:

В приведенном примере на рисунке оба дерева построены из одного
и того же набора ключей, но высота первого дерева больше, поэтому время выполнения операций над ним будет больше. Например, при поиске узла с ключом 6 в первом случае требуется просмотреть все шесть узлов, а во втором только три узла: 3->5->6.

Второе дерево лучше сбалансировано, чем первое. Чем больше узлов в дереве, тем более очевидно преимущество дерева поиска над обычным двоичным деревом при условии, что дерево поиска хорошо сбалансировано.

Как построить дерево поиска минимальной высоты?

Если набор ключей известен заранее, то его надо упорядочить. Корнем поддерева становится узел с ключом, значение которого – медиана этого набора. Для упорядоченного набора, содержащего нечетное количество ключей, – это ключ, находящийся ровно в середине набора. Для набора 1,2,3,4,5,6, который содержит четное количество ключей, в качестве медианы может быть выбран ключ как со значением 3, так и со значением 4.

Для определенности выберем 3. Узел с этим ключом будет корнем дерева.

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

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

Но полный набор ключей не всегда известен заранее.

Если ключи поступают по очереди, то построение дерева поиска будет зависеть от порядка их поступления. Если, например, ключи будут поступать в порядке 1,2,3,4,5,6, то получится дерево, изображенное на рисунке слева. Высота такого дерева максимальна для этого набора ключей, следовательно, и время выполнения операций над ним также будет максимальным. Поэтому при добавлении очередного узла, возможно, дерево понадобится перестраивать, чтобы уменьшить его высоту, сохраняя тот же набор узлов.

Идеальную балансировку поддерживать сложно. Если при добавлении очередного узла количество узлов в левом и правом поддеревьях какого-либо узла дерева станет различаться более, чем на 1, то дерево не будет являться идеально сбалансированным, и его надо будет перестраивать, чтобы восстановить свойства идеально сбалансированного дерева поиска. Поэтому обычно требования к сбалансированности дерева менее строгие.

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

⦁ АВЛ-деревья,
⦁ красно-черные деревья и
⦁ самоперестраивающиеся деревья (splay-деревья).

Для АВЛ-деревьев сбалансированность определяется разностью высот правого и левого поддеревьев любого узла. Если эта разность по модулю не превышает 1, то дерево считается сбалансированным. Данное условие проверяется после каждого добавления или удаления узла, и определен минимальный набор операций перестройки дерева, который приводит к восстановлению свойства сбалансированности, если оно оказалось нарушено.

В красно-черных деревьях каждый узел имеет дополнительное свойство – цвет, красный или черный. На дерево наложены ограничения по расположению и количеству узлов в зависимости от цвета, и определен набор операций перестройки дерева в случае нарушения этих ограничений после добавления или удаления узла. Если АВЛ-деревья накладывают достаточно строгие условия на сбалансированность, и при добавлении узлов дерево достаточно часто приходится перестраивать, то в красно-черном дереве у каждого узла высоты левого и правого поддеревьев могут отличаться не более, чем в два раза.

И, наконец, третий вид рассматриваемых сбалансированных деревьев поиска – самоперестраивающиеся деревья. В отличие от двух предыдущих видов, у этих деревьев нет никаких ограничений на расположение узлов, а сбалансированность в среднем достигается за счет того, что каждый раз перед выполнением операции над узлом этот узел перемещается в корень дерева. Но есть вероятность того, что дерево в определенный момент может оказаться не сбалансированным.

2. АВЛ-деревья.

АВЛ-деревом называется такое дерево поиска, в котором для любого его узла высоты левого и правого поддеревьев отличаются не более, чем на 1. Эта структура данных разработана советскими учеными Адельсон-Вельским Георгием Максимовичем и Ландисом Евгением Михайловичем в 1962 году. Аббревиатура АВЛ соответствует первым буквам фамилий этих ученых. Первоначально АВЛ-деревья были придуманы для организации перебора в шахматных программах. Советская шахматная программа «Каисса» стала первым официальным чемпионом мира в 1974 году.

В каждом узле АВЛ-дерева, помимо ключа, данных и указателей на левое и правое поддеревья (левого и правого сыновей), хранится показатель баланса – разность высот правого и левого поддеревьев. Ниже приведен пример АВЛ-дерева. Таким образом, получается, что в АВЛ-дереве показатель баланса balance для каждого узла, включая корень, по модулю не превосходит 1. На рисунке ниже справа приведен пример дерева, которое не является АВЛ-деревом, поскольку в одном из узлов баланс нарушен, т.е. |balance|>1. Здесь и далее для АВЛ-деревьев будем указывать в узле значение показателя баланса.

Все операции над АВЛ-деревом очень похожи на операции с бинарным деревом поиска, но каждая операция требует еще и последующей балансировки дерева.

Но анализ возможных случаев показывает, что для исправления разбалансировки в узле p достаточно выполнить либо простой поворот влево вокруг p, либо так называемый большой поворот влево вокруг того же p. Простой поворот выполняется при условии, что высота левого поддерева узла q меньше высоты его правого поддерева: h(s)≤h(D).

Большой поворот применяется при условии h(s)>h(D) и сводится в данном случае к двум простым — сначала правый поворот вокруг q и затем левый вокруг p.

3. Красно-черные деревья.

АВЛ-деревья исторически были первым примером использования сбалансированных деревьев поиска. В настоящее время более популярны красно-черные деревья (КЧ-деревья). Изобретателем красно-черного дерева считается немецкий ученый Рудольф Байер. КЧ-деревья – это двоичные деревья поиска, каждый узел которых хранит дополнительное поле color, обозначающее цвет: красный или черный, и для которых выполнены приведенные ниже свойства.

Будем считать, что если left или right равны NULL, то это «указатели» на фиктивные листья. Таким образом, все узлы – внутренние (нелистовые).

Свойства КЧ-деревьев:

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

Определение: Черной высотой узла называется количество черных узлов на пути от этого узла к узлу, у которого оба сына – фиктивные листья.

Сам узел не включается в это число. Например, у дерева, приведенного на рисунке ниже, черная высота корня равна 2.

Определение: Черная высота дерева – черная высота его корня.

4. Самоперестраивающиеся деревья (splay trees).

Самоперестраивающееся дерево – это двоичное дерево поиска, которое, в отличие от предыдущих двух видов деревьев не содержит дополнительных служебных полей в структуре данных (баланс, цвет и т.п.). Оно позволяет находить быстрее те данные, которые использовались недавно. Самоперестраивающееся дерево было придумано Робертом Тарьяном и Даниелем Слейтером в 1983 году.

Идея самоперестраивающихся деревьев основана на принципе перемещения найденного узла в корень дерева. После выполнения этой операции двоичное дерево перестраивается, оставаясь при этом деревом поиска, так, что:

⦁ если узел с ключом k есть в дереве, то он становится корнем;
⦁ если узла с ключом k нет в дереве, то корнем становится его предшественник или последователь.

Идея перемещения найденного узла в корень основана на предположении, что если тот же самый элемент потребуется в ближайшее время, он будет найден быстрее.

5. Сравнение АВЛ, красно-черных и самоперестраивающихся деревьев (splay trees).

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

По сложности реализации самые простые – АВЛ-дерево, самые сложные – КЧ-деревья, поскольку приходится рассматривать много нетривиальных случаев при вставке и удалении узла. В теории операция удаления в КЧ-дереве эффективнее, в связи с чем они больше распространены.

Самоперестраивающиеся деревья существенно отличаются от АВЛ- и КЧ-деревьев потому что не накладывают никаких ограничений на структуру дерева. Операция поиска в дереве модифицирует само дерево, поэтому в случае обращения к разным узлам самоперестраивающееся дерево может работать медленнее. К тому же, в процессе работы дерево может оказаться полностью разбалансированным. Но доказано, что если вероятности обращения к узлам фиксированы, то самоперестраивающееся дерево будет работать асимптотически не медленнее двух других рассмотренных видов деревьев. Отсутствие дополнительных полей дает преимущество по памяти.

Различные виды сбалансированных деревьев поиска используются, в частности, в системном программном обеспечении, например, в ядрах операционных систем.

В каком случае какой вид деревьев лучше всего использовать.

Если входные данные полностью рандомизированы, то наилучшим вариантом оказываются деревья поиска общего вида – несбалансированные. Если входные данные в основном рандомизированные, но периодически встречаются упорядоченные наборы, то стоит выбрать КЧ-деревья. Если при вставке преобладают упорядоченные данные, то АВЛ-деревья оказываются лучше в случае, когда дальнейший доступ к элементам рандомизирован, а самоперестраивающиеся деревья – когда дальнейшие доступ последователен или кластеризован.

Итоги занятия.

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

А на следующем занятии мы поймем, что программистам, как и бомжам, иногда тоже приходится разгребать кучи… Хотя о чем это я! Ведь его величество Интернет – это тоже огромная куча, в которой иногда можно найти очень ценные и полезные вещи…

АВЛ-дерево

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

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

Содержание

Высота дерева

Высоту поддерева с корнем [math]x[/math] будем обозначать как [math]h(x)[/math] , высоту поддерева [math]T[/math] — как [math]h(T)[/math] .

Если [math]m_h[/math] — минимальное число вершин в AVL-дереве высоты [math]h[/math] . Тогда как легко видеть, [math]m_ = m_ + m_h + 1[/math] . Равенство [math]m_h = F_ — 1[/math] докажем по индукции.

База индукции [math]m_1 = F_3 — 1[/math] — верно, [math]m_1 = 1, F_3 = 2[/math] .

Допустим [math]m_h = F_ — 1[/math] — верно.

Тогда [math]m_ = m_h + m_ + 1 = F_ — 1 + F_ — 1 + 1 = F_ — 1[/math] .

[math]F_h = \Omega(\varphi^h)[/math] , [math]\varphi = \dfrac< \sqrt<5>+1><2>[/math] . То есть

[math]n \geqslant \varphi^[/math]

Логарифмируя по основанию [math]\varphi[/math] , получаем

[math]\log_<\varphi>n \geqslant h[/math]

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

Балансировкой вершины называется операция, которая в случае разницы высот левого и правого поддеревьев [math]|h(L) — h(R)| = 2[/math] , изменяет связи предок-потомок в поддереве данной вершины так, чтобы восстановилось свойство дерева [math]|h(L) — h(R)| \leqslant 1[/math] , иначе ничего не меняет. Для балансировки будем хранить для каждой вершины разницу между высотой её левого и правого поддерева [math]diff[i] = h(L) — h(R)[/math]

Для балансировки вершины используются один из 4 типов вращений:

[math]diff[a] = -2[/math] и [math]diff[b] = -1[/math]

[math]diff[a] = -2[/math] и [math]diff[b] = 0[/math] .

[math]diff[a] = 0[/math] и [math]diff[b] = 0[/math]

[math]diff[a] = -1[/math] и [math]diff[b] = 1[/math]

[math]diff[a] = -2[/math] , [math]diff[b] = 1[/math] и [math]diff[c] = 1[/math]

[math]diff[a] = -2[/math] , [math]diff[b] = 1[/math] и [math]diff[c] = -1[/math]

[math]diff[a] = -2[/math] , [math]diff[b] = 1[/math] и [math]diff[c] = 0[/math] .

[math]diff[a] = 0[/math] , [math]diff[b] = -1[/math] и [math]diff[c] = 0[/math]

[math]diff[a] = 1[/math] , [math]diff[b] = 0[/math] и [math]diff[c] = 0[/math]

[math]diff[a] = 0[/math] , [math]diff[b] = 0[/math] и [math]diff[c] = 0[/math]

Малый левый поворот:

Большой левый поворот пишется проще:

Малое правое и большое правое вращение определяются симметрично малому левому и большому левому вращению. В каждом случае операция приводит к нужному результату, а полная высота уменьшается не более чем на [math]1[/math] и не может увеличиться.

Все вращения, очевидно, требуют [math]O(1)[/math] операций.

Операции

Добавление вершины

Пусть нам надо добавить ключ [math]t[/math] . Будем спускаться по дереву, как при поиске ключа [math]t[/math] . Если мы стоим в вершине [math]a[/math] и нам надо идти в поддерево, которого нет, то делаем ключ [math]t[/math] листом, а вершину [math]a[/math] его корнем. Дальше поднимаемся вверх по пути поиска и пересчитываем баланс у вершин. Если мы поднялись в вершину [math]i[/math] из левого поддерева, то [math]diff[i][/math] увеличивается на единицу, если из правого, то уменьшается на единицу. Если пришли в вершину и её баланс стал равным нулю, то это значит высота поддерева не изменилась и подъём останавливается. Если пришли в вершину и её баланс стал равным [math]1[/math] или [math]-1[/math] , то это значит высота поддерева изменилась и подъём продолжается. Если пришли в вершину и её баланс стал равным [math]2[/math] или [math]-2[/math] , то делаем одно из четырёх вращений и, если после вращения баланс стал равным нулю, то останавливаемся, иначе продолжаем подъём.

Так как в процессе добавления вершины мы рассматриваем не более, чем [math] O(h) [/math] вершин дерева, и для каждой запускаем балансировку не более одного раза, то суммарное количество операций при включении новой вершины в дерево составляет [math] O(\log) [/math] операций.

Удаление вершины

Для простоты опишем рекурсивный алгоритм удаления. Если вершина — лист, то удалим её, иначе найдём самую близкую по значению вершину [math]a[/math] , переместим её на место удаляемой вершины и удалим вершину [math]a[/math] . От удалённой вершины будем подниматься вверх к корню и пересчитывать баланс у вершин. Если мы поднялись в вершину [math]i[/math] из левого поддерева, то [math]diff[i][/math] уменьшается на единицу, если из правого, то увеличивается на единицу. Если пришли в вершину и её баланс стал равным [math]1[/math] или [math]-1[/math] , то это значит, что высота этого поддерева не изменилась и подъём можно остановить. Если баланс вершины стал равным нулю, то высота поддерева уменьшилась и подъём нужно продолжить. Если баланс стал равным [math]2[/math] или [math]-2[/math] , следует выполнить одно из четырёх вращений и, если после вращений баланс вершины стал равным нулю, то подъём продолжается, иначе останавливается.

В результате указанных действий на удаление вершины и балансировку суммарно тратится, как и ранее, [math] O(h) [/math] операций. Таким образом, требуемое количество действий — [math] O(\log) [/math] .

Поиск вершины, минимум/максимум в дереве, etc.

Остальные операции не меняют структуры дерева, поэтому выполняются так же, как и в наивной реализации дерева поиска.

Слияние двух AVL-деревьев

Дано два дерева [math]T_1[/math] и [math]T_2[/math] , все ключи в [math]T_1[/math] меньше ключей в [math]T_2[/math] , [math]h(T_1) \leqslant h(T_2)[/math] .

В дереве [math]T_1[/math] удаляем самую правую вершину, назовём её [math]b[/math] . Высота дерева [math]T_1[/math] может уменьшиться на единицу. В дереве [math]T_2[/math] идём от корня всегда в левое поддерево и, когда высота этого поддерева [math]P[/math] будет равна высоте дерева [math]T_1[/math] , делаем новое дерево [math]S[/math] , корнем [math]S[/math] будет вершина [math]b[/math] , левым поддеревом будет дерево [math]T_1[/math] , а правым дерево [math]P[/math] . Теперь в дереве [math]T_2[/math] у вершины, в которой мы остановились при спуске, левым поддеревом делаем дерево [math]S[/math] и запускаем балансировку. Таким образом, дерево [math]T_2[/math] будет результатом слияния двух АВЛ-деревьев.

Дерево [math]T_1[/math] и [math]T_2[/math] до слияния

Дерево [math]T_2[/math] после слияния

Алгоритм разделения AVL-дерева на два

Алгоритм первый

Пусть у нас есть дерево [math]T[/math] . Мы должны разбить его на два дерева [math]T_<1>[/math] и [math]T_<2>[/math] такие, что [math]T_ <1>\leqslant x[/math] и [math]x \lt T_<2>[/math] .

Предположим, что корень нашего дерева [math]\leqslant x[/math] , в таком случае все левое поддерево вместе с корнем после разделения отойдет в дерево [math]T_<1>[/math] . Тогда рекурсивно спускаемся в правое поддерево и там проверяем это условие (так как часть правого поддерева тоже может содержать ключи [math]\leqslant x[/math] ). Если же корень оказался [math]\gt x[/math] , то мы спускаемся той же рекурсией, но только в левое поддерево и ищем там.

Пусть мы пришли в поддерево [math]S[/math] , корень которого [math]\leqslant x[/math] . В таком случае этот корень со своим левым поддеревом должен отойти в дерево [math]T_<1>[/math] . Поэтому мы делаем следующее: запоминаем ссылку на правое поддерево [math]S[/math] , удаляем корень, запоминая его значение (не меняя конфигурацию дерева, то есть просто делаем ссылки на него NULL’ами). Таким образом, мы отделяем сбалансированное АВЛ-дерево (бывшее левое поддерево [math]S[/math] ). Делаем новую вершину со значением бывшего корня правым листом самой правой вершины [math]S[/math] и запускаем балансировку. Обозначим полученное дерево за [math]T'[/math] . Теперь нам нужно объединить его с уже построенным ранее [math]T_<1>[/math] (оно может быть пустым, если мы первый раз нашли такое дерево [math]S[/math] ). Для этого мы ищем в дереве [math]T_<1>[/math] самое правое поддерево [math]P[/math] высоты, равной высоте [math]T'[/math] (спускаясь от корня всегда в правые поддеревья). Делаем новое дерево [math]K[/math] , сливая [math]P[/math] и [math]T'[/math] (очевидно, все ключи в [math]T_<1>[/math] меньше ключей в [math]T'[/math] , поэтому мы можем это сделать). Теперь в дереве [math]T_<1>[/math] у отца вершины, в которой мы остановились при поиске дерева [math]P[/math] , правым поддеревом делаем дерево [math]K[/math] и запускаем балансировку. После нужно спуститься в правое поддерево бывшего дерева [math]S[/math] (по ссылке, которую мы ранее запомнили) и обработать его.

Если мы пришли в поддерево [math]Q[/math] , корень которого [math]\gt x[/math] , совершаем аналогичные действия: делаем NULL’ами ссылки на корень [math]Q[/math] , запоминая ссылку на его левое поддерево. Делаем новую вершину со значением бывшего корня левым листом самой левой вершины [math]Q[/math] и запускаем балансировку. Объединяем полученное АВЛ-дерево с уже построенным ранее [math]T_<2>[/math] аналогичным первому случаю способом, только теперь мы ищем самое левое поддерево [math]T_<2>[/math] .

Рассмотрим пример (рис. 1). Цветом выделены поддеревья, которые после разделения должны отойти в дерево [math]T_<1>[/math] . [math]x = 76[/math] .

Корень дерева [math]\leqslant x[/math] , поэтому он со всем выделенным поддеревом должен отойти в дерево [math]T_<1>[/math] . По описанному выше алгоритму отделяем это поддерево с корнем и делаем из них сбалансированное АВЛ-дерево [math]T'[/math] (рис. 2). Так как это первая ситуация, в которой корень рассматриваемого поддерева был [math]\leqslant x[/math] , [math]T'[/math] становится [math]T_<1>[/math] . Далее по сохраненной ссылке спускаемся в правое поддерево. Его корень [math]\gt x[/math] . Следовательно, строим из него и его правого поддерева [math]T_<2>[/math] и спускаемся в левое поддерево. Снова корень [math]\leqslant x[/math] . Строим новое [math]T'[/math] и объединяем его с уже существующим [math]T_<1>[/math] (рис. 3).

Далее действуем по алгоритму и в итоге получаем (рис. 4):

Данный алгоритм имеет сложность [math]O(\log^ <2>n)[/math] .

Алгоритм второй

Рассмотрим решение, которое имеет сложность [math]O(\log)[/math] .

Вернемся к примеру (рис. 1). Теперь рекурсивно спустимся вниз и оттуда будем строить деревья [math]T_<1>[/math] и [math]T_<2>[/math] , передавая наверх корректные АВЛ-деревья. То есть для рис. 1 первым в дерево [math]T_<1>[/math] придет вершина [math]75[/math] с левым поддеревом (выделено светло-зеленым цветом), так как это корректное АВЛ-дерево, оно же и вернется из рекурсии. Далее мы попадем в вершину со значением [math]70[/math] и должны слить ее и ее левое поддерево (выделено светло-синим) с тем, что нам пришло. И сделать это нужно так, чтобы передать наверх корректное АВЛ-дерево. Будем действовать по такому алгоритму, пока не дойдем до вершины.

Пусть мы пришли в поддерево [math]S[/math] с корнем [math]\leqslant x[/math] . Тогда сольем его с уже построенным на тот момент [math]T_<1>[/math] ( [math]T_<1>[/math] пришло снизу, а значит по условию рекурсии это корректное АВЛ-дерево, [math]S \leqslant T_<1>[/math] и [math]h(T_<1>) \leqslant h(S)[/math] ). Но так как обычная процедура слияния сливает два АВЛ-дерева, а [math]S[/math] не является корректным АВЛ-деревом, мы немного ее изменим. Пусть мы в дереве [math]S[/math] нашли самое правое поддерево [math]K[/math] , высота которого равна высоте [math]T_<1>[/math] . Тогда сделаем новое дерево [math]T'[/math] , корнем которого будет вершина [math]S[/math] (без нее это дерево является сбалансированным), правым поддеревом — [math]T_<1>[/math] , левым — [math]K[/math] . И подвесим [math]T'[/math] на то место, где мы остановились при поиске [math]K[/math] . Запустим балансировку. В случае, когда корень поддерева, в которое мы пришли, [math]\gt x[/math] , все аналогично.

Разберем пример на рис. 1. Пусть мы рекурсивно спустились до узла [math]77[/math] . Ключ больше [math]x[/math] , поэтому эта вершина станет деревом [math]T_<2>[/math] и передастся наверх. Теперь мы поднялись в узел [math]75[/math] . Он со своим левым поддеревом станет деревом [math]T_<1>[/math] и мы снова поднимемся наверх в узел [math]70[/math] . Он со своим левым поддеревом снова должен отойти в дерево [math]T_<1>[/math] , и так как теперь дерево [math]T_<1>[/math] уже не пустое, то их надо слить. После слияния по описанному выше алгоритму получим (рис. 5)

После мы поднимемся в вершину с ключом [math]80[/math] . Она с правым поддеревом отойдет в дерево [math]T_<2>[/math] (рис. 6).

И на последней итерации мы поднимемся в корень дерева с ключом [math]50[/math] , он с левым поддеревом отойдет в дерево [math]T_<1>[/math] , после чего алгоритм завершится.

Пусть поддеревьев с ключами [math]\leqslant x[/math] оказалось больше, чем поддеревьев с ключами [math]\gt x[/math] . Докажем для них логарифмическую асимптотику. Дерево на последнем уровне имеет высоту [math]H_[/math] (она может быть не равна [math]1[/math] , если мы придём в [math]x[/math] ). Его мы передаем наверх и вставляем в поддерево высотой [math]H_[/math] . [math]H_ \leqslant H_[/math] , так как разница высот поддеревьев у любой вершины не больше [math]1[/math] , и мы при переходе от [math]H_[/math] к [math]H_[/math] поднимаемся как минимум на одну вершину вверх. Слияние этих поддеревьев мы выполним за [math]H_ — H_[/math] , получим в итоге дерево высоты не большей, чем [math]H_[/math] . Его мы передадим наверх, поэтому в следующий раз слияние будет выполнено за [math]H_ — H_[/math] и так далее. Таким образом мы получим [math](H — H_<1>) + (H_ <1>— H_<2>) + (H_ <2>— H_<3>) + \cdots + (H_ — H_) = H — H_ = O(\log)[/math] .

Итоговая асимптотика алгоритма — [math]O(\log)[/math] .

АВЛ-дерево с O(1) бит в каждом узле

В обычной реализации АВЛ-дерева в каждом узле мы хранили высоту этого узла. Так как высоты левых и правых поддеревьев в АВЛ-дереве отличаются максимум на [math]1[/math] , то мы будем хранить не всю высоту дерева, а некоторое число, которое будет показывать, какое поддерево больше, или равны ли они, назовём фактор баланса. Таким образом в каждом узле будет храниться [math]1[/math] — если высота правого поддерева выше левого, [math]0[/math] — если высоты равны, и [math]-1[/math] — если правое поддерево выше левого.

Операции

Операция добавления
Пусть нам надо добавить ключ [math]t[/math] . Будем спускаться по дереву, как при поиске ключа [math]t[/math] . Если мы стоим в вершине [math]a[/math] и нам надо идти в поддерево, которого нет, то делаем ключ [math]t[/math] листом, а вершину [math]a[/math] его корнем. Пересчитываем баланс данного узла [math]a[/math] . Если он оказался [math]0[/math] , то высота поддерева с корнем в этой вершине не изменилась и пересчет балансов останавливается. Дальше начинаем подниматься вверх по дереву, исправляя балансы попутных узлов. Если мы поднялись в вершину [math]i[/math] из левого поддерева, то баланс увеличивается на единицу, если из правого, то уменьшается на единицу. Если мы пришли в вершину и её баланс стал равным [math]1[/math] или [math]-1[/math] , то это значит, что высота поддерева изменилась, и подъём продолжается. Если баланс вершины [math]a[/math] , в которую мы собираемся идти из ее левого поддерева, равен [math]1[/math] , то делается поворот для этой вершины [math]a[/math] . Аналогично делаем поворот, если баланс вершины [math]a[/math] , в которую мы идем из ее правого поддерева, равен [math]-1[/math] . Если в результате изменения узла, фактор баланса стал равен нулю, то останавливаемся, иначе продолжаем подъём.

Операция удаления
Если вершина — лист, то просто удалим её, иначе найдём ближайшую по значению вершину [math]a[/math] , поменяем ее местами с удаляемой вершиной и удалим. От удалённой вершины будем подниматься вверх к корню и пересчитывать фактор баланса вершин. Если мы поднялись в вершину [math]i[/math] из левого поддерева, то фактор баланса уменьшается на единицу, если из правого, то увеличивается на единицу. Если мы пришли в вершину и её баланс стал равным [math]1[/math] или [math]-1[/math] , то это значит, что высота поддерева не изменилась, и подъём можно остановить. Если баланс вершины стал равным нулю, то высота поддерева уменьшилась и подъём нужно продолжить. Если баланс вершины [math]a[/math] , в которую мы собираемся идти из ее левого поддерева, равен [math]-1[/math] , то делается поворот для этой вершины [math]a[/math] . Аналогично делаем поворот, если баланс вершины [math]a[/math] , в которую мы идем из ее правого поддерева, равен [math]1[/math] . Если в результате изменения узла, фактор баланса стал равен нулю, то подъём продолжается, иначе останавливается.

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

Опишем операции балансировки, а именно малый левый поворот, большой левый поворот и случаи их возникновения. Балансировка нам нужна для операций добавления и удаления узла. Для исправления факторов баланса, достаточно знать факторы баланса двух(в случае большого поворота — трех) вершин перед поворотом, и исправить значения этих же вершин после поворота. Обозначим фактор баланса вершины [math]i[/math] как [math]balance[i][/math] . Операции поворота делаются на том шаге, когда мы находимся в правом сыне вершины [math]a[/math] , если мы производим операцию добавления, и в левом сыне, если мы производим операцию удаления. Вычисления производим заранее, чтобы не допустить значения [math]2[/math] или [math]-2[/math] в вершине [math]a[/math] . На каждой иллюстрации изображен один случай высот поддеревьев. Нетрудно убедиться, что в остальных случаях всё тоже будет корректно.

1 вариант: [math]balance[a] = -1[/math] и [math]balance[b] = -1[/math]

2 вариант: [math]balance[a] = -1[/math] и [math]balance[b] = 0[/math]

1 вариант: [math]balance[a] = 0[/math] и [math]balance[b] = 0[/math]

2 вариант: [math]balance[a] = -1[/math] и [math]balance[b] = 1[/math]

1 вариант: [math]balance[a] = -1[/math] , [math]balance[b] = 1[/math] и [math]balance[c] = 1[/math]

2 вариант: [math]balance[a] = -1[/math] , [math]balance[b] = 1[/math] и [math]balance[c] = -1[/math]

3 вариант: [math]balance[a] = -1[/math] , [math]balance[b] = 1[/math] и [math]balance[c] = 0[/math]

1 вариант: [math]balance[a] = 0[/math] , [math]balance[b] = -1[/math] и [math]balance[c] = 0[/math]

2 вариант: [math]balance[a] = 1[/math] , [math]balance[b] = 0[/math] и [math]balance[c] = 0[/math]

3 вариант: [math]balance[a] = 0[/math] , [math]balance[b] = 0[/math] и [math]balance[c] = 0[/math]

Примеры

Ниже приведены примеры добавления и удаления вершины с подписанными изменениями факторов баланса каждой вершины.