НОВОСТИ
Новости сайта
О САЙТЕ
Содержание сайта
БИБЛИОТЕКА
Структуры и алгоритмы
ОБРАТНАЯ СВЯЗЬ
Связь с автором
Структуры и алгоритмы

Сильноветвящиеся деревья

Цель: изучение вниз-направленных деревьев 2-3-4 и красно - черных деревьев.

На прошлых занятиях были рассмотрены деревья, которые имели всего лишь 2 ветви. На сегодняшнем занятии рассмотрим деревья, которые будут иметь много ветвей. Такие деревья называются сильноветвящимися.

Сильноветвящиеся деревья могут содержать в своих узлах более, чем один ключ.

Разрешим тройные и четверные узлы, которые могут содержать два или три ключа соответственно. У тройного узла есть 3 выходящие из него ветви, одна ветвь для всех записей ключи которых меньше чем оба его ключа, одна для всех записей, которые больше либо равны первому ключу, но меньше второго , и одна для всех записей, которые больше его ключей или равны второму ключу. Аналогично, 4-ной узел имеет 4 ветви выходящие из него; по одной для каждого интервала определенного его 3 ключами. (Узлы в обычном бинарном дереве можно таким образом называть двойными узлами: один ключ, две ветви.)

stree001.gif (1692 bytes)

Дерево содержащее двойные, тройные и четверные узлы называется деревом 2-3-4.

stree002.gif (1966 bytes)

Чтобы вставить новый узел в 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-ным узлом - это расщеплять любой четверной узел, попадающийся нам пока мы просматриваем наше дерево сверху до низу.

stree003.gif (1594 bytes)

Расщепление 4-ных узлов.

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

str001.gif (1226 bytes)
str002.gif (1461 bytes)
str003.gif (1507 bytes)
str004.gif (1621 bytes)
str005.gif (1712 bytes)
str006.gif (1726 bytes)
str007.gif (1912 bytes)
str008.gif (2058 bytes)

Эта операция "расщепления" работает благодаря тому, что мы передвигаем не только ключи, но и указатели. Так 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;

stree006.gif (9744 bytes)

Последний метод реализации деревьев имеет очевидный недостаток. Для хранения множества связанных списков расходуется значительный объем памяти.
Поэтому рассмотрим еще один вариант представления сильно - ветвящихся деревьев - это красно - черные деревья.

Красно - черные деревья

Мы можем представить 2-3-4 деревья в виде бинарных деревьев (состоящих лишь из 2-ный узлов) используя лишь один дополнительный бит на узел. Идея состоит в том, чтобы представить 4-ные и 3-ные узлы как 2-ные соединенные между собой красными звеньями; напротив, черные же звенья соединяют узлы 2-3-4 дерева. Представление довольно простое: 4-ной узел - это 3 двойных соединенных красными звеньями, а 3-ной - это 2 двойных, также соединенных красными звеньями.

stree007.gif (1460 bytes)

Красно-черное представление 3-ных и 4-ных узлов.

Давайте представим последнее 2-3-4 дерево в виде красно - черного дерева.

stree008.gif (4174 bytes)

Одно из самых замечательных свойств красно-черных деревьев, это то, что процедура поиска treesearch для них не отличается от обычной процедуры для бинарных деревьев (за исключением ситуации с дублирующимися ключами). Мы реализуем цвет звена добавив к нему поле red, принимающее значение true если звено красное, и false в противоположном случае. Процедура поиска treesearch просто никогда не проверяет это поле. Таким образом, все наши "улучшения" не вызвали каких-либо дополнительных затрат времени в процедуре поиска. Так, как каждый ключ вставляется только раз, а ищется много раз, то отсюда следует, что по крайней мере мы добились улучшения времени поиска.

Добавление узла в красно - черное дерево.

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

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

stree009.gif (3282 bytes)

Расщепление 4-ного узла переключением цвета.

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

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

stree010.gif (5141 bytes)

Расщепление 4-ного узла переключением цвета; требуется вращение (двойной правый поворот и одиночный правый поворот)

stree011.gif (3222 bytes)

Расщепление узла в красно - черном дереве

stree012.gif (7581 bytes)

Вставка узлов в дерево

Напишем программу, которая демонстрирует вставку и поиск в красно - черном дереве.

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.

Итак, на сегодняшнем занятии мы рассмотрели сильноветвящиеся деревья.

Почта /// Структуры и алгоритмы