Структуры данных и алгоритмы (1021739), страница 40
Текст из файла (страница 40)
Это поле назовем ключом. Например, если элементы множества — работники некоторого предприятия, то ключевым полем может быть поле, содержащее табельный номер или номер карточки социального страхования,В каждый внутренний узел записываются ключ наименьшего элемента, являющегося потомком второго сына, и ключ наименьшего элемента — потомка158ГЛАВА 5. СПЕЦИАЛЬНЫЕ МЕТОДЫ ПРЕДСТАВЛЕНИЯ МНОЖЕСТВтретьего сына, если, конечно, есть третий сын1.
На рис. 5.6 показан пример 2-3дерева. В этом и последующих примерах мы идентифицируем элементы с их ключевым полем, так что порядок элементов становится очевидным.Рис. 5.6. 2-3 деревоОтметим, что 2-3 дерево с k уровнями имеет от 2*"1 до З*"1 листьев. Другимисловами, 2-3 дерево, представляющее множество из п элементов, будет иметь неменее 1 + Iog3n и не более 1 + Iog2n уровней. Таким образом, длины всех путей будут иметь порядок O(logn).Можно найти запись с ключом х в множестве, представленном 2-3 деревом, завремя O(logra) путем простого перемещения по дереву, руководствуясь при этом значениями элементов, записанных во внутренних узлах.
Во внутреннем узле node ключх сравнивается со значением у наименьшего элемента, являющегося потомком второго сына узла 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.1Существуют другие разновидности 2-3 деревьев, когда во внутренний узел помещаютсяцелые записи, как это делается в деревьях двоичного поиска.5.4.
РЕАЛИЗАЦИЯ МНОЖЕСТВ ПОСРЕДСТВОМ СБАЛАНСИРОВАННЫХ...159Рис. 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) среди сыновей корня дерева. С этим160ГЛАВА 5. СПЕЦИАЛЬНЫЕ МЕТОДЫ ПРЕДСТАВЛЕНИЯ МНОЖЕСТВузлом корень будет иметь четыре сына, поэтому он разбивается на два узла и образуется новый корень, как показано на рис. 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,в.5 - 8 - 16 - 19 -,2) (5)(7)(8)(13(16)(18)(19)(2)(5)(8;(12) (1fабвРис. 5.9. Удаление элемента 7 из 2-3 дереваИз вышеприведенных примеров видно, что часто приходится манипулироватьзначениями внутренних узлов. Мы всегда сможем вычислить эти значения, если будем помнить наименьшие значения всех потомков узлов, составляющих путь от де5.4. РЕАЛИЗАЦИЯ МНОЖЕСТВ ПОСРЕДСТВОМ СБАЛАНСИРОВАННЫХ...161рева до удаляемого листа.
Эту информацию можно получить путем рекурсивногоприменения алгоритма удаления, вызываемого для каждого узла, составляющегопуть, который начинается от корня дерева. Возникающие при этом ситуации учтеныпри написании программы (см. далее), реализующей оператор DELETE. ПТипы данных для 2-3 деревьевОграничимся представлением (посредством 2-3 деревьев) множеств элементов, чьиключи являются действительными числами. Природа других полей, которые вместес полем key (ключ) составляют запись об элементе, пока не определена и здесь нас неинтересует; общий тип записи обозначим как elementtype.При написании программ на языке Pascal родители листьев должны быть записями, содержащими два поля действительных чисел (ключи наименьших элементовво втором и в третьем поддеревьях) и три поля указателей на элементы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
