Основы программирования. Динамические массивы. Списки. Ассоциативные массивы. Деревья. Хеш-таблицы - 40 стр.

UptoLike

ВУЗ: 

ЮФУ | Ростов-на-Дону

Составители: 

Рубрика: 

42
дерева. Следовательно, для его удаления достаточно присвоить указателю, ранее
указывавшему на него, адрес его левого поддерева.
Почему приведенный алгоритм корректен? Для этого достаточно показать,
что после его работы дерево остается БДП. Это очевидно, поскольку если пред-
ставлять элементы дерева как упорядоченную последовательность, то данный ал-
горитм для удаления элемента переписывает
в него значение предыдущего эле-
мента, после чего удаляет этот предыдущий. Поскольку удаление предыдущего
выполняется по алгоритму случая а) или б), дерево остается БДП.
Данное доказательство дает нам возможность привести еще один, симмет-
ричный предыдущему, алгоритм удаления: чтобы удалить элемент с двумя подде-
ревьями, достаточно найти самый левый элемент в его
правом поддереве (значе-
ние которого непосредственно следует за данным), и перед удалением переписать
его значение в исходный.
Приведем рекурсивную процедуру удаления элемента из БДП.
procedure Delete(x: DataType; var r: PNode);
procedure FindAndDelMostRight(var p: PNode);
var v: PNode;
begin
if p.right<>nil then
FindAndDelMostRight(p.right)
else
begin
r.data:=p.data;
v:=p;
p:=p.left;
Dispose(v);
end;
end;
var v: PNode;
begin
if r=nil then
exit;
if
x<r.data then
Delete(x,r.left)
else if x>r.data then
Delete(x,r.right)
else if (r.left=nil) and (r.right=nil) then // слу-
чай а)
begin
Dispose(r);
r:=nil;
end

Страницы