Главная Промышленная автоматика. Рис. 4.33. Расцепление 2-3-дерева. Операции СЦЕПИТЬ(51, 5 а) на вход подаются такие две последовательности Si и Sa, что каждый элемент из Si меньше каждого элемента из Sa; на выход она выдает конкатенацию этих последовательностей, т. е. SiSa. Если Si и Sa представлены соответственно 2-3-деревьями и Га, то мы хотим соединить Ti и в одно дерево Т, листьями которого являются листья дерева Ti в их первоначальном порядке и следующие за ними листья дерева Ti в их первоначальном порядке. Это можно осуществить, вызвав процедуру ИМПЛАНТАЦИЖЛ, Т), приведенную на рис. 4.32. Наконец, рассмотрим операцию РАСЦЕПИТЬ. Напомним, что операция рАсЦЕПИТЬ(а, S) разбивает S на два множества Si= = {fc6<a и bS) и S2={b\b>a и bS). Для ее реализации определим процедуру ДЕЛЕНИЕ {а, Т), которая расцепляет 2-3-дерево Т на два такие 2-3-дерева Т и Га, что метки всех листьев в Г1 не больше а, а метки всех листьев в Га больше а. Метод можно неформально описать следующим образом. Дано 2-3-дерево Г, содержащее элемент а. Идем по пути из корня в лист с меткой а. Этот путь разбивает наше дерево на поддеревья, корнями которых служат не сами узлы, лежащие на нем, а их сыновья. Это иллюстрирует рис. 4.33, где слева от пути находятся деревья Гь Га, Гз и тривиальное дерево, состоящее из одного узла а справа - деревья г4, Т и v. Деревья слева от рассматриваемого пути и дерево, состоящее из одного узла а, соединяются с помощью только что описанного алгоритма конкатенации деревьев. Аналогично соединяются деревья, расположенные справа от пути. Необходимые детали даны в процедуре ДЕЛЕНИЕ (рис. 4.34). 1) Результат процедуры ИМПЛАНТАЦИЯ(7", Г") отнести к левому лесу. Аналогично при применении к деревьям из правого леса результат процедуры ИМПЛАНТАЦИЯ относится к правому лесу. Рис. 4.34. Процедура для расцепления 2-3-дерева. Теорема 4.7. Процедура ДЕЛЕНИЕ разбивает 2-3-дерево Т по листу а так, чпю все листья слева от а и сам лист а оказываются в одном 2-3-дереве, а все листья справа от а - в другом. Эта процедура занимает время 0(ВЫСОТА(7)). Порядок листьев сохраняется. Доказательство. Из свойств процедуры ИМПЛАНТАЦИЯ вытекает, что деревья объединены правильно. Результат о времени работы получается из следующих соображений. Вначале число деревьев любой данной высоты не более 2, только деревьев высоты О может быть 3. Когда два дерева соединяются, получается дерево, высота которого не более чем на единицу больше наибольшей из высот двух исходных деревьев. В случае когда получается дерево высоты, на единицу большей высоты любого из исходных деревьев, его корень имеет степень 2. Таким образом, если соединяются три дерева высоты Л, то в результате получается дерево procedure ДЕЛЕНИЕ(а, Т): begin на пути из узла К0РЕНЬ[7] к листу с меткой а удалить все узлы, кроме этого листа; comment В данный момент дерево Т оказалось разделенным на два леса-левый, состоящий из всех деревьев, листья которых лежат слева от а, и из узла с меткой а, и правый, состоящий из всех деревьев, листья которых лежат справа от а; Willie в левом лесу более одного дерева do begin пусть 7" и Т"-два самых правых дерева в левом лесу; ИМПЛАНТАЦИЖГ, Т")) end; while в правом лесу более одного дерева do begin пусть 7" и Т"-два самых левых дерева в правом лесу; ИМПЛАНТАЦИЯ(Т, Г) end ВЫСОТЫ не более h+\. Следовательно, на каждой стадии процесса число деревьев одинаковой высоты не превосходит 3. Время, требуемое для соединения двух деревьев разной высоты, пропорционально разности их высот, а одинаковой высоты - постоянно. Поэтому объединение всех деревьев происходит за время, пропорциональное сумме числа деревьев и наибольшей из разностей высот любых двух деревьев. Таким образом, всего тратится времени порядка высоты исходного дерева. □ Заметим, что с помощью сцепляемой очереди последовательность Sa можно вставить между парой элементов последовательности Si за время 0(МАХ (logSi, loglSal)). Если Sa=bi, Ьа, • • • . . ., bn, Si=ai, fla, • • •. «m и Sa нужно вставить между элементами а,, и а;+1, то можно применить операцию РАСЦЕПИТЬ(аг, Si) и разбить Si по элементу на две последовательности Si=ai, . . ., а,-и Si=ai+u . . ., а„. Затем применить операцию CUEnHTb(Si, Sa), результатом которой будет последовательность Ss-Ui, . . ., at, bi, . . ., bn, и, наконец, операцию CIEnHTb(S3, Sl), дающую нужную последовательность. 4.13. РАЗБИЕНИЕ Рассмотрим специальный тип расцепления, называемый разбиением. Задача разбиения множества возникает довольно часто, и решение, которое мы продемонстрируем здесь, поучительно само по себе. Пусть даны множество S и разбиение я множества S на непересекающиеся блоки {Bi, Ва, • • •, Bp}. Кроме того, дана функция /, отображающая S на S. Наша задача состоит в том, чтобы найти такое грубейшее (с наименьшим числом блоков) разбиение n = {Ei, Е2, . . ., £,} множества S, что 1) я - подразбиение разбиения я (т. е. каждое множество Ei является подмножеством некоторого блока Bj), 2) если а и b принадлежат Et, то }{а) и f{b) принадлежат Ej для некоторого /. Будем называть я грубейшим разбиением множества S, сов-местимьш с п и f. Очевидное решение- состоит в повторном утончении блоков исходного разбиения следующим способом. Пусть Bj - какой-нибудь блок. Рассмотрим f{a) для каждого а из Bi. Разобьем Bj так, чтобы два элемента а и b попадали в один блок тогда и только тогда, когда f{a) и f{b) оба принадлежат некоторому блоку Bj. Процесс повторяется до тех пор, пока уже нельзя будет проводить дальнейшие утончения. Этот метод дает алгоритм сложности 0(«), поскольку каждое утончение занимает время О (п.), а всего может 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.002 |