Понедельник, Июль 5th, 2010

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

Удаление узла дерева не должно нарушать упорядоченность дерева. При удалении возможны следующие варианты расположения узлов:
1)найденный узел является листом — он просто удаляется (рис.1);

2)найденный узел имеет только сына — в этом случае сын перемещается на место удаленного отца (рис.2);

3)у удаляемого отца два сына —  в  этом  случае  основная  трудность  состоит  в  удалении отца, поскольку в  удаляемую  вершину  входит одна  стрелка,  а выходит две.
В  этом случае  нужно найти  подходящее  звено  поддерева, которое можно было бы  вставить  на место удаляемого, причем  это  подходящее  звено должно просто  перемещаться. Такое  звено всегда  существует:
— это самый  правый элемент   левого   поддерева  (для  достижения  этого  звена необходимо  перейти в следующую вершину по  левой ветви, а  затем  переходить в  очередные вершины  только  по правой ветви  до тех  пор, пока очередная ссылка не будет равна nil);
— это самый  левый  элемент  правого  поддерева   (для  достижения  этого  звена необходимо перейти в следующую  вершину по правой ветви, а  затем  переходить  в очередные  вершины  только по левой ветви  до  тех  пор, пока  очередная такая ссылка не будет равна nil).
Очевидно, что   такие  подходящие  звенья  могут  иметь  не  более  одной ветви.
Алгоритм
Рассмотрим алгоритм в котором  вместо удаляемого узла ставится  самый левый узел правого  поддерева. Удалим узел  с номером 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, в соответствии с вышеприведенным алгоритмом (красным цветом выделены новые связи в дереве).

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

Задания

Страницы: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

Хорошие костыли в минске на прокат по приемлемым ценам

Категория: Учебники