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

вень. На рис. 4.8,а показана вставка элемента с приоритетом 4 в дерево из рис. 4.6. Если новый элемент имеет меньший приоритет, чем у его родителя, то они меняются местами. Таким образом, новый элемент теперь находится в позиции, когда у его сыновей больший приоритет, чем у него. Но возможно, что у его нового родителя приоритет больше, чем у него. В этом случае они также меняются местами. Этот процесс продолжается до тех пор, пока новый элемент не окажется в корне дерева или не займет позицию, где приоритет родителя не будет превышать приоритет нового элемента. Рис. 4.8,6, в показывают этапы перемешения нового элемента.


10 18 9

а б В

Рис. 4.8. Вставка нового элемента

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

1. Элемент а - это новый элемент, который, перемешаясь по дереву вверх, заменил родителя элемента Ь. Пусть старый родитель элемента Ь имел приоритет с, тогда а < с, иначе не произошла бы замена. Но с < Ь, поскольку исходное дерево частично упорядочено. Отсюда следует, что а < Ь. Пример такой ситуации показан на рис. 4.8,в, где элемент 4 становится родителем элемента 6, заменяя его родителя с приоритетом 5.

2. Элемент а спустился вниз по дереву вследствие обмена с новым элементом. В этом случае в исходном дереве элемент а должен быть предком элемента Ь. Поэтому а < Ъ. На рис. 4.8,в элемент 5, ставший родителем элементов с приоритетами 8 и 9, ранее был их "дедушкой".

3. Элемент Ь - новый элемент, который, перемешаясь вверх по дереву, стал сыном элемента а. Если а > Ь, то на следующем шаге они поменяются местами, ликвидируя тем самым нарушение свойства упорядоченности дерева.

Время выполнения оператора вставки пропорционально пути, пройденному новым элементом. Так же, как и в случае оператора DELETEMIN, этот путь не может быть больше 1 + logra. Таким образом, время выполнения обоих этих операторов имеет порядок O(logra).

Реализация частично упорядоченныхдеревьев посредством массивов

Исходя из того, что рассматриваемые нами деревья являются двоичными, по возможности сбалансированными и на самом нижнем уровне все листья "сдвинуты" влево, можно применить для этих деревьев необычное представление, которое называется куча. В этом представлении используется массив, назовем его А, в котором первые и позиций соответствуют га узлам дерева. А[1] содержит корень дерева. Левый сын узла A[i\, если он существует, находится в ячейке .A[2i], а правый сын, если он



также существует, - в ячейке A[2i + 1]. Обратное преобразование: если сын находится в ячейке АЩ, i > 1, то его родитель - в ячейке A[i div 2]. Отсюда видно, что узлы дерева заполняют ячейки А[1], А[2], А[п] последовательно уровень за уровнем, начиная с корня, а внутри уровня - слева направо. Например, дерево, показанное на рис. 4.6, будет представлено в массиве следующей последовательностью своих узлов: 3, 5, 9, 6, 8, 9, 10, 10, 18, 9.

В данном случае мы можем объявить АТД PRIORITYQUEUE (Очередь с приоритетами) как записи с полем contents для массива элементов типа, например processtype, как в примере 4.9, и полем last пелочисленного типа, значение которого указывает на последний используемый элемент массива. Если мы также введем константу maxsize, равную количеству элементов очереди, то получим следующее объявление типов:

type

PRIORITYQUEUE = record

contents: array[1..maxsize] of processtype; last: integer

end;

Реализация операторов, выполняемых над очередью с приоритетами, показана в следующем листинге.

Листинг 4.13. Реализация очереди с приоритетами посредством массива

procedure MAKENULL ( var Л: PRIORITYQUEUE ); begin

A. last:= 0

end; { MAKENULL }

procedure INSERT ( x: processtype; var A: PRIORITYQUEUE ) ,-var

i: integer;

temp: processtype; begin

if A.last >= maxsize then

error(Очередь заполнена) else begin

A.last:= A.last + 1; • A.contents[A.last] :- x;

i: = A.last; { i - индекс текущей позиции x } while (1 > 1) and (p(A. contents [i] ) <

p(A.contents[i div 2])) do begin { перемещение x вверх no дереву путем обмена местами с родителем, имеющим больший приоритет } tenip:= A.contentsli] ; А.СОЛtents[i]:= A.contents[i div 2]; A.contentsli div 2]:= teinp,-i:= i div 2

end; { INSERT }

function DELETEMIN ( var A: PRIORITYQUEUE ): tprocesstype; var

i, j: integer;

temp: processtype;



minimum: Tprocesstype; begin

if A.last = 0 then

error(очередь пуста) else begin

newiminimum);

minimum t := д.contents[1];

A. contents[1] := A.contents[A.last];

A.last:= A.last - 1;

i:= 1;

while i <= A.last div 2 do begin

{ перемещение старого последнего элемента

вниз по дереву } if (р(л. contents[2*i] ) < р(л. contents[2*i + 1])) or (2*i = А.last) then j:= 2*i

else

j:= 2*i + 1;

{ J будет сыном i с наименьшим приоритетом или,

если 2*i = л.last, будет просто сыном i } tf р{Л.contents]i]) > р{А.contents[j]) then begin

{ обмен старого последнего элемента с сыном, имеющим наименьший приоритет }

temp: = л. con tents[ij ;

А. contents[i] := А. contents[j];

А.contents[j]:= temp;

i : = j ;

end else

return(minimum)

{ дальше перемещение элемента невозможно }

end;

return(minimiim) { элемент дошел до листа }

end; { DELETEMIN }

4.12. Некоторые структуры сложных множеств

в этом разделе мы рассмотрим применение двух сложных множеств для представления данных. В первом примере рассмотрим представление отношений "многие-ко-многим", которые встречаются в системах баз данных. Далее мы изучим, как с помош.ью двух структур данных можно представить какой-либо объект (в нашем случае - отображение) более эффективно, чем при представлении этого объекта одной структурой.

Отношения „многие-ко-многим" и структура мультисписков

Пример отношения "многие-ко-многим" между множеством студентов и множеством учебных курсов (учебных предметов) показан в табл. 4.3. Отношение "многие-ко-многим" называется так потому, что на каждый курс могут записаться много студентов (не один) и каждый студент может записаться на несколько курсов.

Время от времени может возникнуть необходимость вставить или удалить студентов с какого-либо курса, определить, какие студенты посеш,ают тот или ной курс, или узнать, какие курсы посеш,ает конкретный студент. Простейшей структурой





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