Алгоритм процедуры Delete

Дано: сбалансированное бинарное дерево с корнем 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 - т.к. эта процедура рекурсивная, то производится возврат в место предыдущего вызова, либо в главную программу.