Главная Промышленная автоматика. Линейно упорядоченное множество 5 можно представить 2-3-деревом, приписав его элементы листьям дерева. Обозначим элемент, приписанный листу /, через ЕШ. Существуют два основных метода приписывания элементов листьям; какой из них применить, зависит от рассматриваемой задачи. Если допускается элементов гораздо больше, чем на самом деле используется, и дереву предстоит быть словарем, то, вероятно, лучше приписывать элементы в порядке возрастания слева направо. В каждом узле v, не являющемся листом, нам потребуется еще два данных: L[v] и М [v]. L[v] -это наибольший элемент множества 5 в поддереве, корнем которого служит самый левый сын узла v; M[v] - это наибольший элемент множества S в поддереве, корнем которого служит второй сын узла v (см. рис. 4.26). Значения L и М, приписанные узлам, позволяют искать элемент, начиная с корня, способом, аналогичным двоичному поиску. Время обнаружения произвольного элемента пропорционально высоте дерева. Поэтому операцию ПРИНАДЛЕЖАТЬ можно выполнить на множестве из п элементов за время O(logn), если представить его в виде 2-3-дерева такого рода. Во втором методе приписывания элементов листьям на порядок, в котором приписываются эти элементы, не налагается никаких ограничений. Метод особенно полезен для реализации операции ОБЪЕДИНИТЬ. Однако для выполнения операций типа УДАЛИТЬ нужен механизм для определения положения листа, представляющего данный элемент. Если элементами множества являются целые числа из фиксированной области, скажем от 1 до п, то лист, представляющий элемент i, можно находить с помощью г-й ячейки некоторого массива. Если же элементы рассматриваемых множеств принадлежат некоторому большому универсальному множеству, то лист, представляющий элемент /, можно находить с помощью вспомогательного словаря. Рассмотрим следующие наборы операций. 1) ВСТАВИТЬ, УДАЛИТЬ, ПРИНАДЛЕЖАТЬ. 2) ВСТАВИТЬ, УДАЛИТЬ, MIN. 3) ВСТАВИТЬ, УДАЛИТЬ, ОБЪЕДИНИТЬ, MIN. 4) ВСТАВИТЬ, УДАЛИТЬ, НАЙТИ, СЦЕПИТЬ, РАСЦЕПИТЬ. Структуру данных, обеспечивающую выполнение операций из множества 1, будем называть словарем, из множества 2 - очередью с приоритетами, из множества 3 - сливаемым деревом, из множества 4 - сцепляемой очередью. Покажем, что 2-3-деревья могут служить для реализации словарей, очередей с приоритетами, сцепляемых очередей и сливаемых деревьев, применение которых обеспечивает выполнение п операций за время 0{п logn). Развитая здесь техника достаточно мощна, чтобы выполнить последовательности, составленные из любого совместного подмножества семи операций, перечисленных в начале главы. Единственная несовместность состоит в том, что операция ОБЪЕДИНИТЬ приводит к неупорядоченному множеству, а РАСЦЕПИТЬ и СЦЕПИТЬ предполагают наличие порядка. 4.10. СЛОВАРИ И ОЧЕРЕДИ С ПРИОРИТЕТАМИ В этом разделе мы изучим основные преобразования, требуемые для реализации словарей и очередей с приоритетами. На протяжении всего раздела будем предполагать, что элементы приписаны листьям 2-3-дерева в порядке слева направо и в каждом нелисте v определены функции L[v] и M[v], введенные в предыдущем разделе. Чтобы в 2-3-дерево вставить новый элемент а, надо найти место для нового листа /, который будет содержать а. Для этого ищут элемент а в дереве. Если дерево содержит более одного элемента, то поиск а окончится в узле /, имеющем двух или трех сыновей, которые являются листьями. Если из узла / выходит только два листа li и /а, то / делаем сыном узла /. Если a<cE[li] то / делаем самым левым сыном узла / и полагаем L[/]=a и M[f]=E[li]; если E[li]<a<E[l2\, то / делаем средним сыном узла / и полагаем Mlf]=a; если E[l2\<a, то / делаем третьим сыном узла /. В последнем случае, возможно, надо будет изменить значения L и М на некоторых подлинных предках узла /. Пример 4.9. Если в 2-3-дерево, изображенное на рис. 4.27,а, вставляется элемент 2, то получается 2-3-дерево, изображенное на рис. 4.27,6. □ Рис. 4.27. Вставка в 2-3-дерево: а - дерево перед вставкой; б - дерево после вставки элемента 2. Теперь предположим, что у / уже есть три листа /i, /а и /3. Сделаем I надлежащим сыном узла /. Теперь / имеет четырех сыновей. Чтобы сохранить 2-3-свойство, образуем новый узел g. Два левых *) E[v] - элемент, приписанный узлу v. Рис. 4.28. Дерево с рис. 4.27, а после вставки элемента 4. Алгоритм 4.4. Вставка нового элемента в 2-3-дерево Вход. Непустое 2-3-дерево Т с корнем г и новый элемент аТ. Выход. Преобразованное 2-3-дерево с новым листом, помеченным а. Метод. По условию Т содержит хотя бы один элемент. Чтобы упростить описание алгоритма, опустим детали корректировки L и М. 1. Если Т состоит из единственного узла / с меткой Ь, образуем новый корень г. Образуем новый узел v с меткой а. Делаем / и v сыновьями корня г, причем / будет левым сыном, если Ь<<а, и правым в противном случае. 2. Если Т содержит более одного узла, положим /=ПОИСК(а, г); процедура ПОИСК приведена на рис. 4.29. Образуем новый сына оставим сыновьями узла /, а два правых переделаем в сыновей узла g. Затем сделаем g братом узла /, сделав его сыном отца узла /. Если отец узла / имел двух сыновей, то на этом мы остановимся. Если же трех, то надо рекурсивно повторять эту процедуру до тех пор, пока у всех узлов в дереве останется не более трех сыновей. Если у корня окажется четыре сына, образуем новый корень с двумя новыми сыновьями, каждый из которых будет иметь в качестве двух своих сыновей двух из четырех сыновей старого корня. Пример 4.10. Если в 2-3-дерево на рис. 4.27,а, вставляется элемент 4, то новый лист с меткой 4 надо сделать самым левым сыном узла с. Поскольку у с уже есть три сына, строим новый узел с. Затем делаем листья 4 и 5 сыновьями узла с, а листья 6 и 7 - сыновьями узла с. Теперь делаем с сыном узла а. Но поскольку у а уже есть три сына, строим новый узел а. Делаем узлы Ь и с сыновьями старого узла а, а узлы с к d - сыновьями нового узла а. Наконец, образуем новый корень г и делаем а а а его сыновьями. Полученное дерево изображено на рис. 4.28. □ 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.0021 |