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


Рис. 4.21. Результат операции ЧН.

горитма 4.3 нелинейно по п. Для этого построим конкретную последовательность операций ОБЪЕДИНИТЬ и НАЙТИ, на которой алгоритм 4.3 работает нелинейное время.

Удобно ввести новую операцию над деревьями, которую мы будем называть ЧАСТИЧНО НАЙТИ - сокращенно ЧН. Пусть Т - дерево, в котором узлы v, t»i, Ua, • w образуют путь из узла v к его предку w (w не обязательно корень). Операция ЧН (v, w) делает каждый из узлов v, Vi, Wj. • • , Um-i сыном узла w. Мы будем говорить, что эта операция ЧН имеет длину т+1 (если w=uy, то длина равна 0). На рис. 4.21,6 отражено влияние операции ЧН(и, ш) на дерево, приведенное на рис. 4.21,а.

Пусть дана последовательность а операций ОБЪЕДИНИТЬ и НАЙТИ. Когда выполняется данная операция НАЙТИ из а, мы находим положение узла v в некотором дереве Т и идем по пути из и в корень W этого дерева. Теперь предположим, что выполняются только операции ОБЪЕДИНИТЬ из а, а операции НАЙТИ не выполняются. В результате получается некоторый лес F. Действие данной операции НАЙТИ из о все еще можно уловить, если найти в F положение узлов v и w, которые должна была использовать эта операция НАЙТИ, и затем выполнить ЧН (и, w). Заметим, что узел W может больше не быть корнем в F.

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




Рис. 4.22. Дерево Г(2).

ревьев мы построим последовательности операций ОБЪЕДИНИТЬ и ЧН, на которых время работы алгоритма 4.3 более чем линейно.

Определение. Для kO пусть Т (к) дерево, в котором

1) глубина каждого листа равна к

2) каждый узел высоты h имеет 2* сыновей,

Таким образом, корень дерева Т (к) имеет 2* сыновей, каждый из которых является корнем экземпляра дерева Т {к-1). На рис. 4.22 изображено дерево Т(2).

Лемма 4.4. Для каждого кО можно построить дерево Т{к), которое порождается некоторой последовательностью операций ОБЪЕДИНИТЬ и содержит в качестве подграфа дерево Т (к), причем по меньшей мере четверть узлов дерева Т(к) являются листьями в Т{к).

Доказательство. Доказательство проводится индукцией по к. Для =0 лемма тривиальна, ибо Т{0) состоит из одного узла. Чтобы построить Т(к) для к>0, построим сначала 2*+1 экземпляров Т(к-1). Образуем дерево Т (к), выбрав один экземпляр Т(к-1) и затем влив в него один за другим каждый из оставшихся экземпляров. Корень полученного дерева имеет (среди других) 2* сыновей, каждый из которых является корнем дерева T{k-1).

Пусть Л() - общее число узлов в Т{к) и L{k) - число листьев в Т{к). Тогда

Л/(0) = 1,

Л/(/г) = (2*-Ь l)iV(/: -1) для к1

откуда

L{0) = \,

L(fe) = 2ftL(-1) для kl,

Д(2 + 1) =2



Комбинируя (4.3) с (4.4), получаем

Ljk) 2 ., 1

Лемма доказана. □

Мы будем строить последовательность операций ОБЪЕДИНИТЬ и ЧН, которая сначала даст дерево Т" (k), а затем выполнит ЧН на листьях подграфа T{k). Сначала покажем, что для каждого />0 найдется такое число k, что можно выполнить ЧН длины / последовательно на каждом листе дерева T{k).

Определение. Пусть D (с, /, h) - такое наименьшее значение k, что если заменить каждое поддерево в T(k) с корнем высоты А любым деревом, имеющим / листьев и высоту не меньше 1, то на каждом листе полученного дерева можно будет выполнить ЧН длины с.

Лемма 4.5. Значение D (с, I, h) определено (т. е. конечно) для всех с, I и h, больших нуля.

Доказательство. В доказательстве применяется двойная индукция. Мы хотим доказать наше утверждение индукцией по с. Но для доказательства этого утверждения для с, исходя из истинности его для с-1, надо провести индукцию по I.

Базис, т. е. случай с=1, доказывается легко. D(l, I, h)=h для всех I а h, поскольку ЧН длины 1 не перемещает никаких узлов.

Теперь, чтобы провести индукцию по с, предположим, что для всех I и h определено значение D{c-1, /, /г). Мы должны показать, что D (с, /, h) определено для всех / и h. Это делается индукцией по I.

Для базиса индукции по / докажем, что

D(c, 1, /i)<D(c-1, 2*+i, Л-Ы).

Заметим, что по определению числа D {с, I, h) при Z«l поддеревья в Т () с корнями высоты h заменяются деревьями с единственным листом. Пусть Н - множество узлов высоты h в дереве T{k). Очевидно, что в этом преобразованном дереве каждый лист является подлинным потомком единственного элемента множества Н. Поэтому, если бы мы смогли выполнить операции ЧН длины с-1 на всех элементах множества Н, то, конечно, смогли бы выполнить ЧН длины с на всех листьях.

Заметим, что для />2 справедливо неравенство 1п(1--2-0<2~, поэтому





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