Верхушка дерева
-
Структура данных Верхнее дерево
- Основано на бинарном дереве для некорневых динамических деревьев
- Используется для операций, связанных с путями
- Дополнено для поддержания свойств дерева, таких как диаметр, центр и медиана
-
Определение и свойства
- Определяется для базового дерева T и набора внешних граничных вершин ∂T
- Внешние граничные вершины могут быть кластерами, представляющими все верхнее дерево
- Кластеры могут быть путями, точечными кластерами, гроздьями листьев, пограничными кластерами и кластерами ребер
-
Операции и обновления
- Ссылка(v, w) объединяет два дерева и возвращает новое верхнее дерево
- Вырезать(v, w) удаляет кромку из дерева и возвращает два новых верхних дерева
- Expose(S) создает новые внешние граничные вершины и возвращает новый корневой кластер
-
Внутренние операции
- Поглощать(A, B) объединяет два кластера и возвращает новый кластер
- Расщеплять(C) удаляет кластер и обновляет его дочерние элементы
- Создавать(v, w) создает кластер ради края (v, w)
- Искоренять(C) удаляет кластер из верхнего дерева
-
Нелокальный поиск
- Пользователь может выбрать кластер для поиска
- Черный ящик верхнего дерева обеспечивает поиск ребра на пересечении выбранных кластеров
- Поиск может быть ограничен определенным путем
-
Примеры нелокального поиска
- Нахождение i-го ребра на более длинном пути от v к w
- Поиск ребра на пути π(C)
-
Реализация функции Выбора
- Используется глобальная переменная для представления вершины и длины пути.
- Функция Choose выбирает кластер с длиной пути не менее заданной.
- Для поддержания длины пути необходимо поддерживать длину единицы измерения.
-
Поиск центра дерева
- Центр дерева можно найти, найдя двухцентровое ребро или ребро с центром в качестве одной конечной точки.
- Функция Clean требуется для распространения отложенного обновления.
-
Интересные результаты и приложения
- Схема проверки поддерживает максимальный вес на пути к кластеру.
- Схема доказательства поддерживает заданную длину пути к кластеру.
- Запросы, касающиеся диаметра дерева, требуют O(log n) времени.
-
Верхние деревья в динамической двусторонней связи
- Верхние деревья используются в современных алгоритмах для динамической двусторонней связи.
- Амортизированное время обновления составляет O(log^4 n), время запроса O(log n/log log n).
- Амортизированная сложность обновлений составляет O(log^5 n).
-
Реализация верхних деревьев
- Верхние деревья реализованы с использованием многоуровневого разбиения и динамических графовых алгоритмов.
- Амортизированные реализации имеют небольшие мультипликативные коэффициенты временной сложности.
- Наихудшие реализации ускоряют выполнение запросов за счет отключения ненужных обновлений.
-
Использование многоуровневого секционирования
- Многоуровневое секционирование позволяет представить дерево разделов кластера CPT(T).
- Стратегия разбиения на разделы важна для сохранения верхнего дерева в O(log n) время.
-
Полилогарифмические алгоритмы для связности и минимального остовного дерева
- Stephen Alstrup, Jacob Holm, Kristian De Lichtenberg, и Mikkel Thorup предложили полилогарифмические алгоритмы для задач связности, минимального остовного дерева, 2-edge и биконнектности.
- Эти алгоритмы являются полностью динамическими и детерминированными.
- Результаты опубликованы в Journal of the ACM в 2001 году.
-
Книги по алгоритмам
- Donald Knuth, The Art of Computer Programming: Fundamental Algorithms, Third Edition, Addison-Wesley, 1997.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, Second Edition, MIT Press and McGraw-Hill, 2001.
-
Дополнительные материалы
- Maintaining Information in Fully Dynamic Trees with Top Trees.
- Self-Adjusting Top Trees. Tarjan and Werneck, Proc. 16th SoDA, 2005.