4.11. СЛИВАЕМЫЕ ДЕРЕВЬЯ

В данном разделе мы познакомимся со структурой данных, с помощью которой можно выполнить последовательность из операций ВСТАВИТЬ, УДАЛИТЬ, ОБЪЕДИНИТЬ и MIN за время В этой структуре, которую можно воспринимать как обобщение сортирующего дерева, рассмотренного в разд. 3.4, множество элементов 5 представляется Каждый элемент из появляется в виде метки листа дерева но множество листьев не упорядочено, как это было в двух предыдущих разделах. Каждый внутренний узел дерева пометим значением т. е. значением наименьшего элемента, хранящегося в

поддереве с корнем Для этого применения не нужны.

Наименьший элемент множества можно найти, если следующим образом двигаться вниз по дереву начиная от его корня. Находясь во внутреннем узле переходим к сыну узла помеченному наименьшим значением функции НАИМЕНЬШИЙ. Следовательно, если содержит листьев, то операция MIN занимает шагов.

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

Рис. 4.32. Процедура ИМПЛАНТАЦИЯ.

всякий раз, когда выполняется операция ВСТАВИТЬ, но это требует не более шагов.

Коль скоро лист I удален из надо для каждого его подлинного предка пересчитать значения функции НАИМЕНЬШИЙ. Новым значением для будет наименьшее из значений для двух или трех сыновей узла Если всегда пересчитывать снизу вверх, то индукцией по числу пересчетов можно показать, что каждое вычисление дает для функции НАИМЕНЬШИЙ правильный ответ. Так как эта функция меняется только в предках удаленного листа, то операцию УДАЛИТЬ можно выполнить за шагов.

Изучим операцию ОБЪЕДИНИТЬ. Каждое множество представлено отдельным Чтобы слить два множества вызываем процедуру приведенную на рис. 4.32, где это представляющие

Пусть высота дерева не меньше высоты дерева находит на самом правом пути в узел с высотой и делает корень дерева его самым правым братом. Если у его отца окажется четыре сына, ИМПЛАНТАЦИЯ вызовет процедуру Значения функции НАИМЕНЬШИЙ на узлах, потомки которых изменяются в процессе выполнения процедуры ИМПЛАНТАЦИЯ, можно скорректировать тем же способом, что и в операции УДАЛИТЬ.

В качестве упражнения предлагаем показать, что процедура ИМПЛАНТАЦИЯ соединяет в одно 2-3-дерево за время Если учитывать время на корректировку значений то процедура ИМПЛАНТАЦИЯ может занять времени.

Рассмотрим теперь приложение, в котором естественно возникают операции ОБЪЕДИНИТЬ, MIN и УДАЛИТЬ.

Пример 4.12. В примере 4.1 мы изложили алгоритм для нахождения остовных деревьев наименьшей стоимости. Он формировал из узлов все большие и большие множества, такие, что элементы каждого из них соединялись ребрами, выбранными для остовного дерева наименьшей стоимости. Стратегия нахождения новых ребер для этого остовного дерева состояла в том, чтобы перебирать ребра (сначала наименьшей стоимости) и проверять, соединяют ли они какие-нибудь еще не соединенные узлы.

Рассмотрим другую стратегию. Для каждого множества узлов V,- будем хранить множество всех нерассмотренных ребер,

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

Для реализации этого алгоритма надо сначала образовать для каждого узла множество инцидентных ему ребер. Чтобы среди ребер, инцидентных узлам из найти нерассмотренное ребро наименьшей стоимости, применим MIN-оператор к множеству нерассмотренных ребер для Затем удалим из найденное так ребро Если окажется, что имеет в только один конец, а другой лежит в множестве отличном от то выполним операцию ОБЪЕДИНИТЬ для (например, используя структуру данных алгоритма 4.3), а также для

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

Вначале для каждого узла образуем 2-3-дерево, содержащее все инцидентные ему ребра. Чтобы построить такое дерево, начнем с листьев. Затем добавим узлы высоты 1, так объединяя листья в группы по два или три, чтобы групп из двух листьев было не больше двух. Сделав это, вычислим для каждого узла высоты 1 наименьшую стоимость листа-потомка. Затем соберем узлы высоты 1 в группы по два или три и будем продолжать процесс до тех пор, пока на некотором уровне не образуется один узел, а именно корень. Время, затрачиваемое на такое построение дерева, пропорционально числу листьев. Реализация остальной части алгоритма теперь должна быть очевидна. Общее время работы составляет где число всех ребер.