yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->Листинг 5.8. Объявление типов данных узлов 2-3 дерева

Алгоритмы и структуры данных

Листинг 5.8. Объявление типов данных узлов 2-3 дерева

type

elementtype = record

key: real;

{ объявление других полей, если необходимо }

end;

nodetype = (leaf, interior);

{ объявление типа узла, содержащее поля leaf (лист) и

interior (внутренний узел) }

twothreenode = record

case kind: nodetype of

leaf: (element: elementtype) ;

interior:(firstchild, secondchild, thirdchild:

↑twothreenode;   lowofsecond, lowofthird: real)

end;

SET = ↑twothreenode;

Реализация оператора INSERT

Детали реализации операторов для 2-3 деревьев несколько запутанны, но принципы просты. Поэтому подробно мы опишем только оператор вставки. Реализации операторов удаления, проверки на принадлежность множеству и других подобны реализации оператора INSERT, а оператор нахождения минимального элемента выполняется просто спуском по самому левому пути дерева. Оператор INSERT реализован как основная программа, вызывающая корень дерева и процедуру insertl, которая рекурсивно вызывается для узлов дерева. Для определенности мы предполагаем, что 2-3 дерево не является пустым деревом и содержит более одного узла.

Последние два случая, когда дерево пустое или содержит только один узел, реализуются простой последовательностью шагов, которые читатель может написать самостоятельно.

Функция insertl должна возвращать как указатель на новый узел, если он будет создан, так и ключ наименьшего элемента, находящегося ниже нового узла. В языке Pascal механизм создания такой функции достаточно сложен, поэтому мы объявили insertl как процедуру, которая присваивает значения параметрам pnew и low при создании нового узла. В листинге 5.9 показан эскиз этой процедуры, а ее полный код приведен в листинге 5.10.

Листинг 5.9. Процедура вставки в 2-3 дерево

procedure insertl ( node: ↑twothreenode; x: elementtype;

{ элемент x должен быть вставлен в поддерево с корнем node }

var pnew: ↑twothreenode; { указатель на новый элемент }

var low: real); { наименьший элемент в поддереве с корнем,

на который указывает pnew }

begin

pnew:= nil;

if node является листом then begin

if x не является элементом, содержащимся в node then begin

создание нового узла, указанного pnew;

сделать х элементом, содержащимся в новом узле;

low:= x.key

end

end

else begin { node является внутренним узлом }

выбрать wсына узла node;

insertl(w, x, pback, lowback);

if pback <> nil then begin

вставка указателя pback среди детей узла node,

расположенных справа от w;

if node имеет 4-х сыновей then begin

создание нового узла, указанного pnew;

создание нового узла для 3-го и 4-го сыновей node;

задание значений полям lowofsecond и lowoftnird

для узла node и нового узла;

задание полю low наименьшего ключа

среди детей нового узла

end

end

end

end; { insertl }

 

Листинг 5.10. Полный код процедуры insert1

procedure insertl ( node: ↑twothreenode; ,   x: elementtype;

var pnew: ↑twothreenode; var low: real );

var

pback: ↑twothreenode;

lowback: real;

child: 1..3; { указывает на следующего "обрабатываемого"

сына node (ср. с w в листинге 5.9) }

w: ↑twothreenode; { указатель на сына }

begin

pnew:= nil;

if node↑. .kind = leaf then begin

if node↑.element.key <> x.key then begin

{ создание нового листа, содержащего х и

            "возврат" этого листа }

new(pnew, leaf) ;

if node↑.element.key < x.key then

{ запись x в новый узел }

begin pnew↑.element:= x; low: = x.key end

else begin

pnew↑.element:= node↑.element;

node↑.element:= x;

low-.= pnew↑. element, key

end

end

end

else begin { node является внутренним узлом }

{ выбор следующего сына node }

if x.key < node↑.lowofsecond then

begin child:= 1; w:= node↑.firstchild end

else if{node↑.thirdchild = nil) or

(x.key < node↑.lowofsecond) then begin

{ x во втором поддереве }

child:= 2;

w.= node↑. secondchild

end

else begin { x в третьем поддереве }

child:= 3;

w: = node↑.thirdchild

end;

insertl(w, x, pback, lowback); if pback <> nil then

{ надо вставить нового сына node }

if nodeT.thirdchild = nil then

{ node имеет только двух сыновей }

if child = 2 then begin

node↑.thirdchild:= pback;

node↑.lowofthird:= lowback ,    

end

else begin { child = 1 }

node↑. thirdchild:= node↑.secondchild;

node↑.lowofthird:= node↑. lowofsecond;

node↑.secondchild:= pback;

node↑. lowofsecond:= lowback

end

else begin { node уже имеет трех сыновей }

new(pnew, interior) ;

if child = 3 then begin

{pback и 3-й сын становятся сыновьями нового узла }

pnew↑.firstchild:= node↑.thirdchild;

pnew↑.secondchild:= pback;

pnew↑. thirdchild:= nil;

pnew↑.lowofsecond:= lowback;

{ lowofthird для pnew неопределен }

low:= node↑.lowofthird;

node↑. thirdchild: = nil

end

else begin

{child ≤ 2; перемещение 3-го сына node к pnew}

pnew↑.secondchild:= nodet.thirdchild;

pnew↑.lowofsecond:= nodet. lowofthird;

pnew↑.thirdchild:= nil;

node↑.thirdchild:= nil

end;

if child = 2 then begin

{pback становится 1-м сыном pnew }

pnew↑.firstchild:= pback;

low: =  lowback

end;

if child =  1  then begin

{  2-й сын node перемещается к pnew,

pback становится 2-м сыном node  }

pnew↑.firstchild:= node↑.secondchild;

low: =  nodet. lon/ofsecond;

node↑.secondchild:= pback;

node↑. lowof second: =  lowback

end

end

end

end;   {   insertl   }

Теперь можно написать процедуру INSERT, которая вызывает insertl. Если insert 1 "возвращает" новый узел, тогда INSERT должна создать новый корень дерева. Код процедуры INSERT представлен в листинге 5.11. Здесь мы считаем, что тип SET — это тип ↑twothreenode, т.е. указатель на корень 2-3 дерева, чьи листья содержат элементы исходного множества.

 

48