Динамические деревья: различия между версиями

Задача построения динамического дерева заключается в поддержке произвольного леса с n вершинами, который меняется со временем при помощи вставки дуг (связывания) и удаления дуг (отрезания). В зависимости от приложения, информация может быть ассоциирована с вершинами, дугами или обоими типами объектов. Запросы и обновления могут относиться к отдельным вершинам или дугам, однако чаще они относятся к целым путям или деревьям. В число типичных операций входят нахождение дуги минимальной стоимости в заданном пути, определение вершины с минимальной стоимостью в заданном дереве и добавление константного значения к стоимости каждой дуги на пути или каждой вершины дерева. Каждая из этих операций, равно как и операции связывания и отрезания, могут быть выполнены за время O(log n) на подходящих структурах данных.

ST-дерево (согласно алгоритму из [14]). В левой части представлено исходное дерево с корнем в вершине a, уже разбитое на пути; в правой части – текущая структура данных. Дуги, изображенные сплошными линиями, соединяют вершины одного и того же пути; изображенные пунктиром – соединяют разные пути

При использовании стандартных сбалансированных бинарных деревьев поиска (например, красно-черных деревьев) ST-деревья поддерживают операции динамического дерева с амортизированным временем исполнения <math>O(log^2 n)</math>. Это значение может быть улучшено до амортизированного времени O(log n) при помощи локально смещенных бинарных деревьев поиска, и до O(log n) в наихудшем случае – при помощи глобально смещенных бинарных деревьев поиска. Однако смещенные деревья поиска [5] сами по себе достаточно сложны. Более практичная реализация ST-деревьев использует [[косые деревья]] – самонастраивающиеся бинарные деревья поиска, поддерживающие все операции динамического дерева с амортизированным временем исполнения O(log n) [14].

Недостаток топологических деревьев и RC-деревьев заключается в том, что лес, на основе которого они строятся, должен иметь вершины с ограниченными (константными) степенями, чтобы гарантировать время O(log n) на исполнение операции. И хотя ST-деревья не имеют подобного ограничения при сборе информации по путям, им необходимы ограниченные степени для сбора информации по деревьям. Ограничения по степени могут быть обойдены при помощи «растроения» исходного леса (замены вершины с высокой степенью серией вершин с низкими степенями [9]), но при таком подходе возникают несколько специальных случаев.

«[[Верхушки деревьев]]», введенные Алструпом и коллегами [3, 4], не имеют подобных ограничений, в силу чего они позволяют охватить более общие случаи, чем все рассмотренные ранее структуры данных. Их кластеры также создаются при помощи процедуры стягивания дерева, однако они ведут себя скорее как дуги, чем как вершины. Кластер типа «сжатие» объединяет две дуги, имеющие общую вершину второй степени; кластер типа «обрезка» объединяет дугу, содержащую конечную точку первой степени, с дугой, дугой, смежной с ее второй конечной точкой.

Фактически верхушки деревьев были изначально предложены не как самостоятельные структуры данных, но как интерфейс над топологическими деревьями. Однако по соображениям эффективности хотелось бы иметь более прямую реализацию. Холм, Тарьян, Торуп и Вернек предложили концептуально простой автономный алгоритм обновления верхушки дерева после выполнения операции связывания или отрезания за время O(log n) в наихудшем случае [17]. Кроме того, Тарьян и Вернек предложили самонастраивающиеся верхушки деревьев [16] – более эффективную реализацию верхушек деревьев, основанную на декомпозиции путей: она разбивает исходный лес на пути с непересекающимися дугами, представляет эти пути в виде косых деревьев,

 

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

ET-деревья, предложенные Хензингером и Кингом [10] и впоследствии несколько упрощенные Тарьяном [ ], используют иной подход к представлению динамических деревьев – линеаризацию. Она поддерживает эйлеров путь по каждому входному дереву: замкнутый путь, который проходит через каждую дугу дважды – по одному разу в обоих направлениях. Путь порождает линейный порядок на вершинах и ребрах и, следовательно, может быть представлен в виде сбалансированного бинарного дерева поиска. Связывание и отрезание дуг от леса соответствует присоединению и отщеплению затрагиваемых этими операциями бинарных деревьев и может быть выполнено за время O(log n). Линеаризация является, пожалуй, самым простым из трех подходов, однако у нее есть серьезный недостаток: поскольку каждая дуга встречается дважды, эта структура данных может собирать информацию только по деревьям, а не по путям.

Структуры данных в виде динамических деревьев способны решать задачу динамической связности на ациклических графах, которая заключается в следующем: пусть даны две вершины, v и w; требуется определить, принадлежат ли они к одному и тому же дереву. Патраку и Демен [ ] доказали наличие нижней границы £?(log n) для этой задачи; это значение относится и к представленным структурам данных.

Вначале Слейтор и Тарьян использовали динамические деревья для алгоритма блокирующего потока Диница [   ]. Динамические деревья используются для поддержки леса ребер с положительной остаточной емкостью. Как только источник s и сток t становятся элементами одного и того же дерева, алгоритм посылает максимально возможный поток по пути s-t; это снижает до нуля остаточную емкость по меньшей мере одного ребра, которое затем можно отрезать от дерева. С тех пор было предложено несколько алгоритмов с максимальной и минимальной стоимостью потока, включающих динамические деревья (например, в [9, 15]). Динамические структуры данных (в особенности основанные на стягивании дерева) также широко используются в динамических графовых алгоритмах – таких как динамические версии построения минимальных остовных деревьев [6,10], связности [ ], двусвязности [ ] и двудольности [10]. В числе других областей применения можно упомянуть оценку динамических деревьев выражений [ ] и стандартные алгоритмы на графах [13].

 

Несколько исследований были посвящены эффективности различных структур данных на основе динамических деревьев; в большинстве случаев самыми быстрыми оказывались ST-деревья, реализованные на базе косых деревьев. В частности, Фредериксон обнаружил, что при выполнении операций с динамическими деревьями в алгоритме нахождения максимального потока топологическим деревьям требуется почти на 50% больше времени, чем ST-деревьям на основе косых деревьев [8]. Акар и коллеги [ ] показали, что RC-деревья оказываются существенно более медленными по сравнению с ST-деревьями на основе косых деревьев в случае, если большинство операций представляют собой связывание и отрезание (например, в алгоритмах обработки сетевых потоков), но быстрее в случаях, когда преобладают запросы и обновление значений. Причина в том, что при перекосе структура ST-деревьев меняется даже в процессе запроса, тогда как RC-деревья остаются неизменными.

Тарьян и Вернек [ ] представили экспериментальное сравнение нескольких структур данных на основе динамических деревьев. Для произвольных последовательностей операций связывания и отрезания косые ST-деревья демонстрируют максимальную скорость; за ними следуют косые ET-деревья, самонастраивающиеся верхушки деревьев, верхушки деревьев для наихудшего случая и RC-деревья. Подобные же данные об относительной эффективности были получены для более реалистичных последовательностей операций, за исключением таких, в которых число запросов существенно превышало число структурных операций; в таком случае самонастраивающиеся структуры данных оказываются более медленными по сравнению с RC-деревьями и верхушками деревьев для наихудшего случая. В этом же экспериментальном исследовании рассматривалась «очевидная» реализация ST-деревьев, явным образом представляющая лес и требующая линейного времени на операцию в наихудшем случае. В силу ее простоты она оказывается заметно более быстрой, чем структуры данных со временем O (log n), для запросов и обновлений, связанных с путями – за исключением случаев, когда длина путей измеряется сотнями вершин. В случаях, когда лес имеет очень большой диаметр или когда имеется необходимость в сборе информации по деревьям, а не только по путям, более полезными оказываются более изощренные решения.