yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->5.4. Реализация множеств посредством сбалансированных деревьев

Алгоритмы структуры данных

5.4. Реализация множеств посредством сбалансированных деревьев

В разделах 5.1 и 5.2 мы рассмотрели способы представления множеств посредством деревьев двоичного поиска и узнали, что операторы, подобные INSERT, выполняются за время, пропорциональное средней длине пути в этом дереве. Затем мы показали, что средняя глубина узлов составляет O(logn) для "случайного" дерева из га узлов. Однако некоторые последовательности операций вставки и удаления узлов дерева могут привести к деревьям двоичного поиска, чья средняя глубина будет пропорциональна п. Это наводит на мысль попытаться после каждой вставки или удаления реорганизовать дерево так, чтобы оно всегда было полно, тогда время выполнения оператора INSERT и других подобных операторов всегда будет иметь порядок O(logn).

На рис. 5.5,а показано дерево из шести узлов, а на рис. 5.5,6 — то же дерево (уже полное) после вставки седьмого узла с элементом 1. Но обратите внимание, что каждый узел на рис. 5.5,6 имеет другого родителя, отличного от родителя, изображенного на рис. 5.5,а. Отсюда следует, что надо сделать га шагов при вставке элемента 1, чтобы сохранить дерево по возможности сбалансированным. Это значительно хуже, чем в случае простой вставки в полное дерево двоичного поиска при реализации словарей, очередей с приоритетами и других АТД, где оператор INSERT (и другие ему подобные) требует времени порядка O(logn).

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

1.    Каждый внутренний узел имеет или два, или три сына.

2.    Все пути от корня до любого листа имеют одинаковую длину.

Будем считать, что пустое дерево и дерево с одним узлом также являются 2-3 деревьями.

Рассмотрим представления множеств, элементы которых упорядочены посредством некоторого отношения линейного порядка, обозначаемого символом "<". Элементы множества располагаются в листьях дерева, при этом, если элемент а располагается левее элемента b, справедливо отношение а < b. Предполагаем, что упорядочивание элементов по используемому отношению линейного порядка основывается только на значениях одного поля (среди других полей записи, содержащей информацию об элементе), которое формирует тип элементов. Это поле назовем ключом. Например, если элементы множества — работники некоторого предприятия, то ключевым полем может быть поле, содержащее табельный номер или номер карточки социального страхования.

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

Отметим, что 2-3 дерево с k уровнями имеет от 2k-1 до Зk-1 листьев. Другими словами, 2-3 дерево, представляющее множество из п элементов, будет иметь не менее 1 + log3n и не более 1 + log2n уровней. Таким образом, длины всех путей будут иметь порядок O(logn).

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

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

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

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

 

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

Особый случай возникает при необходимости разбиения корня дерева. В этой ситуации создается новый корень, чьими сыновьями будут два узла, полученные в результате разбиения старого корня. Очевидно, в этом случае количество уровней 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,в.

Из вышеприведенных примеров видно, что часто приходится манипулировать значениями внутренних узлов. Мы всегда сможем вычислить эти значения, если будем помнить наименьшие значения всех потомков узлов, составляющих путь от дерева до удаляемого листа. Эту информацию можно получить путем рекурсивного применения алгоритма удаления, вызываемого для каждого узла, составляющего путь, который начинается от корня дерева. Возникающие при этом ситуации учтены при написании программы (см. далее), реализующей оператор DELETE.

 

73