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

procedure ПОИСК(а, г):

if любой сын узла г является листом tiien return г else begin

пусть S; будет i-м сыном узла г; if a<L[r] then return ПОИСК(а, else

if у r два сына или aM[r] then return ПОИСК(а, Sj) else return ПОИСК(а, s,)

Рис. 4.29. Процедура ПОИСК.

лист / С меткой а. Если у / два сына с метками bi и &2, то делаем / надлежащим сыном узла /. А именно, I будет левым сыном, если a<:bi, средним, если bi<.a<.b2, и правым, если Ь2<.а. Если у / три сына, делаем / надлежащим сыном узла /, а затем чтобы включить в 7 узел/и его четырех сыновей, вызываем ДОБ ABC Ы НА (/). Процедура ДОБАВСЫНА приведена на рис. 4.30. Чтобы учесть присутствие узла а, корректируем значения L и М вдоль пути из а

procedure ДОБАВСЫНА (w): begin

образовать новый узел и;

сделать двух самых правых сыновей узла v левым и правым

сыновьями узла у; if у и нет отца then

begin

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

сделать v левым, а v правым сыном корня г end else begin

пусть /-отец узла v;

сделать v сыном узла /, расположенным непосредственно

справа от v; if теперь у / четыре сына then ДОБАВСЫНА(/) end

Рис. 4.30. Процедура ДОБАВСЫНА.



) Достаточно пройти путь от а до такого узла, что а - не наибольший элемент в его поддереве.

) Два узла с одним огцом называются братьями.

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

Теорема 4.6. Алгоритм 4.4 вставляет новый элемент в 2-3-дерево с п листьями за время, не превосходящее О (logn). Более того, этот алгоритм сохраняет порядок исходных листьев и структуру 2-3-дерева.

Доказательство. Очевидная индукция по числу вызовов процедуры ПОИСК показывает, что новый лист становится сыном того узла, какого надо. Порядок исходных листьев не затрагивается. Что касается времени работы, то в силу леммы 4.6 высота 2-3-дерева с п листьями не превосходит log п. Поскольку ДОБАВСЫНА(и) рекурсивно вызывает себя только на отце узла v, может произойти не более log п рекурсивных вызовов Каждый вызов ДОБАВСЫНА занимает постоянное время, так что общее время не превосходит О (logn). □

Элемент а можно удалить из 2-3-дерева способом, по существу обратным к вставке. Пусть а - метка листа /. Рассмотрим отдельно три случая.

Случай 1. Если / - корень, удаляем его. (В этом случае а был единственным элементом в дереве.)

Случай 2. Если / - сын узла, имеющего трех сыновей, удаляем его.

Случай 3. Если / - сын узла, имеющего двух сыновей sal, то может быть одно из двух:

а) / - корень; удаляем / и / и делаем корнем второго сына s;

б) / - не корень. Допустим, что / имеет брата ) слева от себя. Случай, когда брат находится справа, рассматривается аналогично. Если у g только два сына, делаем узел s самым правым сыном узла g, удаляем / и рекурсивно вызываем процедуру удаления, чтобы удалить /. Если у g три сына, то самого правого сына делаем левым сыном узла / и удаляем /.

Пример 4.11. Из 2-3-дерева на рис. 4.28 удалим элемент 4. Лист с меткой 4 является сыном узла с, у которого два сына. Поэтому делаем лист с меткой 5 самым правым сыном узла Ь, удаляем лист с меткой 4 и затем рекурсивно удаляем узел с.

Узел с - сын узла а, у которого два сына. Узел а - правый брат узла а. Поэтому по симметрии делаем b самым левым сыном узла а, удаляем с и затем рекурсивно удаляем а.




Рис. 4.31. Дерево с рис. 4.28 после удаления элемента 4.

Узел а - сын корня. Применяя случай За, делаем а корнем остающегося дерева (рис. 4.31). □

Формальную детализацию процесса, а также доказательство того, что на 2-3-дереве с п листьями его можно выполнить не более чем за O(logn) шагов, оставляем в качестве упражнения.

Итак, операции ПРИНАДЛЕЖАТЬ, ВСТАВИТЬ и УДАЛИТЬ на 2-3-дереве с п листьями можно вьшолнить не более чем за О (log л) шагов. Следовательно, 2-3-дерево может служить словарем с производительностью O(nlogn), ибо оно может обеспечить выполнение последовательности из п операций ПРИНАДЛЕЖАТЬ, ВСТАВИТЬ и УДАЛИТЬ не более чем за O(nlogn) шагов.

Исследуем теперь операцию M1N. Наименьший элемент в 2-3-дереве расположен в самом левом листе, который, конечно, можно найти за О (log п) шагов. Поэтому любую последовательность из п операций ВСТАВИТЬ, УДАЛИТЬ и M1N можно с помощью 2-3-дерева вьшолнить за время O(nlogn). Тем самым обосновано наше утверждение о том, что 2-3-дерево может служить для реализации очереди с приоритетами с производительностью O(nlogn). Для этой же цели годятся также сортирующее дерево, используемое в алгоритме Сортдеревом, и АВЛ-дерево, обсуждаемое в упр. 4.30- 4.33.

4.11. СЛИВАЕМЫЕ ДЕРЕВЬЯ

В данном разделе мы познакомимся со структурой данных, с помощью которой можно выполнить последовательность из операций ВСТАВИТЬ, УДАЛИТЬ, ОБЪЕДИНИТЬ и M1N за время O(nlogn). В этой структуре, которую можно воспринимать как обобщение сортирующего дерева, рассмотренного в разд. 3.4, множество элементов 5 представляется 2-3-деревом Т. Каждый элемент из S появляется в виде метки листа дерева Т, но множество листьев не упорядочено, как это было в двух предыдущих разделах. Каждый внутренний узел дерева Т пометим значением НАИМЕНЬ-ШИЙ[и], т. е. значением наименьшего элемента, хранящегося в





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