2-3-4 – Деревья (стр. 1 )

2-3-4 –ДЕРЕВЬЯ

Существует еще одна разновидность сбалансированных деревьев, аналогичных по алгоритмам вставки и удаления элементов 2-3-деревьям. Это 2-3-4 – деревья.

В отличие от 2-3 –деревьев, 2-3-4- деревья допускают хранение в узлах данных. Кроме того, узлы имеют от 2-х до 4-х сыновей. Данные, хранящиеся в узлах, служат границами, разделяющими значения ключей в поддеревьях узлов.

12

 

4 18 22

0 24 26

В 2-3-4 – дереве узлы обладают еще большей гибкостью, чем в 2-3- дереве и соответственно количество разделений и слияний узлов в нем меньше, благодаря наличию 4-узлов.

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

Алгоритмы вставки и удаления также аналогичны 2-3- деревьям . Они обеспечивают полную сбалансированность дерева. Если поиск при вставке заканчивается на 2-узле, то он преобразуется в 3-узел. Если это 3-узел, то он преобразуется в 4-узел. Если элемент вставляется в 4-узел, то он разделяется на два 2-узла, при этом средний элемент передается родительскому узлу. Если родительский узел тоже 4-узел, то он также разделяется на два 2-узла. Этот процесс

может распространиться вплоть до корня дерева. Если корень дерева также 4-узел, то он разделяется на два 2-узла и образуется новый корень – 2-узел, к которому присоединены два 2-узла, полученные при разделении бывшего корня. Таким образом точкой роста 2-3-4- дерева является корень дерева.

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

2-узел 3-узел 3-узел 4-узел

4-узел 4-узел

 

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

Когда корень дерева является 4-узлом, то при вставке любого элемента он автоматически разделяется и образуется новый 2-узел, который становится корнем дерева.

Пример построения 2-3-4- дерева:

1

18

18 7

 

4 19

 

 

18

 

 

Поскольку 4-узлы разделяются на пути от вершины вниз, эти деревья называются нисходящими 2-3-4- деревьями.

Максимальная высота 2-3-4- дерева h=(log2n+1), и вставка нового элемента, как правило, не изменяет ее за исключением случая, когда разделяется корень дерева.

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

До сих пор не удалось точно проанализировать аналитически производительность

2-3-4 – деревьев. Но эмпирически показано, что для балансировки 2-3-4 – деревьев используется очень мало разделений. Худший случай 2-3-4 – дерева оценивается высотой log2n, но на практике высота не приближается к этому значению.

К сожалению, реализация 2-3-4 – дерева довольно громоздка: накладные расходы, связанные с манипулированием сложными структурами узлов, рассмотрением различных сочетаний 2-, 3- и 4-узлов делают алгоритмы более медленными по сравнению с BST –деревьями.

Красно-черные деревья избавлены от этих недостатков. Они основываются на модели

2-3-4 – дерева, но используют только 2-узлы.

КРАСНО–ЧЕРНЫЕ ДЕРЕВЬЯ (RB - ДЕРЕВЬЯ)

Алгоритм вставки с нисходящим разделением прост для понимания, но реализация его громоздка.

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

RB – деревья можно считать 2-3-4 – деревьями, но 3- и 4-узлы в нем представлены абстрактно, с помощью эквивалентных групп 2-узлов.

4-узел можно представить в виде группы из трех 2-узлов.

 

Чтобы выделить эту группу в качестве 4-узла в дереве, пометим связи внутри группы цветом, например, красным.

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

 

или

 

Остальные связи, объединяющие отдельные 2-, 3- и 4-узлы, обозначим как черные связи.

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

 

B

 

R R

 

B B

или

R R

 

Пример 2-3-4 – дерева и эквивалентного ему RB – дерева выглядит следующим образом:

 

12 12

 

 

0

 

6

14

В RB – дереве алгоритм поиска соответствует стандартному алгоритму поиска в BST – дереве и поэтому работает более быстро, чем в 2-3-4 – дереве и быстрее, чем в BST – дереве.

Алгоритм вставки должен соответствовать алгоритму вставки в 2-3-4 – дерево, но выполняется на эквивалентной структуре RB – дерева. При этом дополнительные затраты на балансировку

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

Рассмотрим преобразования в RB – дереве, эквивалентные вставке в 2-3-4 – дерево. Новый элемент, то есть новый узел, как и в BST – дереве подключается в качестве листа к терминальному узлу. При этом связь, подключающая новый узел к дереву всегда красная, так как в результате подключения образуется как минимум 3-узел, то есть узел нового элемента всегда красный.

2-узел 3-узел

1) 2

1 2

1

 

3-узел 4-узел

2)

 

14 17

 

3) Подключение к 4 узлу должно вызвать разделение 4-узла на два 2-узла.

Как упоминалось выше, можно использовать схему нисходящего и восходящего разделения

4-узлов и схема нисходящего разделения имеет свои преимущества. Поэтому рассмотрим вначале схему нисходящего разделения 4-узла, лежащего на пути поиска при вставке нового элемента.

3а)

2 3

В 2-3-4:

4 2 2