Сильноветвящиеся деревья
Цель: изучение вниз-направленных деревьев 2-3-4 и красно - черных деревьев.
На прошлых занятиях были рассмотрены деревья, которые имели всего лишь 2 ветви. На сегодняшнем занятии рассмотрим деревья, которые будут иметь много ветвей. Такие деревья называются сильноветвящимися.
Сильноветвящиеся деревья могут содержать в своих узлах более, чем один ключ.
Разрешим тройные и четверные узлы, которые могут содержать два или три ключа соответственно. У тройного узла есть 3 выходящие из него ветви, одна ветвь для всех записей ключи которых меньше чем оба его ключа, одна для всех записей, которые больше либо равны первому ключу, но меньше второго , и одна для всех записей, которые больше его ключей или равны второму ключу. Аналогично, 4-ной узел имеет 4 ветви выходящие из него; по одной для каждого интервала определенного его 3 ключами. (Узлы в обычном бинарном дереве можно таким образом называть двойными узлами: один ключ, две ветви.)
 |
Дерево содержащее двойные, тройные и четверные узлы называется деревом 2-3-4.
|
Чтобы вставить новый узел в 2-3-4 дерево нужно произвести поиск и затем "нацепить" наш узел. Легко видно что делать если узел, в котором обрывается наш поиск, двойной: просто превращаем его в тройной. Например, 240 могли бы добавить в дерево изображенное на рисунке просто добавив его (и другую ветвь) к узлу содержащему 190. Аналогично 3-ной узел можно легко превратить в 4-ной. Но как нам быть если новый узел должен быть вставлен в 4-ной узел? Например, как нам вставить 70 в дерево рисунка? Одна из возможностей - нацепить 70 как новый самый левый узел узла содержащего 80, 90 и 140. Однако, есть более лучшее решение этой проблемы: сперва расщепим 4-ной узел в два двойных и передадим один из его ключей его родителями. Так узел содержащий 80, 90 и 140 делится на два двойных (один содержащий 80, другой содержащий 140) и его центральный ключ 90 передается в 3-ной узел содержащий 50 и 180, превращая его в 4-ной узел. После таких махинаций у нас освобождается место для 70 в узле содержащем 80.
Но что если нам нужно расщепить 4-ной узел, родитель которого тоже является 4-ным узлом? Один из способов - расщепить также и его родителя, и продолжать так до самого верха. Однако более легкий путь гарантирования того, что родитель расщепляемого узла никогда не будет 4-ным узлом - это расщеплять любой четверной узел, попадающийся нам пока мы просматриваем наше дерево сверху до низу.
 |
Расщепление 4-ных узлов.
Вышеприведенный пример показывает, что мы легко можем вставлять новые узлы просматривая дерево сверху вниз и расщепляя 4-ные узлы по мере продвижения вниз. В частности, как показано на рисунке, каждый раз как мы наталкиваемся на 2-ной узел соединенный с 4-ным, мы преобразуем его в 3-ной узел соединенным с двумя 2-ными, и каждый как мы встречаем 3-ной узел соединенный с 4-ным, мы преобразуем его в 4-ной узел соединенным с двумя 2-ными.
 |
 |
 |
 |
 |
 |
 |
 |
Эта операция "расщепления" работает благодаря тому, что мы передвигаем не только ключи, но и указатели. Так 2 двойных узла имеют тоже количество указателей (четыре), что и один 4-ной узел, благодаря чему расщепление можно выполнить не переиначивая того, что находится ниже узла расщепления. Тройной же узел не может быть преобразован в четверной простым добавлением в него ключа: нам необходимо будет также добавить и указатель (в этом случае этот указатель обеспечивается из расщепляемого узла). Критическая точка этого метода - это то, что все трансформации чисто "локальные": не требуется проверять или изменять никакие части дерева кроме тех, что изображены на рисунке. Каждая из таких трансформаций передает вверх один из ключей 4-ного узла его родителю по дереву и переставляет указатели. Заметьте, что нам нет нужды волноваться, что родитель узла окажется 4-ным узлом так, как трансформация гарантирует, что любой узел в который мы добрались -не 4-ной. В частности, когда мы достигнем дна дерева, мы будем иметь дело в 2-ным или 3-ным узлом, и потому можем вставлять в него напрямую. Как только корень дерева становится 4-ным узлом, мы делим его. Это приводит к тому, что наше дерево "подрастает" на уровень. Только превращение корня дерева в 4-ной узел может заставить наше дерево подрасти на один уровень.
Алгоритм набросанный выше показывает как производить поиск в 2-3-4 деревьях; в следствии того, что 4-ный узлы расщепляются по мере того, как мы продвигаемся сверху вниз, деревья были названы вниз-направленные 2-3-4 деревья. Что самое интересное во всем этом - это то, что несмотря на то, что мы вовсе не волновались о том, чтобы сбалансировать это дерево, оно получилось идеально сбалансированным.
При рассмотрении сильноветвящихся деревьев мы ограничимся только рассмотрением деревьев 2-3-4, т.к. любое сильноветвящееся дерево можно свести к дереву 2-3-4.
Сильноветвящееся дерево можно представить с использованием связных списков для запоминания указателей сыновей каждой вершины.
Type
P_child = ^child;
P_node = ^node;
Child = record
Next_child: p_child;
Father: p_node;
End;
Node = record
Key: integer;
son : child;
end;
 |
Последний метод реализации деревьев
имеет очевидный недостаток. Для хранения
множества связанных списков расходуется
значительный объем памяти.
Поэтому рассмотрим еще один вариант
представления сильно - ветвящихся деревьев
- это красно - черные деревья.
Красно - черные деревья
Мы можем представить 2-3-4 деревья в виде бинарных деревьев (состоящих лишь из 2-ный узлов) используя лишь один дополнительный бит на узел. Идея состоит в том, чтобы представить 4-ные и 3-ные узлы как 2-ные соединенные между собой красными звеньями; напротив, черные же звенья соединяют узлы 2-3-4 дерева. Представление довольно простое: 4-ной узел - это 3 двойных соединенных красными звеньями, а 3-ной - это 2 двойных, также соединенных красными звеньями.
 |
Красно-черное представление 3-ных и 4-ных узлов.
Давайте представим последнее 2-3-4 дерево в виде красно - черного дерева.
 |
Одно из самых замечательных свойств красно-черных деревьев, это то, что процедура поиска treesearch для них не отличается от обычной процедуры для бинарных деревьев (за исключением ситуации с дублирующимися ключами). Мы реализуем цвет звена добавив к нему поле red, принимающее значение true если звено красное, и false в противоположном случае. Процедура поиска treesearch просто никогда не проверяет это поле. Таким образом, все наши "улучшения" не вызвали каких-либо дополнительных затрат времени в процедуре поиска. Так, как каждый ключ вставляется только раз, а ищется много раз, то отсюда следует, что по крайней мере мы добились улучшения времени поиска.
Добавление узла в красно - черное дерево.
Добавление проходит по тому же алгоритму, что и для дерева 2-3-4. Мы ищем подходящий узел, а по пути поиска расщепляем все четверные узлы.
Преобразование необходимое когда мы встречаем 2-ной узел соединенный с 4-ным довольно простое, и такое же преобразование работает когда мы натыкаемся на 3-ной узел соединенный с 4-ным "справа", как показано на рисунке. Таким образом, расщепление начинается с того, что мы перекрашиваем X в красное, а детей X в черное.
 |
Расщепление 4-ного узла переключением цвета.
Однако мы пропустили две другие ситуации, которые могут возникнуть когда мы встречаем 3-ной узел соединенный с 4-ным не "справа.
В этом случае расщепление 4-ного узла приводит к тому, что у нас остается 2 красных звена подряд, эта ситуация незаконна, и должна быть поправлена.
|
Расщепление 4-ного узла переключением цвета; требуется вращение (двойной правый поворот и одиночный правый поворот)
 |
Расщепление узла в красно - черном дереве
Вставка узлов в дерево
Напишем программу, которая демонстрирует вставку и поиск в красно - черном дереве.
Program PoiskByTree;
type
rec=record
fio:string [40];
gr:string[4];
kurs:string[1];
end;
link=^l;
l=record
key:rec;
red:boolean;
l,r:link;
end;
Var
head, w: link;
k: rec;
st1: string;
f: file of rec;
Function rotate(v:rec;y:link):link;
var
c,gs:link;
begin
if v.fio[1]<y^.key.fio[1] then c:=y^.l else c:=y^.r;
if v.fio[1]<c^.key.fio[1] then
begin
gs:=c^.l; c^.l:=gs^.r; gs^.r:=c;
end else
begin
gs:=c^.r; c^.r:=gs^.l; gs^.l:=c;
end;
if v.fio[1]<y^.key.fio[1] then y^.l:=gs else y^.r:=gs;
rotate:=gs;
end;
Function split(v : rec; m,p,g,gg : link):link;{Перекрашивает}
begin
m^.red:=true; m^.l^.red:=false; m^.r^.red:=false;
if p^.red then
begin
g^.red:=true;
if (v.fio[1] < g^.key.fio[1]) <> (v.fio[1] < p^.key.fio[1]) then
p:=rotate(v,g);
m:=rotate(v,gg); m^.red:=false;
end;
head^.r^.red:=false;
split:=m;
end;
Function insert(v : rec; n : link):link;
var
q1,q2,p : link;
begin
p:=n; q1:=p;
repeat
q2:=q1; q1:=p;
p:=n;
if v.fio[1]<n^.key.fio[1] then n:=n^.l Else n:=n^.r;
if n^.l^.red And n^.r^.red then n:=split(v,n,p,q1,q2);
until n^.l=n;
New(n);
n^.key.fio:=v.fio;
n^.l:=n;
n^.r:=n;
if v.fio[1]<p^.key.fio[1] then p^.l:=n else p^.r:=n;
insert:=n;
n:=split(v,n,p,q1,q2);
End;
procedure search(st:string; x:link; var z:rec);
begin
while st<>x^.key.fio do
if st<x^.key.fio then x:=x^.l
else x:=x^.r;
z:=x^.key;
end;
begin
new(head);
assign(f,'d:\my.dat');
reset(f);
while not eof(f) do
begin
read(f,k);
w:=insert(k,head);
end;
readln(st1);
search(st1,head,k);
end.
Итак, на сегодняшнем занятии мы рассмотрели сильноветвящиеся деревья
