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

       

Алгоритм


Рассмотрим алгоритм в котором  вместо удаляемого узла ставится  самый левый узел правого  поддерева. Удалим узел  с номером 150, тогда на его место станет элемент под номером 152, т.к. он  является самым  левым из правого поддерева.

Введем  следующие обозначения:

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

Q - указатель  отстающий от Р на один шаг

V - указатель на элемент, который будет замещать удаляемый узел

T - указатель, отстает от V на один шаг

S - указатель,  опережает V на один шаг

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

(Псевдокод)

Q=nil

 P=Tree

 While (P<>nil)and(K(P)<>key)do {поиск узла с нужным ключем}



   If key<K(P) then P=Left(P)

     Else P=Right(P)

   EndIf

 EndWhile

 If P=nil then "Ключ не найден" {проверка если такого элемента нет}

                Return          {выход}

 EndIf

 If Left(P)=nil then V=Right(P) {если левая ссылка равна nil

   Else

     If Right(P)=nil then V=Left(P)

       Else

         GetNode(P)

         T=P

         V=Right(P) S = Left(V)

 While S <> nil  {поиск самого }

   T = V         {левого эл-нта}

   V = S     {правого поддерева}

   S = Left(V)

 EndWhile

 If T <> P then

   "V-не сын"

   Left(T) = Right(V)

   Right(V)= Right(P)

 EndIf

 Left(V) = Left(P)

 If Q = nil then

   "p - корень"

   Tree = V

   Return

 EndIf

       If P = Left(Q) then

         Left(Q) = V

       Else

         Right(Q)= V

       EndIf

     EndIf

   EndIf

 FreeNode(P)

Return

Иллюстрация процесса удаления узла 150, в соответствии с вышеприведенным алгоритмом (красным цветом выделены новые связи в дереве).

Конечный вариант дерева после удаления

 



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