АЛГОРИТМ ПРОЦЕДУРЫ Del.

Дано: указатель - r на элемент дерева с двумя поддеревьями.

Алгоритм производит удаление этого элемента, с сохранением связей с нижележащими элементами, и вызов процедуры балансировки.

Используется вспомогательный указатель q, описанный в процедуре Delete.

_Начало . Del.

1. Поиск последнего элемента в правом поддереве

_Если . RPTR(r) <> nil { элемент не найден }

_то .: r=RPTR(r);

вызов процедуры Del;

_если . h=true _то . вызов процедуры Balance_R;

перейти к п.2;

_иначе .: KEY(q)=KEY(r); r=RPTR(r); h=true;

2. Выход.

_Конец . Del;

ОПИСАНИЕ РАБОТЫ:

· П.1 - производится рекурсивный поиск самого правого элемента в поддереве. Если элемент найден, то он ставится на место удаленного элемента, устанавливается флаг удаления, и осуществляется выход. Если установлен флаг удаления элемента, то вызывается процедура балансировки.

· П.5 - т.к. эта процедура рекурсивная, то производится возврат в место предыдущего вызова, либо в вызывающую процедуру (Delete).