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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В целом дерево может иметь нагрузку на края.${\displaystyle {\mathcal {T}}}$

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

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

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

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

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

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

Ниже приведены три допустимых пользователем обновления леса.

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

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

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

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

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

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

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

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

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

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

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

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

• ([SLEATOR AND TARJAN 1983]). Мы можем поддерживать динамическую коллекцию взвешенных деревьев во времени для каждой ссылки и разреза, поддерживая запросы о максимальном весе ребра между любыми двумя вершинами во времени.${\displaystyle {\mathcal {O}}(\log n)}$${\displaystyle O(\log n)}$
  • Схема доказательства: Она включает в себя поддержание в каждом узле максимального веса (max_wt) на его кластерном пути, если это точечный кластер, то max_wt( ) инициализируется как Когда кластер является объединением двух кластеров, то это максимальное значение двух объединенных кластеров. Если нам нужно найти максимальный вес между и , то мы делаем Expose и сообщаем max_wt${\displaystyle {\mathcal {C}}}$${\displaystyle -\infty .}$${\displaystyle v}$${\displaystyle w}$${\displaystyle {\mathcal {C}}=}$${\displaystyle (v,w),}$${\displaystyle ({\mathcal {C}}).}$
• ([SLEATOR AND TARJAN 1983]). В сценарии вышеприведенного приложения мы также можем добавить общий вес ко всем ребрам на заданном пути · · · во времени.${\displaystyle x}$${\displaystyle v}$${\displaystyle w}$${\displaystyle {\mathcal {O}}(\log n)}$
  • Схема доказательства: Мы вводим вес, называемый extra( ), который добавляется ко всем ребрам в , который поддерживается соответствующим образом; split( ) требует, чтобы для каждого дочернего пути мы установили max_wt(A) := max_wt( ) + extra( ) и extra( ) := extra( ) + extra( ). Для  := join( ) мы устанавливаем max_wt( ) := max {max_wt( ), max_wt( )} и extra( ) := 0. Наконец, чтобы найти максимальный вес на пути · · · мы устанавливаем  := Expose и возвращаем max_wt( ).${\displaystyle {\mathcal {C}}}$${\displaystyle \pi ({\mathcal {C}}).}$${\displaystyle {\mathcal {C}}}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {C}},}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {C}}}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {C}}}$${\displaystyle {\mathcal {C}}}$${\displaystyle {\mathcal {A}},}$ ${\displaystyle {\mathcal {B}}}$${\displaystyle {\mathcal {C}}}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {B}}}$${\displaystyle {\mathcal {C}}}$${\displaystyle v}$${\displaystyle w,}$${\displaystyle {\mathcal {C}}}$${\displaystyle (v,w)}$${\displaystyle {\mathcal {C}}}$
• ([GOLDBERG ET AL. 1991]). Мы можем запросить максимальный вес в базовом дереве, содержащем заданную вершину во времени.${\displaystyle v}$${\displaystyle {\mathcal {O}}(\log n)}$
  • Схема доказательства: Для этого требуется сохранение дополнительной информации о максимальном весе некластерного пути-ребра в кластере при операциях слияния и разделения.
• Расстояние между двумя вершинами можно найти за время как length(Expose ).${\displaystyle v}$${\displaystyle w}$${\displaystyle {\mathcal {O}}(\log n)}$${\displaystyle (v,w)}$
  • Схема доказательства: Мы будем поддерживать длину length( ) кластерного пути. Длина поддерживается как максимальный вес, за исключением того, что если создается с помощью join(Merge), length( ) является суммой длин, сохраненных с его потомками пути.${\displaystyle {\mathcal {C}}}$${\displaystyle {\mathcal {C}}}$${\displaystyle {\mathcal {C}}}$
• Запросы относительно диаметра дерева и его последующего ухода требуют времени.${\displaystyle {\mathcal {O}}(\log n)}$
• Центр и медиану можно сохранить с помощью операций «Связать» (Объединить) и «Разделить» (Разделить) и запросить с помощью нелокального поиска во времени.${\displaystyle {\mathcal {O}}(\log n)}$

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

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

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

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

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

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

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

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

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

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

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

• Стивен Альструп, Джейкоб Холм, Кристиан Де Лихтенберг и Миккель Торуп , Поддержание информации в полностью динамических деревьях с верхними деревьями , Транзакции ACM в алгоритмах (TALG), Vol. 1 (2005), 243–264, номер документа : 10.1145/1103963.1103966.
• Стивен Альструп, Якоб Холм, Кристиан Де Лихтенберг и Миккель Торуп , Полилогарифмические детерминированные полностью динамические алгоритмы для связности, минимального остовного дерева, 2-ребер и бисвязности , Журнал ACM, т. 48, выпуск 4 (июль 2001 г.), 723–760, doi :10.1145/502090.502095
• Дональд Кнут . Искусство программирования : основные алгоритмы , третье издание. Addison-Wesley, 1997. ISBN 0-201-89683-4 . Раздел 2.3: Деревья, стр. 308–423. 
• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest и Clifford Stein . Introduction to Algorithms , Second Edition. MIT Press и McGraw-Hill, 2001. ISBN 0-262-03293-7 . Раздел 10.4: Представление корневых деревьев, стр. 214–217. Главы 12–14 (Двоичные деревья поиска, красно-черные деревья, расширение структур данных), стр. 253–320. 

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