yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->Листинг 5.9. Процедура вставки в 2-3 дерево

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

Листинг 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 дерева, чьи листья содержат элементы исходного множества.

Листинг 5.11. Оператор INSERT для множеств, представленных посредством 2-3 деревьев

procedure INSERT ( x: elementtype; var S: SET );

var

pback: ↑twothreenode;  {указатель на узел, возвращенный insertl}

lowback: real; {наименьшее (low) значение в поддереве pback}

saveS: SET; {для временного хранения копии указателя S}

begin

{ здесь надо вставить процедуру проверки, которая выясняет, является ли S пустым деревом или имеет только один узел, и осуществляет для этих ситуаций вставку }

insertl(S, x, pback, lowback);

if pback <> nil then begin

{ создание нового корня, на его сыновей указывают S и pback }

saveS:= S;

new(S);

S↑.firstchild:=  saveS;

S↑.secondchi1d:= pback;

S↑ .lowofsecond:=  lowback;

S↑.thirdchild:= nil;

end

end;    {   INSERT   }

 

75