Главная Промышленная автоматика. 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.0019 |