Удаление вершины из дерева поиска

Теперь рассмотрим удаление вершины из ДП. По сравнению с добавлением удаление реализуется более сложным алгоритмом, поскольку добавляемая вершина всегда является терминальной, а удаляться может ЛЮБАЯ, в том числе и нетерминальная. При этом может возникать несколько различных ситуаций.

Рассмотрим фрагмент ДП с целыми ключами.

Ситуация 1. Удаляемая вершина не имеет ни одного потомка, т.е. является терминальной. Удаление реализуется очень легко обнулением соответствующего указателя у родителя. Например, для удаления вершины с ключом 23 достаточно установить 25.left = nil.

Ситуация 2. Удаляемая вершина имеет только одного потомка. В этом случае удаляемая вершина вместе со своим потомком и родителем образуют фрагмент линейного списка. Удаление реализуется простым изменением указателя у родительского элемента. Например, для удаления вершины с ключом 20 достаточно установить 30.left = 20.right = 25

Ситуация 3. Пусть удаляемая вершина имеет двух потомков. Этот случай наиболее сложен, поскольку нельзя просто в родительской вершине изменить соответствующее ссылочное поле на адрес одного из потомков удаляемой вершины. Это может нарушить структуру дерева поиска. Например, замена вершины 30 на одного из ее непосредственных потомков 20 или 40 сразу нарушает структуру дерева поиска.

Существует специальное правило для определения вершины, которая должна заменить удаляемую. Это правило состоит из двух взаимоисключающих действий:

· либо войти в левое поддерево удаляемой вершины и в этом поддереве спустится как можно глубже, придерживаясь только правых потомков; это позволяет найти в дереве ближайшую меньшую вершину (например, для вершины 30 это будет вершина 25)

· либо войти в правое поддерево удаляемой вершины и спустится в нем как можно глубже придерживаясь только левых потомков; это позволяет найти ближайшую бОльшую вершину (например, для той же вершины 30 это будет вершина 33).

Перейдем к программной реализации процедуры удаления. Поскольку при удалении могут изменяться связи между внутренними вершинами дерева, удобно (но, конечно же, не обязательно) использовать рекурсивную реализацию. Основная процедура DeleteNodeрекурсивно вызывает сама себя для поиска удаляемой вершины. После нахождения удаляемой вершины процедура DeleteNodeопределяет число ее потомков. Если потомков не более одного, выполняется само удаление. Если потомков два, то вызывается вспомогательная рекурсивная процедура Changer для поиска вершины-заменителя.

Procedure DeleteNode ( var pCurrent : Tp);

Var pTemp : Tp;

Procedure Changer ( var p : Tp);

begin

{реализация рассматривается ниже}

end;

begin

if pCurrent = nil then “удаляемой вершины нет, ничего не делаем”

Else

if x < pCcurrent^.inf then DeleteNode ( pCcurrent^.left)

Else

if x > pCurrent^.inf then DeleteNode ( pCurrent^.right)

else{удаляемая вершина найдена}

begin

pTemp := pCurrent;

if pTemp^.right = nil then pCurrent := pTemp^.left

Else

ifpTemp^.left = nil then pCurrent := pTemp^.right

else {два потомка, ищем заменитель}

Changer ( pCurrent^.left); { а можно и pCurrent^.right }

Dispose( pTemp);

end;

end;

Схема процедуры Changer:

begin

if p^.right <> nil then Changer ( p^.right)

else {правое поддерево пустое, заменитель найден, делаем обмен}

Begin

pTemp^.inf := p^.inf; {заменяем информац. часть удаляемой вершины}

pTemp := p; {pTemp теперь определяет вершину-заменитель}

p := p^.left; {выходной параметр адресует левого потомка заменителя}

end;

end;

Дополнительный комментарий к процедурам. Подпрограмма Changer в качестве входного значения получает адрес левого (или правого) потомка удаляемой вершины и рекурсивно находит вершину-заменитель. После этого информационная часть удаляемой вершины заменяется содержимым вершины-заменителя, т.е. фактического удаления вершины не происходит. Это позволяет сохранить неизменными обе связи этой вершины с ее потомками. Удаление реализуется относительно вершины-заменителя, для чего ссылка pTemp после обмена устанавливается в адрес этой вершины. Кроме того, в самом конце процедуры Changer устанавливается новое значение выходного параметра p: оно равно адресу левого потомка вершины-заменителя. Это необходимо для правильного изменения адресной части вершины-родителя для вершины-заменителя. Само изменение происходит при отработке механизма возвратов из рекурсивных вызовов процедуры Changer. Когда все эти возвраты отработают, происходит возврат в основную процедуру DeleteNode, которая освобождает память, занимаемую вершиной-заменителем. Отметим, что приведенная выше реализация процедуры Changer ориентирована на поиск в левом поддереве удаляемой вершины и требует симметричного изменения для поиска заменителя в правом поддереве.

Для окончательного уяснения данного алгоритма настоятельно рекомендуем провести ручную пошаговую отработку его для небольшого примера, как это было сделано для значительно более простого алгоритма построения идеально сбалансированного дерева.