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

nodet. thirdchild:= nil

else begin

{.child < 2; перемещение 3-го сына node к pnew] pnewt.secondchild: nodet. thirdchild; pnewt.lowofsecond:= nodet.lowofthird; pnewt.thirdchild: nil; лodet. thirdchild:= nil

end;

if child = 2 then begin

(pback становится 1-м сыном pnew } pn ewt.fi rs tchi I d: = pback; low:= lowback

end;

if child = 1 then begin

{ 2-й сын node перемещается к pnew,

pback становится 2-м сыном node } pnewt. firstchild: = nodet. secondchild; low:= nodet-lowofsecond; nodet. secondchiId: = pback; nodet. lowof second- lowback

end; { insertl }

Теперь можно написать процедуру INSERT, которая вызывает insert]. Если insertl "возвращает" новый узел, тогда INSERT должна создать новый корень дерева. Код процедуры INSERT представлен в листинге 5.11. Здесь мы считаем, что тип SET - это тип Ttwothreenode, т.е. указатель на корень 2-3 дерева, чьи листья содержат элементы исходного множества.

Листинг 5.11. Оператор INSERT для множеств, представленных посредством 2-Здеревьев

procedure insert ( х: elementtype; var s: set ) ;

pback: ttwothreenode; (указатель на узел, возвращенный insertl} lowback: real; {наименьшее (low) значение в поддереве pback] saves: set; { для временного хранения копии указателя s } begin

{ здесь надо вставить процедуру проверки, которая выясняет, . является ли s п/стым деревом или имеет только один узел, и Осуществляет для этих ситуаций вставку } insertHSr к, pback, lowback); if pback о nil then begin

{ создание нового корня, на его сыновей указывают s и pback } saveS:= S; new(S) ;

St. firstchild: = saveS; .secondchild:= pback; 5t. Joivof second: = lowback; St. thirdchi Id: = nil;

end; { insert )



Реализация оператора DELETE

Сделаем набросок функции deletel, которая по заданному указателю на узел node и элементу х удаляет лист, являющийся потомком узла node и содержащий значение x, если, конечно, такой лист существует. Если после удаления узел node имеет только одного сьша, то функция deletel возвращает значение true, а если узел node имеет двух или трех сыновей, то возвращает значение false. Эскиз этой функции показан в следующем листинге.

Листинг 5.12. Рекурсивная процедура удаления

function deletel ( node; ttwothreenode; x: elementtype ): boolean; var

ол1уоле: boolean;

.{ содержит значение, возвращаемое по вызову deletel }

begin

deletel := false;

if сыновья node являются листьями then begin if x принадлежит этим листьям then begin удаление x;

смещение сыновей node, которые были справа от х,

на одну позицию влево; If node имеет только одного сына then deletel;= true

else begin { node находится на втором уровне или вьщ1е } определяется, какой сын узла node может

иметь среди своих потомков х; оп1уопе:= deletel{w, х); {в зависимости от ситуации w обозначает nodet.firstchild, nodet. secondchild млк nodet. thirdchild } If onlyone then begin { просмотр сыновей node } If w - первый сын node then

If у - 2-й сын node, имеющий 3-х сыновей then

1-й сын у делается 2-м сыном w; else begin { у имеет двух сыновей } сын W делается 1-м сыном у; удаление w из множества сыновей узла node; if node имеет только одного сына then deletel;= true

end;

If w - второй сын node then

If у - 1-й сын node, имеющий 3-х сыновей then

3-й сын у делается 1-м сыном w else { у имеет двух сыновей }

If существует z - 3-й сын node, имеющий 3-х сыновей then

1-й сын Z делается 2-м сыном w else begin

{ у node нет сыновей, имеющих трех детей } сын w делается 3-м сыном у;

полезным вариантом такой функции была бы функция, которая только по ключевому значению удаляла все элементы с этим ключом.



удаление w из множества сыновей узла node; if node имеет только одного сына then delete!:= true

end;

if w - третий сын node then

if у - 2-й сын node, имеющий 3-х сыновей then

3-й сын у делается 1-м сыном w; else begin { у имеет двух сыновей }

сын W делается 3-м сыном у;

удаление w из множества сыновей узла node;

end; { deletel }

Мы оставляем для читателя детализацию кода функции deletel. В качестве еще одного упражнения предлагаем написать процедуру DELETE(S, х), которая проверяла бы, не является ли множество S пустым или состоящим из одного элемента, и если это не так, то вызывала бы функцию deletel(S, х). Если deletel возвратит значение true, то процедура должна удалить корень (узел, на который указывает S) и сделать S указателем на единственного (в данной ситуации) сына корня.

5.5. Множества с операторами MERGE и FIND

в этом разделе мы рассмотрим ситуацию, когда есть совокупность объектов, каждый из которых является множеством. Основные действия, выполняемые над такой совокупностью, заключаются в объединении множеств в определенном порядке, а также в проверке принадлежности определенного объекта конкретному множеству. Эти задачи решаются с помощью операторов MERGE (Слить) и FIND (Найти). Оператор MERGE(A, В, С) делает множество. С равным объединению множеств А и В, если эти множества не пересекаются (т.е. не имеют общих элементов); этот оператор не определен, если множества А и В пересекаются. Функция FIND(a:) возвращает множество, которому принадлежит элемент ж; в случае, когда ж принадлежит нескольким множествам или не принадлежит ни одному, значение этой функции не определено.

Пример 5.6. Отношением эквивалентности является отнощение со свойствами рефлексивности, симметричности и транзитивности. Другими словами, если на множестве S определено отнощение эквивалентности, обозначаемое символом то для любых элементов а, Ь и с из множества S (не обязательно различных) справедливы следующие соотнощения.

1. а = а (свойство рефлексивности).

2. Если а = Ь, то Ь = а (свойство симметричности).

3. Если а=Ьтл.Ь=с, toa=c (свойство транзитивности).

Отнощение равенства (обозначается знаком "=") - это пример отнощения эквивалентности на любом множестве S. Для любых элементов а, Ь и с из множества S имеем (1) а - а; (2) если а = Ь, то Ь = а; (3) если а = 6 и Ь = с, то а = с. Далее мы встретимся с другими примерами отнощения эквивалентности.

В общем случае отнощение эквивалентности позволяет разбить совокупность объектов на непересекающиеся группы, когда элементы а и Ь будут принадлежать одной группе тогда и только тогда, когда а = Ъ. Если применить отнощение равенства (частный случай отнощения эквивалентности), то получим группы, состоящие из одного элемента.





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.0033