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

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

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

[pic 1]

[pic 2][pic 3]

[pic 4][pic 5]

[pic 6][pic 7]

[pic 8][pic 9][pic 10][pic 11][pic 12][pic 13][pic 14][pic 15]

[pic 16][pic 17][pic 18][pic 19][pic 20][pic 21]

[pic 22][pic 23][pic 24][pic 25][pic 26][pic 27]

Ситуация 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                                    {удаляемая вершина найдена}