Структуры и алгоритмы обработки данных

       

Процедура удаления элемента из бинарного дерева


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

1) удаляемый узел является листом, в этом случае он просто удаляется, не нарушая этим упорядоченность дерева ;

2) если удаляемый узел имеет только одного сына, то сын перемещается на место удаляемого отца ;

4) если у удаляемого узла 2 сына. В этом случае на место удаляемого отца помещается либо его предшественник в симметричном обходе (обход слева направо), либо его последователь.

Разработаем алгоритм для 3-его случая (вершина-узел имеет 2-х сыновей), вместо удаляемого узла поставим его приемника в симметричном обходе. Предшественником удаляемого узла 12 является самый правый узел левого поддерева - узел 11, а приемником или последователем при симметричном обходе (обход слева направо) является самый левый узел правого поддерева - узел 13.

Будем использовать следующие указатели :

p - рабочий указатель;

q - отстает на один шаг от p;

v - указывает приемника;

t - отстает от v на один шаг;

s - опережает v на один шаг.

1) Процедурой поиска элемента находим удаляемый элемент. Указатель p указывает на удаляемый элемент.

2) Установим указатель v на узел, который будет замещать удаляемый элемент.

      IF left (p)=nil

        THEN v=right (p)



        ELSE IF right (p)=nil

                   THEN v=left (p)

                   ELSE t=p

                            v=right (p)

                            s=left (v)

WHILE s<>nil

            t=v

            v=s

            s=left (v)

END WHILE

      IF t<>p

        THEN WRITE (v не является сыном p)

                  left (t)=right (v)

                 right (v)=right (p)

      END IF

left (v)=left (p)

       IF q=nil

         THEN WRITE (v корень)

                   tree=v

         RETURN

       END IF

       IF p=left (q)

         THEN left (q)=v

         ELSE right (q)=v

       END IF

    END IF

END IF

FREENODE (p) (процедура создает свободный узел, т.е. очищает ячейку памяти, в которой находится удаленный элемент)

RETURN



Содержание раздела