4.10. СЛОВАРИ И ОЧЕРЕДИ С ПРИОРИТЕТАМИ

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

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

Если из узла выходит только два листа то делаем сыном узла Если то I делаем самым левым сыном узла и полагаем если то I делаем средним сыном узла и полагаем если то I делаем третьим сыном узла В последнем случае, возможно, надо будет изменить значения на некоторых подлинных предках узла

Пример 4.9. Если в 2-3-дерево, изображенное на рис. 4.27,а, вставляется элемент 2, то получается 2-3-дерево, изображенное на рис. 4.27,6.

Рис. 4.27. Вставка в 2-3-дерево: а — дерево перед вставкой; дерево после вставки элемента 2.

Теперь предположим, что уже есть три листа Сделаем I надлежащим сыном узла Теперь имеет четырех сыновей. Чтобы сохранить 2-3-свойство, образуем новый узел Два левых

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

Пример 4.10. Если в 2-3-дерево на рис. 4.27,а, вставляется элемент 4, то новый лист с меткой 4 надо сделать самым левым сыном узла с. Поскольку у с уже есть три сына, строим новый узел с. Затем делаем листья 4 и 5 сыновьями узла с, а листья 6 и 7 — сыновьями узла с. Теперь делаем с сыном узла а. Но поскольку у а уже есть три сына, строим новый узел а. Делаем узлы и с сыновьями старого узла а, а узлы сыновьями нового узла а. Наконец, образуем новый корень и делаем его сыновьями. Полученное дерево изображено на рис. 4.28.

Рис. 4.28. Дерево с рис. 4.27, а после вставки элемента 4.

Алгоритм 4.4. Вставка нового элемента в 2-3-дерево

Вход. Непустое с корнем и новый элемент

Выход. Преобразованное 2-3-дерево с новым листом, помеченным а.

Метод. По условию содержит хотя бы один элемент. Чтобы упростить описание алгоритма, опустим детали корректировки

1. Если состоит из единственного узла I с меткой образуем новый корень Образуем новый узел с меткой а. Делаем сыновьями корня причем I будет левым сыном, если и правым в противном случае.

2. Если содержит более одного узла, положим ; процедура ПОИСК приведена на рис. 4.29. Образуем новый

Рис. 4.29. Процедура

лист I с меткой а. Если два сына с метками то делаем I надлежащим сыном узла А именно, I будет левым сыном, если средним, если и правым, если Если три сына, делаем I надлежащим сыном узла а затем чтобы включить в узел/и его четырех сыновей, вызываем Процедура приведена на рис. 4.30. Чтобы учесть присутствие узла а, корректируем значения вдоль пути из а

Рис. 4.30. Процедура

в корень. Другие очевидные изменения, корректирующие значения производятся процедурой (здесь они опущены — предлагаем их в качестве упражнения).

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

Доказательство. Очевидная индукция по числу вызовов процедуры ПОИСК показывает, что новый лист становится сыном того узла, какого надо. Порядок исходных листьев не затрагивается. Что касается времени работы, то в силу леммы 4.6 высота листьями не превосходит Поскольку рекурсивно вызывает себя только на отце узла может произойти не более рекурсивных вызовов Каждый вызов занимает постоянное время, так что общее время не превосходит

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

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

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

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

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

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

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

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

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

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

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

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

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