1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 35
Текст из файла (страница 35)
4.44. СЛИВАЕМЫЕ ДЕРЕВЬЯ В данном разделе мы познакомимся со структурой данных, с помощью которой можно выполнить последовательность из операций ВСТАВИТЬ, УДАЛИТЬ, ОБЪЕДИНИТЬ и М1И за время 0(л 1ойл). В этой структуре, которую можно воспринимать как обобщение сортирующего дерева, рассмотренного в разд. 3.4, множество элементов 5 представляется 2-3-деревом Т. Каждый элемент из 5 появляется в виде метки листа дерева Т, ио множество листьев не упорядочеио, как это было в двух предьщущих разделах.
Каждый внутренний узел дерева Т пометим значением НАИМЕНЬШИЙ!В), т. е. значением наименьшего элемента, хранящегося в Еуа ГЛ. С СТРУКТУРЫ ДАННЫХ ДЛЯ ЗАДАЧ С МНОЖЕСТВАМИ поддереве с корнем п. Для этого применения 2-3-деревьев Т.(п) и А!(п) не нужны. Наименьший элемент множества 5 можно найти, если следующим образом двигаться вниз по дереву Т, начиная от его корня. Находясь во внутреннем узле п, переходим к сыну узла и, помеченному наименьшим значением функции НАИМЕНЬШИЙ. Следовательно, если Т содержит а листьев, то операция М!Ы занимает О(!одп) шагов. Во многих приложениях всякий раз, когда надо удалить из о какой-то элемент, он всегда наименьший, Но если мы хотим удалить из 5 произвольный элемент, мы должны уметь найти лист, содержащий его.
В тех приложениях, где элементы можно представить целыми числами 1, 2,..., л, можно пронумеровать сами листья. Если же элементы произвольны, то можно воспользоваться вспомогательным 2-3-словарем, листья которого содержат указатели на листья дерева Т. С помощью этого словаря можно достичь произвольного листа за О (1оя а) шагов. Словарь надо корректировать ргосебпге ИМПЛАНТАЦИЯ(Т„Те): И ВЫСОТА(Т,) = ВЫСОТА(Т,) Гйеп Ьей!и образовать новый корень г; сделать КОРЕНЬ(Тг1 и КОРЕНЬ(Та1 соответственно левым и правым сыновьями узла г; епг! е)зе и !д положнм ВЫСОТА(Т,) > ВЫСОТА(Т,) о!Ьегтп!зе переставить Т, с Т, и "левый" с "правым" !и Ьен!и пусть п — такой узел на самом правом пути в Т„что ГЛУБИНА(и) = ВЫСОТА(Т,) — ВЫСОТА(Т,); пусть у — отец узла и; сделать КОРЕНЬ|Та! сыном узла у, расположенным непосредственно справа от и; В у у сейчас четыре сына !Ьеп ДОБАВСЪ|НА(у)') ент! й Если нам нужны значення с н М для нового узла, образованного процедурой ДОВАВСЫНА(/), то сначала надо найти нанбольшего потомка узла ь, следуя по пути.
идущему в самый правый ласт. Рнс. 4.3УА Процедура ИМПЛАНТАЦИЯ. йуй «ЛЕ СЛИВАЕЫЫЕ ДЕРЕВЬЯ всякий раз, когда выполняется операция ВСТАВИТЬ, но это требует не более О(!опл) шагов. Коль скоро лист 1 удален из Т„надо для каждого его подлинного предка о пересчитать значения функции НАИМЕНЬШИЙ. Новым значением для НАИМЕНЬШИЙ!а! будет наименьшее из значений НАИМЕНЬШИЙЫ для двух или трех сыновей з узла ш Если всегда пересчитывать снизу вверх, то индукцией по числу пересчетов можно показать, что каждое вычисление дает для функции НАИМЕНЬШИЙ правильный ответ. Так как эта функция меняется только в предках удаленного листа, то операцию УДАЛИТЬ можно выполнить за 0(!ода) шагов. Изучим операцию ОБЪЕДИНИТЬ. Каждое множество представлено отдельным 2-3-деревом.
Чтобы слить два множества 5, и 5„вызываем процедуру ИМПЛАНТАЦИЯ (Ты Т,), приведенную на рис. 4.32, где Т, и Т, — это 2-3-деревья, представляющие 5, и 5,'). Пусть высота й, дерева Т, не меньше высоты й, дерева Т», ИМПЛАНТАЦИЯ находит на самом правом пути в Т, узел п с высотой й, и делает корень дерева Т» его самым правым братом. Если у его отца у окажется четыре сына, ИМПЛАНТАЦИЯ вызовет процедуру ДОБАВСЫНА (у).
Значения функции НАИМЕНЬШИЙ на узлах, потомки которых изменяются в процессе выполнения процедуры ИМПЛАНТАЦИЯ, можно скорректировать тем же способом, что и в операции УДАЛИТЬ. В качестве упражнения предлагаем показать, что процедура ИМПЛАНТАЦИЯ соединяет Т» и Т, в одно 2-3-дерево за время 0(й,— й,) (при й,>й»). Если учитывать время на корректировку значений т'. и М, то процедура ИМПЛАНТАЦИЯ может занять 0(МАХ (1оя!!5»!1, 1оя(!5»(!)) времени. Рассмотрим теперь приложение, в котором естественно возникают операции ОБЪЕДИНИТЬ, М1!Ь) и УДАЛИТЬ. Пример 4.!2.
В примере 4.1 мы изложили алгоритм для нахождения остовных деревьев наименьшей стоимости, Он формировал из узлов все большие и ббльшие множества, такие, что элементы каждого из них соединялись ребрами, выбранными для остовного дерева наименьшей стоимости. Стратегия нахождения новых ребер для этого остовногодерева состояла в том, чтобы перебирать ребра (сначала наименьшей стоимости) и проверять, соединяют ли они какие-нибудь еще не соединенные узлы. Рассмотрим другую стратегию. Для каждого множества узлов 1', будем хранить множество Е; всех нерассмотренных ребер, нн- ') Здесь различие между «левым» и «правым» неважно; оно сделано ради сиепляемыи очередей, которые обсуждаются в следуюпьем разделе.
»77 гл, ь стггктугы длнных для злдлч с множяствлми цидентных каким-то узлам в Уь Если выбрать не рассмотренное ранее ребро е, инцидентное узлу из относительно малого множества Уь то другой конец ребра е с большой вероятностью не будет лежать в У„и можно будет добавить е к остовному дереву. Если это нерассмотренное ребро е обладает наименьшей стоимостью среди всех ребер, инцидентных узлам из У,, то можно показать, что включение его в остовное дерево приведет к остовному дереву наименьшей стоимости.
Для реализации этого алгоритма надо сначала образовать для каждого узла множество инцидентных ему ребер. Чтобы среди ребер, инцидентных узлам из Уь найти нерассмотренное ребро наименьшей стоимости, применим М1Ы-оператор к множеству Е; нерассмотренных ребер для Уь Затем удалим из Е, найденное так ребро е. Если окажется, что е имеет в У, только один конец, а другой лежит в множестве У;, отличном от У» то выполним операцию ОБЪЕДИНИТЬ для У, и У; (например, используя структуру данных алгоритма 4.3), а также для Е~ и Е;. В качестве структуры данных для представления каждого множества ребер Е~ можно взять 2-3-дерево, каждый лист которого помечен ребром и его стоимостью. На множестве ребер иет никакого специального порядка. Каждому нелисту приписана наименьшая стоимость его потомков-листьев, обозначаемая НАИМЕНЬШИЙ(п!.
Вначале для каждого узла образуем 2-3-дерево, содержащее все инцидентные ему ребра. Чтобы построить такое дерево, начнем с листьев. Затем добавим узлы высоты 1, так объединяя листья в группы по два или три, чтобы групп из двух листьев было не больше двух. Сделав это, вычислим для каждого узла высоты 1 наименьшую стоимость листа-потомка. Затем соберем узлы высоты 1 в группы по два или три и будем продолжать процесс до тех пор, пока на некотором уровне не образуется один узел, а именно корень.
Время, затрачиваемое на такое построение дерева, пропорционально числу листьев. Реализация остальной части алгоритма теперь должна быть очевидна. Общее время работы составляет 0(е1ойа), где е — число всех ребер. Г) 4.12. СЦЕПЛЯЕМЫЕ ОЧЕРЕДИ В разд. 4.10 было показано, как на 2-3-дереве с п листьями выполнить каждую из операций ВСТАВИТЬ, УДАЛИТЬ, М11ч и ПРИНАДЛЕЖАТЬ за время 0(1ойп), если пользоваться значениями Е и М.
Сейчас покажем, как за время О(!ояп) выполнить каждую из операций СЦЕПИТЬ и РАСЦЕПИТЬ. Снова будем предполагать, что элементы расположены на листьях 2-3-дерева в порядке возрастания слева направо и для каждого узла о вычисляются значения Т,!п) и М[п). !тз а,иь сцепляемые Очеведи Рис. 4.33. Расиеплеиие 2-3-дерева. Операции СЦЕПИТЬ(5„5,) на вход подаются такие две последовательности 5, и 5„что каждый элемент из 5, меньше каждого элемента из 5;, на выход она выдает конкатенацию этих последовательносте, овательностей, т. е.
5,5,. Если 5, и 5, представлены соот- и т и Т в тс венно 2-3-деревьями Т, и Т„то мы хотим соединить Т, и дно дерево Т, листьями которого являются листья дерева ев Т в одно дерев в их первоначальном порядке и следующие за ними листья дере ва Т, в их первоначальном порядке. Это можно осуществить, вызвав процедуру ИМПЛАНТАЦИЯ(Т„Т,), приведенную на рис, 4.32. Наконец, рассмотрим операцию РАСЦЕПИТЬ. Напомним, что операция РАСЦЕПИТЬ(а, 5) разбивает 5 на два множества 5,= =(ЫЬ(а и ЬЕ5) и 5,=(Ь!Ь а и ЬЕ5). Для ее реализации определим процедуру ДЕЛЕНИЕ (а, Т), которая расцепляет 2-3- дерево Т на два такие 2-3-дерева Т, и Т„что метки всех листьев в Т, не больше а, а метки всех листьев в Т, больше а.
Метод можно неформально описать следующим образом. Дано 2-3-дерево Т, содержащее элемент а, Идем по пути из корня в лист с меткой а. Этот путь разбивает наше дерево на поддеревья, корнямп которых служат не сами узлы, лежащие на нем, а их сыновья. Это иллюстрирует рис. 4.33, где слева от пути находятся деревья Т, Т„Т, и тривиальное дерево, состоящее из одного узла ап ь а справа — деревья Т„ Т, и пь Деревья слева от рассматриваемого пути и дерево, состоящее из одного узла а, соединяются с помощью только что описанного алгоритма конкатенации деревьев.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
