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

редактировать

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

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

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

Содержание

1 Глоссарий
- 1.1 Граничный узел
- 1.2 Граничная вершина
  - 1.2.1 Внешние граничные вершины
- 1.3 Кластер
  - 1.3.1 Кластер путей
  - 1.3.2 Кластер точек
  - 1.3.3 Конечный кластер
  - 1.3.4 Пограничный кластер
    - 1.3.4.1 Конечный кластер
    - 1.3.4.2 Конечный кластер пути
- 1.4 Внутренний узел
- 1.5 Путь к кластеру
- 1.6 Объединяемые кластеры
2 Введение
3 Динамические операции
4 Внутренние операции
5 Нелокальный поиск
- 5.1 Примеры нелокального поиска
6 Интересные результаты и приложения
7 Реализация
- 7.1 Использование многоуровневого разбиения
8 Ссылки
9 Внешние ссылки

Глоссарий

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

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

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

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

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

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

Кластер

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

Path Cluster

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

Кластер точек

См. Концевой кластер

Концевой кластер

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

Пограничный кластер

Кластер, содержащий одно ребро, называется пограничным кластером.

Конечный кластер

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

Пограничный кластер пути

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

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

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

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

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

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

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

Введение

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

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

Обычно дерево $T {\ displaystyle {\ mathcal {T}}}$ ${\ mathcal {T}}$ может иметь вес на краях.

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

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

Следовательно, верхнее дерево $ℜ {\ displaystyle \ Re}$ $\ Re$ over ( $T, {\ displaystyle {\ mathcal {T}},}$ ${\ displaystyle {\ mathcal {T}},}$ $∂ T {\ displaystyle \ partial {T}}$ ${\ displaystyle \ partial {T}}$ ) представляет собой двоичное дерево, такое что

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

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

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

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

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

Ссылка (v, w): Где $v {\ displaystyle v}$ $v$ и $w {\ displaystyle w}$ $w$ - вершины в разных деревьях $T {\ displaystyle {\ mathcal {T}}}$ ${\ mathcal {T}}$ 1и $T {\ displaystyle {\ mathcal {T}}}$ ${\ mathcal {T}}$ 2. Он возвращает одно верхнее дерево, представляющее $ℜ {\ displaystyle \ Re}$ $\ Re$ v $∪ {\ displaystyle \ cup}$ $\ чашка$ $ℜ {\ displaystyle \ Re}$ $\ Re$ w $∪ (v, w) {\ displaystyle \ чашка {(v, w)}}$ ${\ displaystyle \ cup {(v, w)}}$
Cut (v, w) : удаляет край $(v, w) {\ displaystyle {(v, w)}}$ ${\ displaystyle {(v, w)}}$ из дерева $T {\ displaystyle {\ mathcal {T}}}$ ${\ mathcal {T}}$ с верхним деревом $ℜ, {\ displaystyle \ Re,}$ ${\ displaystyle \ Re,}$ тем самым превращая его в два деревья $T {\ displaystyle {\ mathcal {T}}}$ ${\ mathcal {T}}$ vи $T {\ displaystyle {\ mathcal {T}}}$ ${\ mathcal {T}}$ wи возвращение двух верхних деревьев $ℜ {\ displaystyle \ Re}$ $\ Re$ vи $ℜ {\ displaystyle \ Re}$ $\ Re$ w.
Expose (S) : вызывается как подпрограмма для реализации большинства запросов в верхнем дереве. $S {\ displaystyle S}$ $S$ содержит не более 2 вершин. Он превращает исходные внешние вершины в обычные вершины, а вершины из $S {\ displaystyle S}$ $S$ - в новые внешние граничные вершины верхнего дерева. Если $S {\ displaystyle S}$ $S$ непусто, он возвращает новый корневой кластер $C {\ displaystyle {\ mathcal {C}}}$ ${\ mathcal {C}}$ с $∂ С = S. {\ displaystyle \ partial {C} = S.}$ ${\ displaystyle \ partial {C} = S.}$ Expose ({v, w}) завершается неудачно, если вершины принадлежат разным деревьям.

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

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

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

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

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

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

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

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

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

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

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

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

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

Интересные результаты и приложения

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

([SLEATOR AND TARJAN 1983]). Мы можем поддерживать динамический сбор данных о весах. d деревьев за O (log ⁡ n) {\ displaystyle {\ mathcal {O}} (\ log n)}времени на ссылку и вырезание, поддерживая запросы о максимальном весе ребер между любыми двумя вершины за O (log ⁡ n) {\ displaystyle O (\ log n)}времени.
- Схема доказательства: он включает в себя поддержание на каждом узле максимального веса (max_wt) на пути его кластера, если это точечный кластер, то max_wt ( $C {\ displaystyle {\ mathcal {C}}}$ ${\ mathcal {C}}$ ) инициализируется как $- ∞. {\ displaystyle - \ infty.}$ ${\ displaystyle - \ infty.}$ Когда кластер представляет собой объединение двух кластеров, тогда это максимальное значение из двух объединенных кластеров. Если нам нужно найти максимальный вес между $v {\ displaystyle v}$ $v$ и $w {\ displaystyle w}$ $w$ , тогда мы делаем $C = {\ displaystyle {\ mathcal {C}} =}$ ${\ displaystyle {\ mathcal {C}} =}$ Раскройте $(v, w), {\ displaystyle (v, w),}$ ${\ displaystyle (v, w),}$ и сообщите max_wt $(C). {\ displaystyle ({\ mathcal {C}}).}$ ${\ displaystyle ({\ mathcal {C}}).}$
([SLEATOR AND TARJAN 1983]). В сценарии вышеуказанного приложения мы также можем добавить общий вес x {\ displaystyle x}ко всем ребрам на заданном пути v {\ displaystyle v}· · · w {\ displaystyle w}в O (log ⁡ n) {\ displaystyle {\ mathcal {O}} (\ log n)}время.
- Схема доказательства: мы вводим вес, называемый дополнительным ( $C {\ displaystyle {\ mathcal {C}}}$ ${\ mathcal {C}}$ ), который будет добавлен ко всем ребрам в $π (С). {\ displaystyle \ pi ({\ mathcal {C}}).}$ ${\ displaystyle \ pi ({\ mathcal {C}}).}$ Поддерживается надлежащим образом; split ( $C {\ displaystyle {\ mathcal {C}}}$ ${\ mathcal {C}}$ ) требует, чтобы для каждого дочернего пути $A {\ displaystyle {\ mathcal {A}}}$ ${\ mathcal {A}}$ из $C, {\ displaystyle {\ mathcal {C}},}$ ${\ displaystyle {\ mathcal {C}},}$ мы устанавливаем max_wt (A): = max_wt ( $A {\ displaystyle {\ mathcal {A}}) }$ ${\ mathcal {A}}$ ) + дополнительный ( $C {\ displaystyle {\ mathcal {C}}}$ ${\ mathcal {C}}$ ) и дополнительный ( $A {\ displaystyle {\ mathcal {A}} }$ ${\ mathcal {A}}$ ): = extra ( $A {\ displaystyle {\ mathcal {A}}}$ ${\ mathcal {A}}$ ) + extra ( $C {\ displaystyle {\ mathcal {C}) }}$ ${\ mathcal {C}}$ ). Для $C {\ displaystyle {\ mathcal {C}}}$ ${\ mathcal {C}}$ : = join ( $A, {\ displaystyle {\ mathcal {A}},}$ ${\ displaystyle {\ mathcal {A}},}$ $B {\ displaystyle {\ mathcal {B}}}$ ${\ mathcal {B}}$ ), мы устанавливаем max_wt ( $C {\ displaystyle {\ mathcal {C}}}$ ${\ mathcal {C}}$ ): = max {max_wt ( $A {\ displaystyle {\ mathcal {A}}}$ ${\ mathcal {A}}$ ), max_wt ( $B {\ displaystyle {\ mathcal {B}}}$ ${\ mathcal {B}}$ )} и дополнительные ( $C {\ displaystyle {\ mathcal {C}}}$ ${\ mathcal {C}}$ ): = 0. Наконец, чтобы найти максимальный вес на пути $v {\ displaystyle v}$ $v$ · · · $w, {\ displaystyle w,}$ ${\ displaystyle w,}$ мы устанавливаем $C {\ displaystyle {\ mathcal {C}}}$ ${\ mathcal {C}}$ : = Expose $( v, w) {\ displaystyle (v, w)}$ $(v, w)$ и возвращает max_wt ( $C {\ displaystyle {\ mathcal {C}}}$ ${\ mathcal {C}}$ ).
([GOLDBERG ET AL. 1991]). Мы можем запросить максимальный вес в базовом дереве, содержащем данную вершину v {\ displaystyle v}в O (log ⁡ n) {\ displaystyle {\ mathcal {O} } (\ log n)}время.
- Схема доказательства: это требует сохранения дополнительной информации о но максимальный вес некластерного края пути в кластере при операциях слияния и разделения.
Расстояние между двумя вершинами v {\ displaystyle v}и w {\ displaystyle w }можно найти в O (log ⁡ n) {\ displaystyle {\ mathcal {O}} (\ log n)}время как длина (Expose (v, вес) {\ displaystyle (v, w)}).
- Схема доказательства: мы будем поддерживать длину ( $C {\ displaystyle {\ mathcal {C}}}$ ${\ mathcal {C}}$ ) пути кластера. Длина сохраняется как максимальный вес, за исключением того, что если $C {\ displaystyle {\ mathcal {C}}}$ ${\ mathcal {C}}$ создается объединением (Merge), длина ( $C {\ displaystyle {\ mathcal {C}}}$ ${\ mathcal {C}}$ ) - это сумма длин, хранящихся вместе с его дочерними элементами пути.
Запросы относительно диаметра дерева и его последующего обслуживания занимают $O (log ⁡ n) {\ displaystyle {\ mathcal {O}} (\ log n)}$ ${\ mathcal {O}} (\ log n)$ time.
Центр и медиана могут поддерживаться с помощью операций Link (слияние) и Cut (разделение) и запрашиваться с помощью нелокального поиска в $O (log ⁡ n) {\ displaystyle {\ mathcal {O}} (\ log n)}$ ${\ mathcal {O}} (\ log n)$ time.
График можно поддерживать, позволяя чтобы обновить набор ребер и задать запросы о связности ребер 2. Амортизированная сложность обновлений составляет $O (log 4 ⁡ n) {\ displaystyle O (\ log ^ {4} n)}$ ${\ displaystyle O (\ log ^ {4} n)}$ . Запросы можно было реализовать еще быстрее. Алгоритм нетривиален, $I (C) {\ displaystyle I ({\ mathcal {C}})}$ ${\ displaystyle I ({\ mathcal {C}})}$ использует $Θ (log 2 ⁡ n) {\ displaystyle \ Theta ( \ log ^ {2} n)}$ $\ Theta (\ log ^ {2} n)$ пробел ([HOLM, LICHTENBERG, THORUP 2000]).
Граф можно поддерживать, позволяя обновлять набор ребер и запрашивать запросы на вершине 2 -соединение. Амортизированная сложность обновлений составляет $O (log 5 ⁡ n) {\ displaystyle O (\ log ^ {5} n)}$ ${\ displaystyle O (\ log ^ {5} n)}$ . Запросы можно было реализовать еще быстрее. Алгоритм нетривиален, $I (C) {\ displaystyle I ({\ mathcal {C}})}$ ${\ displaystyle I ({\ mathcal {C}})}$ использует $Θ (log 2 ⁡ n) {\ displaystyle \ Theta ( \ log ^ {2} n)}$ $\ Theta (\ log ^ {2} n)$ пробел ([HOLM, LICHTENBERG, THORUP 2001]).
Верхние деревья можно использовать для сжатия деревьев способом, который никогда не будет намного хуже, чем DAG сжатие, но может быть экспоненциально лучше.

Реализация

Верхние деревья были реализованы различными способами, некоторые из них включают реализацию с использованием многоуровневого разделения (верхние деревья и алгоритмы динамического графа Якоба Холма и Кристиана де Лихтенберга. Технический отчет), и даже с использованием деревьев ул. Слейатора-Тарьяна (обычно с амортизированными временными границами) (с наихудшими временными границами) (Alstrup et al. Информация в полностью динамических деревьях с верхними деревьями).

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

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

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

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

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

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

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

Ссылки

Стивен Алструп, Якоб Холм, Кристиан Де Лихтенберг и Миккель Торуп, Ведение информации в полностью динамических деревьях с верхними деревьями, Транзакции ACM по алгоритмам (TALG), Vol. 1 (2005), 243–264, doi : 10.1145 / 1103963.1103966
Стивен Альструп, Джейкоб Холм, Кристиан Де Лихтенберг и Миккель Торуп, Полилогарифмический детерминированный полностью динамические алгоритмы для подключения, минимального связующего дерева, 2-кромочного и двойного подключения, Journal of the ACM, Vol. 48 Выпуск 4 (июль 2001 г.), 723–760, doi : 10.1145 / 502090.502095
Дональд Кнут. Искусство программирования : фундаментальные алгоритмы, третье издание. Addison-Wesley, 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.

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