Главная Промышленная автоматика.


элемент х может быть потомком только левого сына корня дepeвa. Аналогично, если X > г, то элемент х может быть потомком только Правого сына корня дерева.

12 18

Рис. 5.1. Два дерева двоичного поиска

Напишем простую рекурсивную функцию MEMBER(a;, реализующую тест на принадлежность элемента множеству. Предполоким, что элементы множества имеют пока не определенный тип данных, который назовем elementtype. Будем считать, что для этого типа данных определены отношения "<" и "=". Если это не так, то необходимо написать функции LT(a, 6) и EQ(a, Ъ) такие, что для любых элементов а и Ь типа elementtype функция LT(a, Ъ) будет принимать значение true тогда и только тогда, когда а "меньше" Б, а функция EQ(a. Ь) - когда а "равно или больше" Ь.

Тип данных nodetype узлов дерева, содержащих поле element для элементов множества и два поля leftchildvL rightchild указателей на левого и правого сыновей, определим с помощью следующего объявления:

type

nodetype = record

element: elementtype;

leftchild, rightchild: tnodetype

end;

Далее определим тип SET (Множество) как указатель на узел, который будет корнем дерева двоичного поиска при представлении множества:

type

set: tnodetype;

Теперь можно написать полный код функции MEMBER (листинг 5.1). Отметим, что, поскольку в данном случае SET и указатель на узел - синонимы, функция может вызывать сама себя для проведения поиска по поддереву, как если бы это поддерево представляло все множество. Другими словами, множество мокно как бы разбить на подмножество элементов, которые меньше х, и подмножество элементов, больших х.

Листинг 5.1. Процедура MEMBER для дерева двоичного поиска

function MEMBER ( х: elementtype; А: SET ) : boolean;

{ возвращает true, если элемент х принадлежит множеству А, false - в противном случае }

Напомним, что любой узел считается (по определению из раздела 3.1 главы 3) предком самого себя, поэтому мы здесь не исключаем возможность, что элемент х может совнасть с левым сыном корня.

5.1. ДЕРЕВЬЯ ДВОИЧНОЕО ПОИСКА 147



begin

if A = nil then

return (false) { x не может принадлежать О } else if X = At .element then

return(true) else if X < At.element then

return (MEMBER (x, At. leftchild)) else { X > aT. element }

return (MEMBER (x, At. rightchild) ) end; { MEMBER }

Процедура INSERT(x, A), которая добавляет элемент x в множество А, также проста для написания. Первым действием этой процедуры должна быть проверка условия А = nil, т.е. не является ли множество А пустым. Если это так, то создается новый узел, содержащий х, я А делается указателем на этот узел. Если множество А не пустое, то, сначала производится поиск элемента, совпадающего с х (это делается примерно так же, как в функции MEMBER). Если элемент х уже есть в множестве, то никакие действия дальше не производятся. Если же в процессе поиска будет достигнут указатель nil (т.е. дошли до листа дерева), то он заменяется на указатель, указывающий на новый узел, содержащий элемент х. Код этой процедуры приведен в листинге 5.2.

Листинг 5.2. Вставка нового элемента в дерево двоичного поиска

procedure INSERT ( х: elementtype; var А: SET ) ; begin

if A - nil then begin newiA) ;

At .element: = x; ЛТ. leftchild: = nil; At. rightchild: = nil

else if X < At. element then

INSERT (x, At. leftchild) else if X > At. element then

INSERT (x, At. rightchild) { если X = At. element, TO никаких действий

не производится, т.к. х уже есть в множестве А ) end; { INSERT }

Удаление элемента представляет некоторые трудности. Сначала надо найти этот элемент в дереве. Если х является листом, то он просто удаляется. Но если X является внутренним узлом (назовем его для краткости inode, от interior node - внутренний узел), то его нельзя просто удалить, так как нарушится связанность дерева.

Если inode имеет только одного сына (как узел 14 на рис. 5.1,6), то его можно заменить этим сыном. Если inode имеет двух сыновей, как узел 10 на рис. 5.1,а, то среди потомков правого сына надо найти элемент с наименьшим значением и заменить им удаляемый элемент. Например, для узла 10 на рис. 5.1,а таким будет узел 12.

Для написания процедуры DELETE полезно иметь функцию DELETEMIN(A), которая удаляет наименьший элемент из непустого дерева и возврашает значение удаляемого элемента. Код функции DELETEMIN приведен в листинге 5.3, а код процедуры DELETE, использующий эту функцию, - в листинге 5.4.

Можно также искать элемент с наибольшим значением среди потомков левого сына. 148 ГЛАВА 5. СПЕЦИАЛЬНЫЕ МЕТОДЫ ПРЕДСТАВЛЕНИЯ МНОЖЕСТВ



Листинг 5.3. Удаление наименьшего элемента

function DELETEMIN { var Л: SET ) : elementtype; begin

if At.leftchild = nil then begin

{ A указывает на наименьший элемент } DELETEMIN:= ЛТ.element; А;= лТ.rightchild

{ замена узла, указанного А, его гавьгм сыном }

else { узел, указанный А, имеет левого сына } DELETEMIN:= DELETEMIN(At.leftchild)

end; { DELETEMIN }

Листинг 5.4. Удаление элемента из девалоичного пОИСкЗ

ад • > • - • л "

procedure DELETE { х: elementtype; var А: SET ); begin

if A<> nil then

if X < лТ. element then

DELETE (x, ЛТ. leftchild) else if X > At. element tlien

DELETE(x, At.risrhtchild) else if (лt. Ieftchild= nil) and (Лt.rightcЛiId= nil) tlien

A:= nil { удаление листа, содержащего x } else if AT.leftchild = nil then

A:= At.rightchild else if At.rigrhtchild = nil then

A:= At.leftchild else { у узла есть оба сына }

Лt. element- DELETEMIN (At. right child) end; { DELETE }

Пример 5.1. Предположим, надо удалить элемент 10 из дерева, показанного на рис. 5.1,а. В данном случае первым исполняемым оператором в процедуре DELETE будет вызов функции DELETEMIN с аргументом-указателем на узел 14. Этот указатель - значение поля rightchild корня. Результатом этого вызова будет еще один вызов той же функции DELETEMIN. В этом случае ее аргументом будет указатель на узел 12, который находится в поле leftchild узла 14. Узел 12 не имеет левого сына, поэтому функция возвращает элемент 12 и устанавливает указатель узла 14 на левого сына в состояние nil. Затем процедура DELETE берет значение 12, юзвращенное функцией DELETEMIN, и заменяет им элемент 10. Результирующее дерево показано на рис. 5.2. □


Рис. 5.2. Дерево, представленное на рис. 5.1,а, после удаления элемента 10

5.1. ДЕРЕВЬЯ ДВОИЧНОЕО ПОИСКА г 149





0 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 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.002