1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 34
Текст из файла (страница 34)
Однако для выполнения операций типа УДАЛИТЬ нужен механизм для определения положения листа, представляющего данный элемент. Если элементами множества являются целые числа из фиксированной области„скажем от 1 до и, то лист, представляющий элемент 1, можно находить с помощью (-й ячейки некоторого массива. Если же элементы рассматриваемых множеств принадлежат некоторому большому универсальному множеству, то лист, представляющий элемент 1, можно находить с помощью вспомогательного словаря. Рассмотрим следующие наборы операций. 1) ВСТАВИТЬ, УДАЛИТЬ, ПРИНАДЛЕЖАТЬ. 2) ВСТАВИТЬ, УДАЛИТЬ, М1)ч). 3) ВСТАВИТЬ, УДАЛИТЬ, ОБЪЕДИНИТЬ, М1(ч).
4) ВСТАВИТЬ, УДАЛИТЬ, НАЙТИ, СЦЕПИТЬ, РАСЦЕПИТЬ. Структуру данных, обеспечивающую выполнение операций из множестна 1, будем называть словарем, из множества 2 — очередью с приоритетами, из множества 3 — сливов иым деревом, из множества 4 — сцепляемой очередью. Покажем, что 2-3-деревья могут служить для реализации словарей, очередей с приоритетами, сцепляемых очередей н сливаемых деревьев, применение которых обеспечивает выполнение и операций за время 0(п )ойп). с~о, словдии и очипеди с приоритетами Развитая здесь техника достаточно мощна, чтобы выполнить последовательности, составленные из любого совместного подмножества семи операций, перечисленных в начале главы.
Единственная несовместность состоит в том, что операция ОБЪЕДИНИТЬ приводит к неупорядоченному множеству, а РАСЦЕПИТЬ и СЦЕПИТЬ предполагают наличие порядка. 4.40. СЛОВАРИ И ОЧЕРЕДИ С ПРИОРИТЕ1АМИ В этом разделе мы изучим основные преобразования, требуемые для реализации словарей и очередей с приоритетами. На протяжении всего раздела будем предполагать, что элементы приписаны листьям 2-3-дерева в порядке слева направо и в каждом нелисте и определены функции 1.[п1 и М[п[, введенные в предыдущем разделе.
Чтобы в 2-3-дерево вставить новый элемент а, надо найти место для нового листа 1, который будет содержать а. Для этого ищут элемент а в дереве. Если дерево содержит более одного элемента, то поиск а окончится в узле 7, имеющем двух или трех сыновей, которые являются листьями. Если из узла 7' выходит только два листа 1, и 1„ то 1 делаем сыном Узла 7'. Если а(Е[[т1 т1, то 1 делаем самым левым сыном Узла 7 и полагаем 7.[11=а и М[71=Е[1т1; если Е[[т[(а(Е[[в[, то 1 делаем средним сыном узла у и полагаем М[71=а; если Е[[а[(а, то 1 делаем третьим сыном узла 7'. В последнем случае, возможно, надо будет изменить значения Т. и М на некоторых подлинных предках узла 7. Пример 4.9.
Если в 2-3-дерево, изображенное на рис. 4.27,а, вставляется элемент 2, то получается 2-3-дерево, изображенное на рис. 4.27,б. П а б Рис. 4.27. Вставка в 2-3.дерево: а — дерево перед вставкой; б — дерево после вставки элемента 2. Теперь предположим, что у 1 уже есть три листа 1„1, и 1з. Сделаем 1 надлежащим сыном узла у'. Теперь 7 имеет четырех сыновей. Чтобы сохранить 2-3-свойство, образуем новый узел д. Два левых т) Е[п1 — элемент, приписанный узлу и.
йтй гл. с стпуктупы длиных для злдлч с множяствлми сына оставим сыновьями узла 1, а два правых переделаем в сыновей узла д. Затем сделаем д братом узла г", сделав его сыном отца узла г. Если отец узла 1 имел двух сыновей, то на этом мы остановимся. Если же трех, то надо рекурсивно повторять эту процедуру до тех пор, пока у всех узлов в дереве останется не более трех сыновей. Если у корня окажется четыре сына, образуем новый корень с двумя новыми сыновьями, каждый из которых будет иметь в качестве двух своих сыновей двух из четырех сыновей старого корня. Пример 4.10.
Если в 2-3-дерево на рис. 4.27,а, вставляется элемент 4, то новый лист с меткой 4 надо сделать самым левым сыном узла с, Поскольку у с уже есть три сына, строим новый узел с'. Затем делаем листья 4 и 5 сыновьями узла с, а листья 6 и 7 — сыновьями узла с'. Теперь делаем с' сыном узла а. Но поскольку у а уже есть три сына, строим новый узел а'. Делаем узлы Ь и с сыновьями старого узла а, а узлы с' и д — сыновьями нового узла а'.
Наконец, образуем новый корень г и делаем а и а' его сыновьями. Полученное дерево изображено иа рис. 4.28. П Рнс. 4.2а. Дерево с рнс. 4.27, а поеле встввкн элемента 4. Алгоритм 4.4. Вставка нового элемента в 2-3-дерево Вход. Непустое 2-3-дерево Т с корнем г и новый элемент а ~ Т. Выход. Преобразованное 2-3-дерево с новым листом, помеченным а. Менад. По условию Т содержит хотя бы один элемент.
Чтобы упростить описание алгоритма, опустим детали корректировки 1. и М. 1. Если Т состоит из единственного узла 1 с меткой Ь, образуем новый корень г'. Образуем новый узел о с меткой а. Делаем! и о сыновьями корня г', причем 1 будет левым сыном, если Ь(а, и правым в противном случае.
2. Если Т содержит более одного узла, положим Г"=ПОИСК(а, г); процедура ПОИСК приведена на рис. 4.29. Образуем новый 1рл 110, слОВАРи и ОчеРеди с ИРиооитетдми ргоседнге ПОИСК(а, г): Н любой сын узла г является листом 1Ьеп ге1цгп г е)ае Ьея|п пусть з; будет 1-м сыном узла г; П а -Цг] |йеп ге1пгп ПОИСК(а, Е1) е!зе Н у г два сына или а(М(г] 1Ьеп ге1цгп ПОИСК(а, з,) е!Ее ге1игп ПОИСК(а, з,) епд Рес. 4.29.
Процедуре ПОИСК. лист 1 с меткой а. Если у ) два сына с метками Ь, и Ь„то делаем 1 надлежащим сыном узла 1. А именно, 1 будет левым сыном, если а(Ь„средним, если Ь1(а<Ь„И правым, если Ь,(а. Если у у три сына, делаем 1 надлежащим сыном узла |, а затем чтобы включить в Т узел1и его четырех сыновей, вызываем ДОБАВСЫНА(1). Процедура ДОБАВСЫНА приведена на рис. 4.30. Чтобы учесть присутствие узла а, корректируем значения 1, и М вдоль пути из а ргосее)пге ДОБАВСЫНА (о): Ьен|п образовать новый узел о', сделать двух самых правых сыновей узла о левым и правым сыновьями узла о', Н у о нет отца 1Ьеп Ьея|п образовать новый корень г; сделать о левым, а и' правым сыном корня г епе( е|зе Ьен)п пусть 1 — отец узла о; сделать о' сыном узла 1, расположенным непосредственно справа от о; 11 теперь у 1 четыре сына 1Ьеп ДОБАВСЪ|НА(1) епд епб Рес.
4.30. Процедура ДОБАВСЫНА. 1УЗ гл. с структуры дднных для здддч с множвствдми в корень з). Другие очевидные изменения, корректирующие значения Б и М, производятся процедурой ДОБАВСЫНА (здесь они опущены — предлагаем их в качестве упражнения). С) Теорема 4.6.
Алгоритм 4.4 вставляет новый элемент в 2-3- дерево с и листьями за время, не превосходящее 0(!оя и). Более того, этот алгоритм сохраняет порядок исходных листьев и структуру 2-3-дерева. Д о к а з а те л ь с т в о. Очевидная индукция по числу вызовов процедуры ПОИСК показывает, что новый лист становится сыном того узла, какого надо.
Порядок исходных листьев не затрагивается. Что касается времени работы, то в силу леммы 4,6 высота 2-3-дерева с и листьями не превосходит 1оя и. Поскольку ДОБАВСЫНА(о) рекурсивно вызывает себя только на отце узла о, может произойти не более 1ояп рекурсивных вызовов Каждый вызов ДОБАВСЫНА занимает постоянное время, так что общее время не превосходит О(!опп). П Элемент а можно удалить из 2-3-дерева способом, по существу обратным к вставке. Пусть а — метка листа 1.
Рассмотрим отдельно три случая. Случай 1. Если 1 — корень, удаляем его. (В этом случае а был единственным элементом в дереве.) Случай 2. Если 1 — сын узла, имеющего трех сыновей, удаляем его. Случай 3. Если 1 — сын узла, имеющего двух сыновей в и 1, то может быть одно из двух: а) 1 — корень; удаляем 1 и ) и делаем корнем второго сына э; б) 1 — не корень. Допустим, что 1 имеет брата ') слева от себя. Случай, когда брат находится справа, рассматривается аналогично. Если у д только два сына, делаем узел в самым правым сыном узла и, удаляем 1 и рекурсивно вызываем процедуру удаления, чтобы удалить 1. Если у д три сына, то самого правого сына делаем левым сыном узла) и удаляем 1, Пример 4.11.
Из 2-3-дерева иа рис. 4.28 удалим элемент 4. Лист с меткой 4 является сыном узла с, у которого два сына. Поэтому делаем лист с меткой 5 самым правым сыном узла Ь, удаляем лист с меткой 4 и затем рекурсивно удаляем узел с. Узел с — сын узла а, у которого два сына. Узел а' — правый брат узла а. Г!озтому по симметрии делаем (з самым левым сыном узла а', удаляем с и затем рекурсивио удаляем а. ') достаточно пройтн путь от а до такого узла, что а — не наибольший зземент а гго поддереве.
з) два узла с одним огном аазмваюгсз брпгпьялгп. тул 4.!1. СЛИВАЕМЫЕ ДЕРЕВЬЯ Ряс. 4.31. Дерево с ряс. 4.28 после удаления элемента 4. Узел а — сын корня. Применяя случай За, делаем а' корнем остающегося дерева (рис. 4.31). С) Формальную детализацию процесса, а также доказательство того, что на 2-3-дереве с л листьями его можно выполнить ие более чем за 0(!ой л) шагов„оставляем в качестве упражнения. Итак, операции ПРИНАДЛЕЖАТЬ, ВСТАВИТЬ и УДАЛИТЬ на 2-3-дереве с л листьями можно выполнить не более чем за 0(!ой л) шагов. Следовательно, 2-3-дерево может служить словарем с производительностью 0(л !ой л), ибо оно может обеспечить выполнение последовательности из л операций ПРИНАДЛЕЖАТЬ, ВСТАВИТЬ и УДАЛИТЬ ие более чем за 0(л !ой л) шагов. Исследуем теперь операцию М!!!.
Наименьший элемент в 2-3- дереве расположен в самом левом листе, который, конечно, можно найти за О(!ой л) шагов. Поэтому любую последовательность из л операций ВСТАВИТЬ, УДАЛИТЬ и М1М можно с помощью 2-3- дерева выполнить за время 0(л!одл). Тем самым обосновано наше утверждение о том, что 2-3-дерево может служить для реализации очереди с приоритетами с производительностью 0 (л 1ой л). Для этой же цели годятся также сортирующее дерево, используемое в алгоритме Сортдеревом, и АВЛ-дерево, обсуждаемое в упр. 4.30— 4.33.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
