Верхнее дерево

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

Верхнее дерево $\Re$ определяется для базового дерева ${\mathcal {T}}$ и набор $\partial {T}$ не более двух вершин, называемых внешними граничными вершинами

Изображение, изображающее верхнее дерево, построенное на основе нижележащего дерева (черные узлы). Дерево, разделенное на реберные кластеры, и полное верхнее дерево для него. Заполненные узлы в верхнем дереве представляют собой кластеры путей, а узлы маленьких кругов — это кластеры листьев. Узел большого круга является корнем. Заглавные буквы обозначают кластеры, непрописные — узлы.

Глоссарий

Граничный узел

См. Граничная вершина.

Граничная вершина

Вершина в связном поддереве является граничной вершиной, если она соединена ребром с вершиной вне поддерева.

Внешние граничные вершины

До пары вершин в верхнем дереве $\Re$ могут называться внешними граничными вершинами, их можно рассматривать как граничные вершины кластера, который представляет все верхнее дерево.

Кластер

Кластер — это связное поддерево, имеющее не более двух граничных вершин .Набор граничных вершин данного кластера ${\mathcal {C}}$ обозначается как $\partial {C}.$С каждым кластером ${\mathcal {C}}$ пользователь может связать некоторую метаинформацию $I({\mathcal {C}}),$ и дать методы для его поддержания при различных внутренних операциях .

Кластер путей

Если $\pi ({\mathcal {C}})$ содержит хотя бы одно ребро, тогда ${\mathcal {C}}$ называется кластером путей .

Скопление точек

См. кластер листьев.

Скопление листьев

Если $\pi ({\mathcal {C}})$ не содержит ребер, т.е. ${\mathcal {C}}$ имеет только одну граничную вершину, тогда ${\mathcal {C}}$ называется кластером листьев .

Граничный кластер

Кластер, содержащий одно ребро, называется Edge Cluster .

Скопление краев листьев

Лист в исходном кластере представлен кластером только с одной граничной вершиной и называется кластером ребер листа .

Кластер границ пути

Краевые кластеры с двумя граничными узлами называются граничными кластерами пути .

Внутренний узел

Узел в ${\mathcal {C}}$ \ $\partial {C}$ называется внутренним узлом ${\mathcal {C}}.$

Путь к кластеру

Путь между вершинами граничными ${\mathcal {C}}$ называется кластера путем ${\mathcal {C}}$ и это обозначается $\pi ({\mathcal {C}}).$

Объединяемые кластеры

Два кластера ${\mathcal {A}}$ и ${\mathcal {B}}$ имеет возможность слияния, если ${\mathcal {A}}\cap {\mathcal {B}}$ является одноэлементным набором (они имеют ровно один общий узел) и ${\mathcal {A}}\cup {\mathcal {B}}$ является кластером.

Введение

Верхние деревья используются для поддержания динамического леса (набора деревьев) при операциях связывания и вырезания.

Основная идея — поддерживать сбалансированное двоичное дерево. $\Re$ логарифмической высоты количества узлов в исходном дереве ${\mathcal {T}}$(т.е. в ${\mathcal {O}}(\log n)$ время) ; по верхнее дерево существу представляет собой рекурсивное подразделение исходного дерева ${\mathcal {T}}$ в кластеры .

В общем, дерево ${\mathcal {T}}$ может иметь вес по краям.

Существует взаимно однозначное соответствие ребрам исходного дерева. ${\mathcal {T}}$ и конечные узлы верхнего дерева $\Re$ и каждый внутренний узел $\Re$ представляет собой кластер, образующийся в результате объединения кластеров, являющихся его дочерними элементами.

Структура данных верхнего дерева может быть инициализирована в ${\mathcal {O}}(n)$ время.

Поэтому верхнее дерево $\Re$ над ( ${\mathcal {T}},$ $\partial {T}$) — бинарное дерево такое, что

• Узлы $\Re$ представляют собой кластеры ( ${\mathcal {T}},$ $\partial {T}$ );
• Листья $\Re$ являются краями ${\mathcal {T}};$
• Родственные кластеры являются соседями в том смысле, что они пересекаются в одной вершине, а их родительский кластер является их объединением.
• Корень $\Re$ это дерево ${\mathcal {T}}$ сам по себе, с набором не более двух внешних граничных вершин.

Дерево с одной вершиной имеет пустую вершину, а дерево, имеющее только ребро, представляет собой всего лишь один узел.

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

Динамические операции

Следующие три — это обновления леса, разрешенные пользователем.

• Ссылка(v, w): Где $v$ и $w$ это вершины в разных деревьях ${\mathcal {T}}$₁ и ${\mathcal {T}}$₂ . Он возвращает одно верхнее дерево, представляющее $\Re$_v $\cup$$\Re$_В $\cup {(v,w)}$
• Cut(v, w) : удаляет край. ${(v,w)}$ с дерева ${\mathcal {T}}$ с верхушкой дерева $\Re ,$ тем самым превратив его в два дерева ${\mathcal {T}}$_в и ${\mathcal {T}}$_w и возвращение двух верхних деревьев $\Re$_в и $\Re$_В .
• Expose(S) : вызывается как подпрограмма для реализации большинства запросов к верхнему дереву. $S$ содержит не более 2 вершин. Он делает исходные внешние вершины нормальными вершинами и превращает вершины из $S$ новые внешние граничные вершины верхнего дерева. Если $S$ непусто, он возвращает новый корневой кластер ${\mathcal {C}}$ с $\partial {C}=S.$ Expose({v,w}) терпит неудачу, если вершины принадлежат разным деревьям.

Внутренние операции

Все обновления леса выполняются в последовательности не более ${\mathcal {O}}(\log n)$ Внутренние операции, последовательность которых рассчитывается далее. ${\mathcal {O}}(\log n)$ время. Может случиться так, что во время обновления дерева листовой кластер может измениться на кластер путей и наоборот. Обновления верхнего дерева выполняются исключительно этими внутренними операциями.

The $I({\mathcal {C}})$ обновляется путем вызова определяемой пользователем функции, связанной с каждой внутренней операцией.

• Объединить $({\mathcal {A}},{\mathcal {B}}){:}$ Здесь ${\mathcal {A}}$ и ${\mathcal {B}}$ являются объединяемыми кластерами , он возвращает ${\mathcal {C}}$ в качестве родительского кластера ${\mathcal {A}}$ и ${\mathcal {B}}$ и с граничными вершинами в качестве граничных вершин ${\mathcal {A}}\cup {\mathcal {B}}.$ Вычисляет $I({\mathcal {C}})$ с использованием $I({\mathcal {A}})$ и $I({\mathcal {B}}).$
• Расколоть $({\mathcal {C}}){:}$ Здесь ${\mathcal {C}}$ это корневой кластер ${\mathcal {A}}\cup {\mathcal {B}}.$ Он обновляет $I({\mathcal {A}})$ и $I({\mathcal {B}})$ с использованием $I({\mathcal {C}})$ и чем он удаляет кластер ${\mathcal {C}}$ от $\Re$.

Разделение обычно реализуется с помощью Clean $({\mathcal {C}})$ метод, который вызывает пользовательский метод для обновлений $I({\mathcal {A}})$ и $I({\mathcal {B}})$ с использованием $I({\mathcal {C}})$ и обновления $I({\mathcal {C}})$ так, что известно, что в его дочерних элементах не требуется ожидающих обновлений. Чем ${\mathcal {C}}$ отбрасывается без вызова пользовательских функций. Clean часто требуется для запросов без необходимости Split .Если Split не использует подпрограмму Clean, а Clean требуется, ее эффекта можно добиться с накладными расходами, комбинируя Merge и Split .

Следующие две функции аналогичны двум предыдущим и используются для базовых кластеров.

• Создавать $(v,w){:}$ Создает кластер ${\mathcal {C}}$ за край $(v,w).$ Наборы $\partial {C}=\partial$$(v,w).$ $I({\mathcal {C}})$ рассчитывается с нуля.
• Искоренить $({\mathcal {C}}){:}$ ${\mathcal {C}}$ это краевой кластер $(v,w).$ Пользовательская функция вызывается для обработки $I({\mathcal {C}})$ и чем кластер ${\mathcal {C}}$ удаляется из верхнего дерева.

Нелокальный поиск

Пользователь может определить Выбрать $({\mathcal {C}}){:}$ операция, которая для корневого (нелистового) кластера выбирает один из его дочерних кластеров. Черный ящик верхнего дерева обеспечивает поиск $({\mathcal {C}}){:}$ подпрограмма, которая организует запросы выбора и реорганизацию верхнего дерева (с использованием внутренних операций) таким образом, чтобы найти единственное ребро на пересечении всех выбранных кластеров. Иногда поиск следует ограничить путем. Для таких целей существует вариант нелокального поиска.Если в корневом кластере есть две внешние граничные вершины ${\mathcal {C}}$, ребро ищется только на пути $\pi ({\mathcal {C}})$. Достаточно сделать следующее изменение: Если только один из дочерних элементов корневого кластера является кластером путей, он выбирается по умолчанию без вызова операции Choose .

Примеры нелокального поиска

Нахождение i-го ребра на более длинном пути из $v$ к $w$ может быть сделано ${\mathcal {C}}$=Expose({v,w}), за которым следует Search( ${\mathcal {C}}$) с соответствующим выбором . Для реализации Choose мы используем глобальную переменную, представляющую $v$ и глобальная переменная, представляющая $i.$ Выбрать выбирает кластер ${\mathcal {A}}$ с $v\in \partial {A}$ если и только если длина $\pi ({\mathcal {A}})$ по крайней мере $i$. Для поддержки операции длина должна поддерживаться в $I$.

Аналогичную задачу можно сформулировать для графа с ребрами неединичной длины. В этом случае расстояние может относиться к ребру или вершине между двумя рёбрами. Мы могли бы определить Choose так, чтобы в последнем случае возвращалось ребро, ведущее к вершине. Можно определить обновление, увеличивающее длину всех ребер вдоль пути на константу. В таком сценарии эти обновления выполняются в постоянное время только в корневом кластере. Очистка необходима для распространения отложенного обновления среди детей. Clean следует вызывать до Choose вызова . Чтобы сохранить длину в $I$ в этом случае потребуется поддерживать единичную длину в $I$ также.

Нахождение центра дерева, содержащего вершину $v$ можно сделать, найдя либо бицентрическое ребро, либо ребро с центром в качестве одной конечной точки. Край можно найти с помощью ${\mathcal {C}}$=Expose({v}), за которым следует Search( ${\mathcal {C}}$) с соответствующим выбором . Выбор выбирает между детьми ${\mathcal {A}},$ ${\mathcal {B}}$ с $a\in \partial {A}\cap \partial {B}$ ребенок с более высоким максимальным расстоянием $(a)$. Для поддержки операции максимальное расстояние в поддереве кластера от граничной вершины должно поддерживаться в $I$. Это также требует поддержания длины пути кластера.

и

Ряд интересных приложений, изначально реализованных другими методами, теперь легко реализован с использованием интерфейса верхнего дерева. Некоторые из них включают

• ([СЛИТОР И ТАРДЖАН 1983]). Мы можем поддерживать динамическую коллекцию взвешенных деревьев в ${\mathcal {O}}(\log n)$ время на соединение и разрез, поддерживая запросы о максимальном весе ребра между любыми двумя вершинами в $O(\log n)$ время.
  • Схема доказательства: оно предполагает поддержание на каждом узле максимального веса (max_wt) на его пути к кластеру. Если это кластер точек, то max_wt( ${\mathcal {C}}$) инициализируется как $-\infty .$ Когда кластер представляет собой объединение двух кластеров, это максимальное значение двух объединенных кластеров. Если нам нужно найти максимальную массу между $v$ и $w$ тогда мы делаем ${\mathcal {C}}=$ Разоблачать $(v,w),$ и сообщите max_wt $({\mathcal {C}}).$
• ([СЛИТОР И ТАРДЖАН 1983]). В сценарии вышеприведенного приложения мы также можем добавить общий вес $x$ ко всем ребрам на заданном пути $v$ · · · $w$ в ${\mathcal {O}}(\log n)$ время.
  • Схема доказательства: мы вводим вес, называемый extra( ${\mathcal {C}}$), который будет добавлен ко всем ребрам в $\pi ({\mathcal {C}}).$ Который поддерживается надлежащим образом; расколоть( ${\mathcal {C}}$) требует, чтобы для каждого дочернего элемента пути ${\mathcal {A}}$ из ${\mathcal {C}},$ мы устанавливаем max_wt(A) := max_wt( ${\mathcal {A}}$) + дополнительно( ${\mathcal {C}}$) и дополнительно( ${\mathcal {A}}$) := дополнительно( ${\mathcal {A}}$) + дополнительно( ${\mathcal {C}}$). Для ${\mathcal {C}}$ := присоединяюсь( ${\mathcal {A}},$ ${\mathcal {B}}$), мы устанавливаем max_wt( ${\mathcal {C}}$) := max {max_wt( ${\mathcal {A}}$), max_wt( ${\mathcal {B}}$)} и дополнительно( ${\mathcal {C}}$) := 0. Наконец, чтобы найти максимальный вес на пути $v$ · · · $w,$ мы устанавливаем ${\mathcal {C}}$ := Разоблачить $(v,w)$ и верните max_wt( ${\mathcal {C}}$).
• ([ГОЛДБЕРГ И др., 1991]). Мы можем запросить максимальный вес в базовом дереве, содержащем данную вершину. $v$ в ${\mathcal {O}}(\log n)$ время.
  • Схема доказательства: для этого требуется сохранение дополнительной информации о ребре некластерного пути максимального веса в кластере при операциях слияния и разделения.
• Расстояние между двумя вершинами $v$ и $w$ можно найти в ${\mathcal {O}}(\log n)$ время как длина(Expose $(v,w)$).
  • Схема доказательства: мы будем поддерживать длину длины ( ${\mathcal {C}}$) пути кластера. Длина сохраняется как максимальный вес, за исключением того, что если ${\mathcal {C}}$ создается путем соединения(Merge), length( ${\mathcal {C}}$) — это сумма длин, хранящихся вместе с дочерними элементами пути.
• Вопросы по диаметру дерева и последующему его уходу принимаются ${\mathcal {O}}(\log n)$ время.
• Центр и Медиана могут поддерживаться с помощью операций Link(Merge) и Cut(Split) и запрашиваться с помощью нелокального поиска в ${\mathcal {O}}(\log n)$ время.

• Верхние деревья используются в современных алгоритмах динамической двусторонней связности . В этой задаче, как и в случае с динамической связностью , граф подвержен удалениям и вставкам ребер, а также запросам, спрашивающим, соединена ли пара вершин двумя ребрами или существует ли мост, разделяющий их. Хольм , де Лихтенберг и Торуп дать детерминированный алгоритм с амортизированным временем обновления $O(\log ^{4}n)$, и $O(\log n/\log \log n)$ время запроса. Последующая работа Холма , Ротенберга и Торупа улучшила это значение до амортизированного времени обновления. $O(\log ^{2}n\log ^{2}\log n)$, также используя верхние деревья

• Граф можно поддерживать, позволяя обновлять набор ребер и задавать запросы о связности вершин 2. Амортизированная сложность обновлений $O(\log ^{5}n)$. Запросы можно было бы реализовать еще быстрее. Алгоритм не тривиален, $I({\mathcal {C}})$ использует $\Theta (\log ^{2}n)$ космос.

• Верхние деревья можно использовать для сжатия деревьев способом, который никогда не будет намного хуже, чем сжатие DAG , но может быть экспоненциально лучше.

Реализация

Деревья вершин были реализованы различными способами, некоторые из них включают реализацию с использованием многоуровневого разделения (верхние деревья и алгоритмы динамических графов Джейкоб Холм и Кристиан де Лихтенберг. Технический отчет) и даже с использованием деревьев Слеатора-Тарьяна (обычно с амортизированными временными границами), Топологические деревья Фредериксона (с наихудшими временными границами) (Алструп и др. Поддержание информации в полностью динамических деревьях с верхними деревьями).

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

Использование многоуровневого секционирования

Любое разбиение кластеров дерева ${\mathcal {T}}$ может быть представлено деревом разделов кластера CPT. $({\mathcal {T}}),$ путем замены каждого кластера в дереве ${\mathcal {T}}$ по краю. Если мы используем стратегию P для разделения ${\mathcal {T}}$ тогда CPT будет CPT _P ${\mathcal {T}}.$ Это делается рекурсивно, пока не останется только одно ребро.

Мы бы заметили, что все узлы соответствующего верхнего дерева $\Re$ однозначно отображаются на краях этого многоуровневого раздела. В многоуровневом разделе могут быть некоторые ребра, которые не соответствуют ни одному узлу верхнего дерева. Это ребра, которые представляют только один дочерний элемент на уровне ниже него, то есть простой кластер. Только ребра, соответствующие составным кластерам, соответствуют узлам верхнего дерева. $\Re .$

Стратегия разделения важна при разделении дерева. ${\mathcal {T}}$ в кластеры. Только осторожная стратегия гарантирует, что мы окажемся в ${\mathcal {O}}(\log n)$ высота многоуровневого раздела (и, следовательно, верхнего дерева).

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

Приведенная выше стратегия секционирования обеспечивает сохранение верхнего дерева в ${\mathcal {O}}(\log n)$ время.

См. также

• Связать/вырезать дерево
• Дерево Эйлеровой башни
• Динамический алгоритм
• Динамическое подключение

Ссылки

• Стивен Альструп, Джейкоб Холм, Кристиан Де Лихтенберг и Миккель Торуп , Поддержание информации в полностью динамических деревьях с верхними деревьями , Транзакции ACM в алгоритмах (TALG), Vol. 1 (2005), 243–264, дои : 10.1145/1103963.1103966
• Стивен Альструп, Джейкоб Холм, Кристиан Де Лихтенберг и Миккель Торуп , Полилогарифмические детерминированные полностью динамические алгоритмы для связности, минимального остовного дерева, 2-ребра и двусвязности , Журнал ACM, Vol. 48, выпуск 4 (июль 2001 г.), 723–760, дои : 10.1145/502090.502095
• Дональд Кнут . Искусство компьютерного программирования : фундаментальные алгоритмы , третье издание. Аддисон-Уэсли, 1997. ISBN   0-201-89683-4 . Раздел 2.3: Деревья, стр. 308–423.
• Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Стейн . Введение в алгоритмы , второе издание. MIT Press и McGraw-Hill, 2001. ISBN   0-262-03293-7 . Раздел 10.4: Представление деревьев с корнями, стр. 214–217. Главы 12–14 (Двоичные деревья поиска, красно-черные деревья, расширение структур данных), стр. 253–320.

Внешние ссылки

• Хранение информации в полностью динамических деревьях с верхними деревьями. Альструп и др.
• Саморегулирующиеся верхние деревья. Тарьян и Вернек, Proc. 16-я конференция SoDA, 2005 г.