yandex rtb 1
ГоловнаЗворотній зв'язок
yande share

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

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

Сделаем набросок функции deletel, которая по заданному указателю на узел node и элементу х удаляет лист, являющийся потомком узла node и содержащий значение х, если, конечно, такой лист существует1. Если после удаления узел node имеет только одного сына, то функция deletel возвращает значение true, а если узел node имеет двух или трех сыновей, то возвращает значение false. Эскиз этой функции показан в следующем листинге.

Листинг 5 .12. Рекурсивная процедура удаления

function deletel ( node: ↑twothreenode; x: elementtype ): boolean;

var

only one: boolean;

{ содержит значение, возвращаемое по вызову deletel }

begin

deletel:= false;

if сыновья node являются листьями then begin

if х принадлежит этим листьям then begin

удаление х;

смещение сыновей node, которые были справа от х,

на одну позицию влево;

if node имеет только одного сына then

deletel:= true

end

end

else begin { node находится на втором уровне или выше }

определяется, какой сын узла node может

иметь среди своих потомков х;

onlyone:= deletel(w, х); {в зависимости от ситуации w

обозначает node↑.firstchild, node↑.secondchild или

node↑. thirdchild }

if onlyone then begin { просмотр сыновей node }

if w — первый сын node then

if у — 2-й сын node, имеющий 3-х сыновей then

1-й сын у делается 2-м сыном w;

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

сын w делается 1-м сыном у;

удаление w из множества сыновей узла node;

if node имеет только одного сына then

deletel:= true

end;

if w — второй сын node then

if у — 1-й сын node, имеющий 3-х сыновей then

3-й сын у делается 1-м сыном w

else { у имеет двух сыновей }

if существует z3-й сын node,

имеющий 3-х сыновей then

1-й сын z делается 2-м сыном w

else begin

{ у node нет сыновей, имеющих трех детей }

сын w делается 3-м сыном у;

удаление  w из множества сыновей узла node;

if node имеет только одного сына then

delete1:=  true

end;

if w — третий сын node then

if у — 2-й сын node,   имеющий 3-х сыновей then

3-й сын у делается 1-м сыном w,

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

сын  w делается 3-м сыном у;

удаление  w из множества сыновей узла node;

end

end

end

end;   {   delete1   }

Мы оставляем для читателя детализацию кода функции delete1. В качестве еще одного упражнения предлагаем написать процедуру DELETE(S, x), которая проверяла бы, не является ли множество S пустым или состоящим из одного элемента, и если это не так, то вызывала бы функцию deletel (S, x). Если delete1 возвратит значение true, то процедура должна удалить корень (узел, на который указывает S) и сделать S указателем на единственного (в данной ситуации) сына корня.

 

76