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

Рис. 4.16. Дерево после выполнения операций ОБЪЕДИНИТЬ.

ПО крайней мере один узел. Допустим, что утверждение верно для всех значений параметра, меньших 1г\. Пусть Т - дерево высоты h с наименьшим числом узлов. Тогда оно должно было получиться 3 результате слияния деревьев Ti и Г г, где Ti - дерево высоты г-1 и у него узлов не больше, чем у Tj. По предположению индукции Ti имеет не менее 2*-* узлов, и, значит. Та имеет не менее 2*-* узлов, откуда следует, что Т имеет не менее 2* узлов. □

Оценим время выполнения (в худшем случае) последовательности из п операций ОБЪЕДИНИТЬ и НАЙТИ, если пользоваться структурой данных-в виде леса, модифицированной так, что в операции ОБЪЕДИНИТЬ корень меньшего дерева становится сыном корня большего дерева. Никакое дерево не может иметь высоту, большую log л. Следовательно, сложность выполнения 0{п) операций ОБЪЕДИНИТЬ и НАЙТИ не превосходит 0{п log п). Эта граница точна в том смысле, что существуют последовательности из п операций, занимающие время, пропорциональное п log п.

Изложим еще одну модификацию этого алгоритма, называемую сжатием путей. Поскольку в общей сложности преобладает сложность операций НАЙТИ, попробуем уменьшить ее. Всякий раз, когда выполняется операция НАЙТИ (i), мы проходим путь от узла i до корня г. Пусть i, Vu v, . . ., и„, г - узлы на этом пути. Тогда каждый из узлов i, Vi, Wa. • • ., "n-i делается сыном корня. На рис. 4.17, б отражено влияние операции НАЙТИ (i) на дерево, приведенное на рис. 4.17, а.




Рис. 4.17. Результат сжатия путей.

Вся процедура слияния деревьев для задачи ОБЪЕДИНИТЬ - НАЙТИ, включая сжатие путей, выражена в следующем алгоритме.

Алгоритм 4.3. Алгоритм быстрого объединения непересекающихся множеств

Вход. Последовательность а операций ОБЪЕДИНИТЬ и НАЙТИ, выполняемых на наборе множеств, элементы которых представлены целыми числами от 1 до п. Предполагается, что имена множеств также являются целыми числами от 1 до п и вначале множество с именем i состоит из единственного элемента - самого числа i.

Выход. Последовательность ответов на операции НАЙТИ из а. Ответ на каждую операцию НАЙТИ надо получить перед просмотром очередной операции в а.

Метод. Описание алгоритма состоит из трех частей: организация начальной структуры, выполнение операции НАЙТИ и выполнение операции ОБЪЕДИНИТЬ.

1. Организация начальной структуры. Для каждого элемента i, lin, образуем узел О;. Полагаем C4ET[Uj]=l, ИМЯ [,1=/ и OTEU[wJ=0. Вначале каждый узел Vi сам является деревом. Чтобы можно было определять корень множества i, образуем такой массив КОРЕНЬ, что КОРЕНЫ/] указывает на и. Чтобы определить узел, содержащий элемент /, образуем массив ЭЛЕМЕНТ; вначале ЭЛЕМЕНТ li]=Vi.

2. Выполнение операции НАЙТИ (/). Программа приведена на рис. 4.18. Начиная с узла ЭЛЕМЕНТ [/], идем по пути, ведущему к корню дерева, и выписываем встретившиеся узлы. По достижении



begin

сделать СПИСОК пустым; 1).-ЭЛЕМЕНТ[1]; while ОТЕЦ[и]=?0 do begin

добавить V в список; end;

comment v теперь корень; print ИМЯ[и];

for для каждого w, входящего в СПИСОК do ОТЕЦ[ш]*-о end

Рис. 4.18. Выполнение операции НАЙТИ (i).

корня выдается имя множества, а каждый узел из пройденного пути делается сыном корня.

3. Выполнение операции ОБЪЕДИНИТЬ(t, /, k). С помощью массива КОРЕНЬ находим корни деревьев, представляющих множества i и /. Затем делаем корень меньшего дерева сыном корня большего дерева. См. рис. 4.19. □

Покажем, что сжатие путей значительно ускоряет работу алгоритма. Чтобы подсчитать это улучшение, введем функции F и G.

begin

wig положить C4ET[K0PEHb[i]]<C4ET[K0PEHb[/jJ otherwise переставить t и / in begin

БОЛЬШОЙ - КОРЕНЬ[/]; МАЛЫЙ КОРЕНЬ[(]; ОТЕЩМАЛЫЙ] БОЛЬШОЙ;

СЧЕТ[БОЛЬШОЙ] СЧЕТ[БОЛЬШОЙ] -ЬСЧЕТ[МА-

ЛЫЙ]; ИМЯ[БОЛЬШОЙ]/г; КОРЕНЬ[/г] - БОЛЬШОЙ end

Рис. 4.19. Выполнение операции ОБЪЕДИНИТЬ («, /, k).





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 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0022