Связать/срезать дерево
-
Структура дерева связей/разрезов
- Дерево связей/разрезов представляет лес, состоящий из корневых деревьев.
- Операции включают добавление, удаление и связывание узлов.
- Каждое дерево разбивается на пути, представленные вспомогательными деревьями.
-
Предпочтительные пути
- Доступ к узлу изменяет предпочтительный путь.
- Предпочтительный дочерний элемент — последний дочерний элемент на пути доступа.
- Предпочтительное ребро соединяет предпочтительный дочерний элемент с узлом.
-
Операции
- FindRoot: находит корень дерева, содержащего узел.
- Cut: удаляет дерево в узле.
- Link: связывает деревья, добавляя ребро.
- Path: выполняет агрегатную функцию для всех узлов на пути.
-
Анализ операций
- Вырезка и привязка имеют стоимость O(1) плюс доступ.
- FindRoot имеет амортизированную верхнюю границу O(log n) плюс доступ.
- Path может возвращать информацию за постоянное время плюс доступ.
-
Тяжелое-легкое разложение
- Ребро называется тяжелым, если размер поддерева > 1/2 размера родительского поддерева.
- Глубина освещенности ≤ lg n.
- Каждое изменение предпочтительного ребра приводит к формированию нового предпочтительного ребра.
-
Верхняя граница
- Операция расширения доступа дает log n.
- Количество обращений должно быть привязано к log n для доказательства верхней границы O(log 2 n).
-
Изменение ребер в дереве
- На любом заданном пути не более log n ребер являются светлыми.
- Количество тяжелых ребер, которые становятся предпочтительными, может быть O(n) для любой операции, но это O(log n) амортизированный.
- В ходе серии операций количество тяжелых ребер, которые становятся предпочтительными, равно количеству тяжелых ребер, которые не были выбраны на предыдущем шаге.
-
Улучшение до O(log n)
- Количество предпочтительных дочерних изменений равно O(log n).
- Если каждое предпочтительное дочернее изменение имеет амортизированную стоимость O(1), то операция доступа также будет O(log n).
- Это достигается с помощью потенциального метода.
-
Применение деревьев связей/разрезов
- Деревья связей/разрезов могут использоваться для решения проблемы динамической связности ациклических графов.
- Они также могут быть использованы для увеличения времени работы алгоритма Диника с O(V^2E) до O(VE log V).