Модели и структуры данных



         

Сбалансированные деревья - часть 8


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

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

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

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

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

    _Начало . Del. 1. Поиск последнего элемента в правом поддереве _Если . RPTR(r) <> nil { элемент не найден } _то .: r=RPTR(r); вызов процедуры Del; _если .


    Содержание  Назад  Вперед