Анализ вычислительной сложности алгоритмов (стр. 5 )

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

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

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

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

32. Красно-черное дерево поиска и модель 2-3-4-дерева.

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

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

B 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

B B

В RB: 3-узел

B R

 

R R B B

3в)

3 4

В 2-3-4:

4 2 2

 

B B 4-узел

В RB:

R B R R

R R B B

 

3с) 3 4

 

В 2-3-4 4 2 2

 

В RB: 3-узел

B B B

 

4-узел R разделение 4-узла R 3-узел R R

 

B R 3 B B

R R 1 B 2 B

 

3d) 3

 

В 2-3-4: 4

 

В RB: B разделение B B B

4-узла

R R R R R

 

B R R B B B

 

R R B B B

 

Два последних случая 3с) и 3d) отличительны тем, что 4-узел подключен к красному узлу 3-узла. Разделение 4-узла приводит к образованию двух 2-узлов и на более высоком уровне – к образованию структуры 3-узла. В дереве образуются две последовательные R-связи, что не может быть 2-3-4 –деревом. Можно преобразовать такое неправильное дерево так, чтобы эти две связи вели из одного узла, что соответствует 4-узлу, путем вращений. Если две последовательные R-связи ориентированы одинаково (3с), то выполняем ротацию корня неправильного дерева и изменяем цвета узлов. Если две R-связи ориентированы по-разному (3d), то сначала путем ротации верхнего R-узла сводим связи к одинаковой ориентации, а затем выполняем ротацию, аналогичную случаю 3с). Для реализации RB-дерева в структуру узла вводим дополнительный параметр – цвет color, который может быть равен RED(1) или BLACK(0) и вспомогательную функцию проверки цвета узла.

33. Красно-черное дерево поиска. Рекурсивный алгоритм вставки элементов

Red(t); Главная функция вставки в RB-дерево выглядит так: RB_Insert(t,x); Вызов этой функции: root RB_Insert(root,x)+RB_Insert1(t,x,s);

Рассмотрим, как строится RB-дерево при последовательном включении элементов:

 

RB-дерево 2-3-4 - дерево

 

1 1 1

 

19 1

1 19

19

1 1 5

5

1 5 19

5 19