Дано: сбалансированное бинарное дерево с корнем ROOT. Поля: LPTR, RPTR, KEY (ключ), BAL (показатель сбалансированности), DATA (информация).
Задан: ключ - х, информация - INF.
Алгоритм находит удаляемый элемент и вызывает процедуры удаления и последующей балансировки бинарного дерева. Если элемент отсутствует в дереве, выдается соответствующее сообщение.
Переменная h используется как флаг, указывающий на то, что было произведено удаление элемента. P - текущий указатель при перемещении по дереву, q - вспомогательный указатель.
_Начало . Delete
1. Поиск удаляемого элемента
_Если . x < KEY(p)
_то .: p=LPTR(p);
Вызов Delete;
_если . h=true _то . Вызов Balance_L;
перейти к п.5
_Если . x > KEY(p)
_то .: p=RPTR(p);
Вызов Delete;
_если . h=true _то . вызов Balance_R;
перейти к п.5
_Если . p=nil
_то .: напечатать "Ключа в дереве нет!";
_конец .;
2. Удаление элемента : (если все предыдущие
условия не выполнены, то указатель указывает на
элемент, подлежащий удалению).
Удаляется элемент с одним поддеревом.
q=p; { вводим вспомогательный указатель }
_если . RPTR(q)=nil
_то .: p=LPTR(q);
h=true;
перейти к п.4;
_если . LPTR(q)=nil
_то .: p=RPTR(q);
h=true;
перейти к п.4;
3. Удаление элемента с двумя поддеревьями:
q=LPTR(q);
_если . h=true _то .: вызов Balance_L;
перейти к п.4
4. Напечатать "Узел удален из дерева".
5. Выход.
_Конец . Delete;
ОПИСАНИЕ РАБОТЫ АЛГОРИТМА:
· П.1 - осуществляет поиск удаляемого элемента с помощью рекурсивных вызовов процедуры Delete (т.е. - самой себя). При этом в стеке сохраняется весь путь поиска. Если было произведено удаление элемента, то производится вызов соответствующей процедуры балансировки. Если элемент с заданным ключом не найден, то выводится соответствующее сообщение.
· П.2 - производится удаление элемента с одной ветвью простым переносом указателя. Устанавливается флаг удаления элемента.
· П.3 - производится вызов процедуры Del, производящей удаление элемента с двумя поддеревьями.
· П.5 - т.к. эта процедура рекурсивная, то производится возврат в место предыдущего вызова, либо в главную программу.