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

) Если нам нужны значения L и М для нового узла, образованного процедурой ДОБАВСЫНА(/), то сначала надо найти наибольшего потомка узла v, следуя по пути, идущему в самый правый лист.

Рис. 4.32. Процедура ИМПЛ.ЛНТАЦИЯ.

поддереве с корнем v. Для этого применения 2-3-деревьев L[v] и Mlv] не нужны.

Наименьший элемент множества S можно найти, если следующим образом двигаться вниз по дереву Т, начиная от его корня. Находясь во внутреннем узле v, переходим к сыну узла и, помеченному наименьшим значением функции НАИМЕНЬШИЙ. Следовательно, если Т содержит п листьев, то операция MIN занимает О (log л) шагов.

Во многих приложениях всякий раз, когда надо удалить из S какой-то элемент, он всегда наименьший. Но если мы хотим удалить из 5 произвольный элемент, мы должны уметь найти лист, содержащий его. В тех приложениях, где элементы можно представить целыми числами 1, 2, . . ., л, можно пронумеровать сами листья. Если же элементы произвольны, то можно воспользоваться вспомогательным 2-3-словарем, листья которого содержат указатели на листья дерева Т. С помощью этого словаря можно достичь произвольного листа за О (log л) шагов. Словарь надо корректировать

procedure ИМПЛАНТАЦИЯ(Г1, Т,): И BblCOTA(ri) = ВЫСОТА(Га) then begin

образовать новый корень г;

сделать KOPEHfafrj и КОРЕНЬ[Г,,] соответственно левым и правым сыновьями узла г;

end else

wig положим BblCOTA(Ti) > высотА(Т,) otherwise переставить Tj с Tj и "левый" с "правым" in bin

пусть W-такой узел на самом правом пути в Т, что ГЛУБИНА(&) = ВЫСОТ A(Ti) - BbICOTA(Ta); пусть /-отец узла v;

сделать КОРЕНЬ[72] сыном узла /, расположенным непосредственно справа от и; if у / сейчас четыре сына then ДОБАВСЫНА(/) i) end



всякий раз, когда выполняется операция ВСТАВИТЬ, но это требует не более O(logn) шагов.

Коль скоро лист / удален из Т, надо для каждого его подлинного предка V пересчитать значения функции НАИМЕНЬШИЙ. Новым значением для НАИМЕНЬШИЙ v] будет наименьшее из значений НАИМЕНЬШИЙ[5] для двух или трех сыновей s узла v. Если всегда пересчитывать снизу вверх, то индукцией по числу пересчетов можно показать, что каждое вычисление дает для функции НАИМЕНЬШИЙ правильный ответ. Так как эта функция меняется только в предках удаленного листа, то операцию УДАЛИТЬ можно выполнить за O(logn) шагов.

Изучим операцию ОБЪЕДИНИТЬ. Каждое множество представлено отдельным 2-3-деревом. Чтобы слить два множества Si и Si, вызываем процедуру ИМПЛАНТАЦИЖГ!, Га), приведенную на рис. 4.32, где Ti и Т - это 2-3-деревья, представляющие Si и 5а

Пусть высота hi дерева Ti не меньше высоты h дерева Т. ИМПЛАНТАЦИЯ находит на самом правом пути в Ti узел v с высотой Ла и делает корень дерева его самым правым братом. Если у его отца / окажется четыре сына, ИМПЛАНТАЦИЯ вызовет процедуру ДОБАВСЫНА (/). Значения функции НАИМЕНЬШИЙ на узлах, потомки которых изменяются в процессе выполнения процедуры ИМПЛАНТАцИЯ, можно скорректировать тем же способом, что и в операции УДАЛИТЬ.

В качестве упражнения предлагаем показать, что процедура ИМПЛАНТАЦИЯ соединяет Ti и Га в одно 2-3-дерево за время О {hi-hi) (при /ii>/ia)- Если учитывать время на корректировку значений L и М, то процедура ИМПЛАНТАЦИЯ может занять 0(MAX(logSi, logllSalD) времени.

Рассмотрим теперь приложение, в котором естественно возникают операции ОБЪЕДИНИТЬ, MIN и УДАЛИТЬ.

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

Рассмотрим другую стратегию. Для каждого множества узлов V/ будем хранить множество Ei всех нерассмотренных ребер, ин-

) Здесь различие между «левым» и «правым» неважно; оно сделано ради сцепляемых очередей, которые обсуждаются в следующем разделе.



4.12. СЦЕПЛЯЕМЫЕ ОЧЕРЕДИ

В разд. 4.10 было показано, как на 2-3-дереве с п листьями выполнить каждую из операций ВСТАВИТЬ, УДАЛИТЬ, MIN и ПРИНАДЛЕЖАТЬ за время О (logn), если пользоваться значениями L и М. Сейчас покажем, как за время О (logn) выполнить каждую из операций СЦЕПИТЬ и РАСЦЕПИТЬ. Снова будем предполагать, что элементы расположены на листьях 2-3-дерева в порядке возрастания слева направо и для каждого узла v вычисляются значения L[v] и Mlv].

цидентных каким-то узлам в У. Если выбрать не рассмотренное ранее ребро е, инцидентное узлу из относительно малого множества У,, то другой конец ребра е с большой вероятностью не будет лежать в У;, и можно будет добавить е к остовному дереву. Если это нерассмотренное ребро е обладает наименьшей стоимостью среди всех ребер, инцидентных узлам из У;, то можно показать, что включение его в остовное дерево приведет к остовному дереву наименьшей стоимости.

Для реализации этого алгоритма надо сначала образовать для каждого узла множество инцидентных ему ребер. Чтобы среди ребер, инцидентных узлам из У;, найти нерассмотренное ребро наименьшей стоимости, применим МШ-оператор к множеству нерассмотренных ребер для У;. Затем удалим из найденное так ребро е. Если окажется, что е имеет в У только один конец, а другой лежит в множестве У, отличном от У;, то выполним операцию ОБЪЕДИНИТЬ для У; и У (например, используя структуру данных алгоритма 4.3), а также для Ei и

В качестве структуры данных для представления каждого множества ребер Ei можно взять 2-3-дерево, каждый лист которого помечен ребром и его стоимостью. На множестве ребер нет никакого специального порядка. Каждому нелисту приписана наименьшая стоимость его потомков-листьев, обозначаемая НАИМЕНЬШИЙ!].

Вначале для каждого узла образуем 2-3-дерево, содержащее все инцидентные ему ребра. Чтобы построить такое дерево, начнем с листьев. Затем добавим узлы высоты 1, так объединяя листья в группы по два или три, чтобы групп из двух листьев было не больше двух. Сделав это, вычислим для каждого узла высоты 1 наименьшую стоимость листа-потомка. Затем соберем узлы высоты 1 в группы по два или три и будем продолжать процесс до тех пор, пока на некотором уровне не образуется один узел, а именно корень. Время, затрачиваемое на такое построение дерева, пропорционально числу листьев. Реализация остальной части алгоритма теперь должна быть очевидна. Общее время работы составляет O(e\oge), где е - число всех ребер. □





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