Высота сбалансированного двоичного дерева

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).

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

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

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

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

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

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

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

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

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

Источник