Балансировка деревьев презентация

Недостаток бинарных поисковых деревьев
При создании дерева последовательностью вставок длины различных ветвей могут сильно различаться:
БПД, созданное для последовательности (2, 9, 3, 4, 8, 5, 6, 7)

Подходы к решению проблемы
Создать древовидные структуры, у которых длины ветвей будут не сильно отличаться друг от друга (сбалансированные деревья)
При этом поддержание сбалансированности должно выполняться с трудоёмкостью не большей, чем O(log N).
Варианты решения:
АВЛ-деревья;
сильно ветвящиеся деревья;
красно-чёрные деревья

АВЛ-ДЕРЕВЬЯ
АВЛ-дерево (почти сбалансированное дерево) – двоичное поисковое дерево, для каждой вершины которого высота её двух поддеревьев различается не более чем на 1.
АВЛ-деревья названы по первым буквам фамилий их изобретателей, Г. М. Адельсона-Вельского и Е. М. Ландиса, которые впервые предложили использовать АВЛ-деревья в 1962 году.

Показатель баланса вершины АВЛ-дерева
Для каждой вершины дерева будем хранить показатель её баланса:
-1, если левое поддерево длиннее правого на 1;
0, если высоты левого и правого поддерева равны;
+1, если правое поддерево длиннее левого на 1;
-2, если левое поддерево длиннее правого на 2;
+2, если правое поддерево длиннее левого на 2.
В двух последних случаях будем считать, что баланс дерева нарушен в этой вершине

Пример АВЛ-дерева с наихудшей балансировкой
54
32
71
16
11
35
61
97
90
60
57
69
+1
-1
-1
-1
-1
-1
+1
0
0
0
0
0

Оценка высоты АВЛ-дерева в зависимости от числа вершин
В идеальном случае (высоты всех поддеревьев равны)
В наихудшем случае (высоты поддеревьев различаются для каждой вершины)
В общем случае
Следовательно, основные операции (поиск, вставка, удаление) имеют трудоёмкость O(log n)

Восстановление сбалансированности вершин АВЛ-дерева после вставки
После выполнения вставки необходимо изменить показатели баланса у вершин, находящихся на ветви дерева, в которую произошла вставка.
T := добавленная вершина;
while Т <> корень do begin
S := отец T;
if T – левый сын S then
уменьшаем показатель баланса S
else
увеличиваем показатель баланса S;
if показатель баланса S=0 then
break;
if abs(показатель баланса S)=2 then begin
устраняем разбалансированность S, выполняя вращение
или двойное вращение;
break;
end;
T := S;
end;

β
Пояснение остановки при установке показателя баланса в 0
Высота дерева, начинающегося с A , не изменилась, дальнейшая проверка не нужна
До вставки
После вставки

α (h-1)
Устранение разбалансированности - вращение
До вставки (высота – h+1)
После вставки (высота – h+2)

α (h-1)
α (h-1)
Высота дерева не изменилась, дальнейшая проверка не нужна
Устранение разбалансированности – вращение (продолжение)
После вставки (высота – h+2)
После вращения (высота – h+1)

α (h-1)
Устранение разбалансированности – двойное вращение
До вставки (высота – h+1)
После вставки (высота – h+2)

α (h-1)
α (h-1)
Устранение разбалансированности – двойное вращение (продолжение)
A
α (h-1)
δ (h-1)
-2
β (h-1)
B
+1
После вставки (высота – h+2)
После двойного вращения (высота – h+1)
С
-1
γ (h-2)
С
0
B
+1
A
0
α (h-1)
β (h-1)
γ (h-2)
δ (h-1)
Высота дерева не изменилась, дальнейшая проверка не нужна

ВОССТАНОВЛЕНИЕ СБАЛАНСИРОВАННОСТИ ВЕРШИН АВЛ-ДЕРЕВА ПОСЛЕ УДАЛЕНИЯ
После выполнения удаления необходимо изменить показатели баланса у вершин, находящихся на ветви дерева, в которой произошло удаление.
if дерево не пусто then begin
S := отец удалённой вершины;
T := удалённая вершина;
while true do begin
if T – левый сын S then
увеличиваем показатель баланса S
else
уменьшаем показатель баланса S;
if abs(показатель баланса S)=1 then
break;
if abs(показатель баланса S)=2 then
устраняем разбалансированность S;
if S – корень then
break;
T := S;
S := отец S;
end;
end;

До удаления
ПОЯСНЕНИЕ ОСТАНОВКИ ПРИ УСТАНОВКЕ ПОКАЗАТЕЛЯ БАЛАНСА В ±1
A
α (h)
β (h)
0
После удаления
Высота дерева, начинающегося с A , не изменилась, дальнейшая проверка не нужна

УСТРАНЕНИЕ РАЗБАЛАНСИРОВАННОСТИ – ВРАЩЕНИЕ (тип 1)
До удаления (высота – h+2)
После удаления (высота – h+2)

УСТРАНЕНИЕ РАЗБАЛАНСИРОВАННОСТИ – ВРАЩЕНИЕ (тип 1)(продолжение)
После удаления (высота – h+2)
После вращения (высота – h+1)
B
α (h)
γ (h-1)
0
β (h-1)
A
0
Высота поддерева уменьшилась, надо продолжать двигаться к корню

УСТРАНЕНИЕ РАЗБАЛАНСИРОВАННОСТИ – ВРАЩЕНИЕ (тип 2)
До удаления (высота – h+2)
После удаления (высота – h+2)

УСТРАНЕНИЕ РАЗБАЛАНСИРОВАННОСТИ – ВРАЩЕНИЕ (тип 2)(продолжение)
После удаления (высота – h+2)
После вращения (высота – h+2)
Высота поддерева не изменилась, можно прекращать работу

До удаления (высота – h+2)
-2
1
После удаления (высота – h+2)
УСТРАНЕНИЕ РАЗБАЛАНСИРОВАННОСТИ – ДВОЙНОЕ ВРАЩЕНИЕ

Устранение разбалансированности – двойное вращение (продолжение)
A
α (h-1)
δ (h-1)
-2
β
B
?
После удаления (высота – h+2)
После двойного вращения (высота – h+1)
С
γ
С
0
B
?
A
?
α (h-1)
β
γ
δ (h-1)
1
Высота поддерева уменьшилась, надо продолжать двигаться к корню

СИЛЬНО ВЕТВЯЩИЕСЯ ДЕРЕВЬЯ
Сильно ветвящееся дерево ((a,b)-дерево) – поисковое дерево, все ветви которого имеют одинаковую высоту, а каждая вершина, кроме листьев, имеет от a до b сыновей.
Мы будем рассматривать (2, 4)-деревья.

Типы вершин в (2, 4)-дереве
справочные (внутренние) вершины
key[i] – максимальное значение ключа в поддереве, начинающемся с son[i];
ключи упорядочены;
количество ключей на единицу меньше количества сыновей
информационные вершины (листья)
Info

Пример (2, 4)-дерева
2
7
14
10
18
45
48
67
64
71
75
84
88

Удачный поиск в (2, 4)-дереве
Поиск значения 45
2
7
14
10
18
45
48
67
64
71
75
84
88

Неудачный поиск в (2, 4)-дереве
Неудачный поиск значения 44
2
7
14
10
18
45
48
67
64
71
75
84
88

Добавление нового элемента
Выполняем поиск, определяя отца добавляемого элемента (вершину f)
Если f имеет двух или трёх сыновей, увеличиваем количество сыновей f и добавляем новый элемент в качестве сына
2
10
7
2
7
5
10

Добавление нового элемента (продолжение)
Если f имеет четырёх сыновей, предварительно расщепляем её на две вершины f1 и f2 с двумя сыновьями каждая:
Добавляем новый узел в качестве сына f1 либо f2:
14
45
18
48
45
46
48

Добавление нового элемента (продолжение)
Если f была корнем, создаём новый корень, сыновьями которого будут f1 и f2:
В противном случае поднимаемся на уровень вверх и добавляем нового сына отцу вершины f
Расщепление полезно проводить в процессе поиска!

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

Удаление значения из (2, 4)-дерева
Пусть f – отец удаляемого листа
Если у f было 3 или 4 сына, уменьшаем количество сыновей:
Если f – корень с двумя сыновьями-листьями, удаляем f. Корнем становится оставшийся сын:
2
10
2

Удаление значения из (2, 4)-дерева (продолжение)
Пусть t – левый или правый брат вершины f с наибольшим числом сыновей.
Если у t 3 или 4 сына, передаём одного из сыновей вершине f:
24

Удаление значения из (2, 4)-дерева (продолжение)
Если у t 2 сына, передаём оставшегося сына вершины f вершине t, удаляем f и переходим на уровень выше :

КРАСНО-ЧЁРНЫЕ ДЕРЕВЬЯ
Красно-чёрное дерево (Red-Black-Tree, RB-Tree) — это одно из самобалансирующихся двоичных деревьев поиска, гарантирующих логарифмический рост высоты дерева от числа узлов и быстро выполняющее основные операции дерева поиска: добавление, удаление и поиск узла.

Свойства красно-чёрного дерева
Каждый узел покрашен либо в чёрный, либо в красный цвет.
Листьями объявляются NIL-узлы (т.е. "виртуальные" узлы, наследники узлов, которые обычно называют листьями). Листья покрашены в чёрный цвет.
Если узел красный, то оба его потомка черны.
На всех ветвях дерева, ведущих от его корня к листьям, число черных узлов одинаково. Эта величина называется чёрной высотой дерева.

Оценки высоты и количества вершин
Если h — чёрная высота дерева, то количество листьев не менее 2h − 1.
Если h — высота дерева, то количество листьев не менее 2(h − 1) / 2.
Если количество листьев N, высота дерева не больше 2log2N + 1, следовательно, максимальная высота растёт как Θ(logN).

Пример чёрно-красного дерева
41
58
87
38
99
91
98
78
50
32

Вставка нового элемента в красно-чёрное дерево
Новый элемент вставляется на место фиктивного листа и красится в красный цвет.
Если отец добавленного элемента – чёрный, завершаем работу.
38
32
38
32
30
После вставки элемента 30
До вставки элемента 30

Вставка нового элемента в красно-чёрное дерево (продолжение)
Если отец добавленного элемента – красный, смотрим на цвет дяди.
Если дядя – красного цвета, перекрашиваем отца, дядю, деда и продолжаем проверку свойства 3 для деда
После вставки элемента 30
До вставки элемента 30

Вставка нового элемента в красно-чёрное дерево (продолжение)
После перекраски, нужно продолжать проверку для вершины 45
После вставки элемента 30
В самом конце мы красим в чёрный цвет корень дерева. Если он был красным, то при этом увеличивается чёрная высота дерева.

Вставка нового элемента в красно-чёрное дерево (продолжение)
Если дядя – чёрного цвета, выполняем вращение ли двойное вращение (аналогично АВЛ – деревьям) и останавливаемся
После вставки элемента 30
До вставки элемента 30

Вставка нового элемента в красно-чёрное дерево (продолжение)
Если дядя – чёрного цвета, выполняем вращение или двойное вращение (аналогично АВЛ – деревьям) с перекраской и останавливаемся
После вращения и перекраски
После вставки элемента 30

Удаление элемента из красно-чёрного дерева
Если удаляемый элемент – красный, свойства красно-чёрного дерева на нарушаются, можно завершить работу.
После удаления элемента 30
До удаления элемента 30

Удаление элемента из красно-чёрного дерева
Если удаляемый элемент – чёрный, свойство 4 может нарушиться.
После удаления элемента 30
До удаления элемента 30