Сильноветвящиеся деревья
Цель: изучение вниз-направленных деревьев 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.
Итак, на сегодняшнем занятии мы рассмотрели
сильноветвящиеся деревья. |
