yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->Листинг 5.3. Удаление наименьшего элемента

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

Листинг 5.3. Удаление наименьшего элемента

function DELETEMIN ( var A: SET ): elementtype;

begin

if A↑.leftchild = nil then begin

{ А указывает на наименьший элемент }

DELETEMIN:= A↑.element;

А:= A↑.rightchild

{ замена узла, указанного А, его правым сыном }

end

else { узел, указанный А, имеет левого сына }

DELETEMIN:= DELETEMIN(A↑.leftchiId)

end; { DELETEMIN }

 

Листинг 5.4. Удаление элемента из дерева двоичного поиска ?

procedure DELETE ( x: elementtype; var A: SET ) ;

begin

if A <> nil then

if x < A↑.element then

DELETE(x,   A↑.leftchild)

else if x > A↑.element then

DELETE(x,   A↑.rightchild)

else if   (A↑.leftchild= nil)   and   (A↑.rightchild= nil)   then

A:= nil  {  удаление листа,   содержащего x  }

else  if A↑.leftchild = nil  then

A:=  A↑.rightchild

else if A↑.rightchild = nil then

A:= A↑.leftchild

else  { у узла есть  оба сына  }

A↑.element:= DELETEMIN(A↑.rightchild)

end;    {   DELETE   }

Пример 5.1. Предположим, надо удалить элемент 10 из дерева, показанного на рис. 5.1,а. В данном случае первым исполняемым оператором в процедуре DELETE будет вызов функции DELETEMIN с аргументом-указателем на узел 14. Этот указатель — значение поля rightchild корня. Результатом этого вызова будет еще один вызов той же функции DELETEMIN. В этом случае ее аргументом будет указатель на узел 12, который находится в поле leftchild узла 14. Узел 12 не имеет левого сына, поэтому функция возвращает элемент 12 и устанавливает указатель узла 14 на левого сына в состояние nil. Затем процедура DELETE берет значение 12, возвращенное функцией DELETEMIN, и заменяет им элемент 10. Результирующее дерево показано на рис. 5.2.

 

43