Дано: указатель - 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).