Динамические деревья

Ключевые слова и синонимы: алгоритм Слейтора-Тарьяна

Постановка задачи

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

Основные результаты

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

Декомпозиция пути

Первая эффективная структура данных для динамического дерева была разработана Слейтором и Тарьяном; она известна как ST-дерево [13, 14], дерево со связыванием и отрезанием или просто динамическое дерево. Она была предназначена для представления корневых деревьев, однако пользователь может изменить корень дерева при помощи операции выворачивания (evert). Эта структура данных разбивает каждое входное дерево на пути с непересекающимися вершинами; каждый путь представляется в виде бинарного дерева поиска, в котором вершины появляются в симметричном порядке. Затем бинарные деревья соединяются в соответствии с тем, как пути соотносятся друг с другом в структуре леса. Точнее говоря, корень бинарного дерева становится средним потомком (в рамках структуры данных) родительского дерева (в лесу) самой верхней вершины соответствующего пути. В собственном бинарном дереве вершина может иметь не более двух потомков (левого и правого), однако при этом у нее может быть произвольное число средних потомков. Путь, включающий вершину (qlifcba на рисунке), должен быть открытым; он представлен в виде самого верхнего бинарного дерева. Все запросы, касающиеся путей, будут относиться к этому пути. Операция открытия (expose) может использоваться для того, чтобы сделать любую вершину частью открытого пути.

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

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

Стягивание дерева

В отличие от ST-деревьев, которые представляют входные деревья непосредственно, топологические деревья Фредериксона [6, 7, 8] представляют стягивание каждого дерева. Исходные вершины представляют собой 0 уровень стягивания. Уровень 1 представляет разбиение этих вершин на кластеры: вершина первой степени может комбинироваться только с ее соседом; вершины второй степени, смежные друг с другом, могут быть объединены в кластер; другие вершины остаются одиночными. Конечный результат представляет собой дерево меньшего размера, разбиение которого на кластеры дает уровень 2. Процесс продолжается до тех пор, пока не останется один кластер. Стягивание представлено в виде топологического дерева, в котором каждый кластер имеет потомков – кластеры, из которых он состоит на предыдущем уровне.

Топологическое дерево (согласно алгоритму из [7]). В левой части представлено исходное дерево и его многоуровневое разбиение; в правой части – соответствующее топологическое дерево.

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

Понятие стягивания дерева было независимо разработано Миллером и Рейфом [11] в контексте параллельных алгоритмов. Они предложили две базовые операции: обрезку (rake), которая удаляет вершины первой степени, и сжатие (compress), удаляющее вершины второй степени. Авторы показали, что O(log n) повторений этих операций достаточно для стягивания любого дерева в единственный кластер. Акар и коллеги преобразовали вариацию своего алгоритма в структуру данных в виде динамического дерева – RC-дерево [1], которое также можно рассматривать как рандомизированную и упрощенную версию топологического дерева.

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

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

Операции обрезки (rake) и сжатия (compress) в алгоритме, использующем верхушки деревьев [16]

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

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

Линеаризация

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

Нижние границы

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

Применение

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

Экспериментальные результаты

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

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

См. также

• Полностью динамическая связность
• Полностью динамическая связность: верхние и нижние границы
• Полностью динамическая высокая связность
• Полностью динамическая высокая связность в планарных графах
• Полностью динамические минимальные остовные деревья
• Полностью динамическая проверка на планарность
• Нижняя граница для динамической связности
• Маршрутизация

Литература

1. Acar, U.A., Blelloch, G.E., Harper, R., Vittes, J.L., Woo, S.L.M.: Dynamizing static algorithms, with applications to dynamic trees and history independence. In: Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 524-533. SIAM (2004)

2. Acar, U.A., Blelloch, G.E., Vittes, J.L.: An experimental analysis of change propagation in dynamic trees. In: Proceedings of the 7th Workshop on Algorithm Engineering and Experiments (ALENEX), pp.41-54 (2005)

3. Alstrup, S., Holm, J., de Lichtenberg, K., Thorup, M.: Minimizing diameters of dynamic trees. In: Proceedings of the 24th International Colloquium on Automata, Languages and Programming (ICALP), Bologna, Italy, 7-11 July 1997. Lecture Notes in Computer Science, vol. 1256, pp. 270-280. Springer (1997)

4. Alstrup, S., Holm, J.,Thorup, M., de Lichtenberg, K.: Maintaining information in fully dynamic trees with top trees. ACM Trans. Algorithms 1 (2), 243-264 (2005)

5. Bent, S.W., Sleator, D.D., Tarjan, R.E.: Biased search trees. SIAM J. Comput. 14(3), 545-568 (1985)

6. Frederickson, G.N.: Data structures for on-line update of minimum spanning trees, with applications. SIAM J. Comput. 14(4),781-798(1985)

7. Frederickson, G.N.: Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees. SIAM J. Comput. 26(2), 484-538 (1997)

8. Frederickson, G.N.: A data structure for dynamically maintaining rooted trees. J. Algorithms 24(1), 37-65(1997) 9. Goldberg, A.V., Grigoriadis, M.D., Tarjan, R.E.: Use of dynamic trees in a network simplex algorithm for the maximum flow problem. Math. Progr. 50,277-290 (1991)

10. Henzinger, M.R., King, V.: Randomized fully dynamic graph algorithms with polylogarihmic time per operation. In: Proceedings of the 27th Annual ACM Symposium on Theory of Computing (STOC), pp. 519-527 (1997)

11. Miller, G.L., Reif, J.H.: Parallel tree contraction and its applications. In: Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 478-489 (1985)

12. Patrajcu, M., Demaine, E.D.: Lower bounds for dynamic connectivity. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC), pp. 546-553 (2004)

13. Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. J. Comput. Syst. Sci. 26(3), 362-391 (1983)

14. Sleator, D.D., Tarjan, R.E.: Self-adjusting binary search trees. J. ACM 32(3), 652-686 (1985)

15. Tarjan, R.E.: Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm. Math. Prog. 78, 169-177(1997)

16. Tarjan, R.E., Werneck, R.F.: Self-adjusting top trees. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 813-822 (2005)

17. Tarjan, R.E., Werneck, R.F.: Dynamic trees in practice. In: Proceedings of the 6th Workshop on Experimental Algorithms (WEA). Lecture Notes in Computer Science, vol. 4525, pp. 80-93 (2007)

18. Werneck, R.F.: Design and Analysis of Data Structures for Dynamic Trees. Ph. D. thesis, Princeton University (2006)