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

Задача построения динамического дерева заключается в поддержке произвольного леса с 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] и впоследствии несколько упрощенные Тарьяном [15], используют иной подход к представлению динамических деревьев – линеаризацию. Она поддерживает [[эйлеров путь]] по каждому входному дереву: замкнутый путь, который проходит через каждую дугу дважды – по одному разу в обоих направлениях. Путь порождает линейный порядок на вершинах и ребрах и, следовательно, может быть представлен в виде сбалансированного бинарного дерева поиска. Связывание и отрезание дуг от леса соответствует присоединению и отщеплению затрагиваемых этими операциями бинарных деревьев и может быть выполнено за время O(log n). Линеаризация является, пожалуй, самым простым из трех подходов, однако у нее есть серьезный недостаток: поскольку каждая дуга встречается дважды, эта структура данных может собирать информацию только по деревьям, а не по путям.

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