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

АЛГОРИТМ ПРОЦЕДУРЫ 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;