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

третьего сына, если, конечно, есть третий сын. На рис. 5.6 показан пример 2-3 дерева. В этом и последующих примерах мы идентифицируем элементы с их ключевым полем, так что порядок элементов становится очевидным.



2J f 5J f 7

Рж. 5.6. 2-3 дерево

Отметим, что 2-3 дерево с k уровнями имеет от 2*" до 3*" листьев. Другими словами, 2-3 дерево, представляющее множество из п элементов, будет иметь не менее 1 -i- logan и не более 1 -i- logsi уровней. Таким образом, длины всех путей будут иметь порядок O(logra).

Мокно найти запись с ключом х в множестве, представленном 2-3 деревом, за время O(logra) путем простого перемещения по дереву, руководствуясь при этом значениями элементов, записанных во внутренних узлах. Во внутреннем узле node ключ X сравнивается со значением у наименьшего элемента, являющегося потомком второго сына узла node. (Напомним, что мы трактуем элементы так, как будто они состоят только из одного ключевого поля.) Если х < у, то перемещаемся к первому сыну узла node. Если х >у п узел node имеет только двух сьшовей, то переходим ко второму сыну узла node. Если узел node имеет трех сыновей я х > у, то сравниваем х со значением Z - вторым значением, записанным в узле node, т.е. со значением наименьшего элемента, являющегося потомком третьего сына узла node. Если х < г, то переходим ко второму сыну, если х > г, переходим к третьему сыну узла node. Таким способом в конце концов мы придем к листу, и элемент х будет принадлежать исходному множеству тогда и только тогда, когда он совпадает с элементом, записанным в листе. Очевидно, что если в процессе поиска получим х = у или х = г, поиск можно остановить. Но, конечно, алгоритм поиска должен предусмотреть спуск до самого листа.

Вставка элемента в 2-3 дерево

Процесс вставки нового элемента х в 2-3 дерево начинается так же, как и процесс поиска элемента х. Пусть мы уже находимся на уровне, предшествующем листьям, в узле node, чьи сыновья (уже проверено) не содержат элемента х. Если узел node имеет двух сыновей, то мы просто делаем элемент х третьим сыном, помещая его в правильном порядке среди других сыновей. Осталось переписать два числа в узле node в соответствии с новой ситуацией.

Например, если мы вставляем элемент 18 в дерево, показанное на рис. 5.6, то узлом node здесь будет самый правый узел среднего уровня. Помещаем элемент 18 среди сыновей этого узла, упорядочивая их как 16, 18 и 19. В узле node записываются числа 18 и 19, соответствующие второму и третьему сыновьям. Результат вставки показан на рис. 5.7.

Существуют другие разновидности 2-3 деревьев, когда во внутренний узел помещаются целые записи, как это делается в деревьях двоичного поиска.



7\ 7


Рис. 5.7. 2-3 дерево с вставленным элементом 18

Предположим, что элемент х будет четвертым, а не третьим сыном узла node. В 2-3 дереве узел не может иметь четырех сыновей, поэтому узел node разбивается на два узла, которые назовем node и node. Два наименьших элемента из четырех станут сыновьями нового узла node, а два наибольших элемента - сыновьями узла node. Теперь надо вставить узел node среди сыновей узла р - родителя узла node. Здесь ситуация аналогична вставке листа к узлу node. Так, если узел р имеет двух сыновей, то узел node становится третьим (по счету) сыном этого узла и помешается непосредственно справа от узла node. Если узел р уже имеет трех сыновей, то он разбивается на два узла р и р, узлу р приписываются два наименьших сына, а узлу р - оставшиеся. Затем рекурсивно вставляем узел р среди сыновей родителя узла р и т.д.


Рис. 5.8. Вставка элемента 10 в 2-3 дерево из рис. 5.7

Особый случай возникает при необходимости разбиения корня дерева. В этой ситуации создается новый корень, чьими сыновьями будут два узла, полученные в результате разбиения старого корня. Очевидно, в этом случае количество уровней 2-3 дерева возрастает на единицу.

Пример 5.4. Предположим, что надо вставить элемент 10 в дерево, показанное на рис. 5.7. Намеченный родитель для нового элемента уже имеет трех сыновей 7, 8 и 12, поэтому он разбивается на два узла. Первый узел будет иметь сыновей 7 и 8, а второй - 10 и 12. Результат этого разбиения показан на рис. 5.8,а. Теперь необходимо вставить новый узел (с сыновьями 10 и 12) среди сыновей корня дерева. С этим



узлом корень будет иметь четыре сына, поэтому он разбивается на два узла и образуется новый корень, как показано на рис. 5.8,6. Подробности реорганизации информации об элементах будут показаны далее при разработке программы для оператора INSERT. □

Удаление элемента из 2-3 дерева

При удалении листа может случиться так, что родитель node этого листа останется только с одним сыном. Если узел node является корнем, то единственный сын становится новым корнем дерева. Для случая, когда узел node не является корнем, обозначим его родителя как р. Если этот родитель имеет другого сына, расположённого слева или справа от узла node, и этот сын имеет трех сыновей, то один из них становится сыном узла node. Таким образом, узел node будет иметь двух сыновей.

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

Пример 5.5. Удалим элемент 10 из дерева, представленного на рис. 5.8,6. После удаления этого элемента его родитель будет иметь только одного сына. Но его "дедушка" имеет другого сына, у которого, в свою очередь, есть три сына: элементы 16, 18 и 19. Этот узел находится справа от неполного узла, поэтому лист с наименьшим элементом 16 переносится в неполный узел. В результате получим дерево, показанное на рис. 5.9,а.

Пусть далее надо удалить из полученного дерева элемент 7. После удаления его родитель будет иметь только одного сына 8, а его "дедушка" не имеет сыновей с тремя "детьми". Поэтому делаем элемент 8 "братом" элементов 2 и 5, как показано на рис. 5.9,6. На этом рисунке узел, помеченный звездочкой, имеет только одного сына, а его родитель не имеет сыновей с тремя "детьми". Поэтому мы удаляем помеченный узел, присоединяя его сына к узлу, расположенному справа от помеченного узла. Теперь корень будет иметь только одного сына, поэтому он также удаляется. В результате получим дерево, показанное на рис. 5.9,в.


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





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

0.0016