Связать/вырезать дерево

Связать/вырезать дерево
Связать/вырезать дерево
Тип	Дерево
Изобретенный	1982
Изобретён	Дэниел Доминик Слейтор ; Роберт Эндре Тарьян ;
Временная сложность в обозначении большого О

Дерево связей/вырезок — это структура данных , представляющая лес , набор корневых деревьев , и предлагает следующие операции:

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

Представленный лес может состоять из очень глубоких деревьев, поэтому, если мы представим лес как простую коллекцию родительских деревьев-указателей , нам может потребоваться много времени, чтобы найти корень данного узла. Однако, если мы представим каждое дерево в лесу как дерево связей/разрезаний, мы сможем определить, какому дереву принадлежит элемент, за O ( log (n)) амортизированное время . Более того, мы можем быстро подстроить коллекцию связанных/вырезанных деревьев под изменения представляемого леса. В частности, мы можем настроить его для объединения (связывания) и разделения (вырезания) за O (log( n амортизированное время )).

Деревья связей/вырезок делят каждое дерево в представленном лесу на непересекающиеся по вершинам пути, где каждый путь представлен вспомогательной структурой данных (часто деревья расширения , хотя исходная статья предшествует деревьям расширения и, таким образом, использует смещенные деревья двоичного поиска). Узлы вспомогательной структуры данных упорядочены по их глубине в соответствующем представленном дереве. В одном варианте, Naive Partitioning , пути определяются по путям и узлам, к которым последний раз обращались, аналогично деревьям танго . При разделении по размеру пути определяются самым тяжелым дочерним элементом (дочерним элементом с наибольшим количеством дочерних элементов) данного узла. Это дает более сложную структуру, но снижает стоимость операций с амортизированного O(log n) до худшего случая O(log n). Он используется для решения различных проблем сетевых потоков и объединения наборов данных.

В оригинальной публикации Слиатор и Тарьян называли деревья связей/вырезаний «динамическими деревьями» или «динамическими динамо-деревьями».

Структура

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

Демонстрация того, как узлы хранятся по глубине в дереве разреза ссылок.

Предпочтительные пути

доступ к узлу v осуществляется Когда в представленном дереве , выбранный путь становится предпочтительным . Предпочтительным дочерним элементом узла является последний дочерний элемент, который был на пути доступа, или значение NULL, если последний доступ был к v или если к этой конкретной ветви дерева не было обращений. — Предпочтительное ребро это ребро, которое соединяет предпочтительного дочернего элемента с v .

В альтернативной версии предпочтительные пути определяются самым тяжелым дочерним элементом.

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

Операции

Нас интересуют операции FindRoot(Node v), Cut(Node v), Link(Node v, Node w) и Path(Node v). Каждая операция реализуется с помощью подпрограммы Access(Node v). Когда мы получаем доступ к вершине v , предпочтительный путь представленного дерева меняется на путь от корня R представленного дерева до узла v . Если узел напуть доступа ранее имел предпочтительный дочерний элемент u , а теперь путь идет к дочернему элементу w , старому предпочтительному ребру. удаляется (заменяется указателем path-parent ), и новый путь теперь проходит через w .

Доступ

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

Теперь мы поднимаемся по представленному дереву к корню R , разрывая и сбрасывая предпочтительный путь там, где это необходимо. Для этого мы следуем указателю родительского пути из v (поскольку v теперь является корнем, у нас есть прямой доступ к указателю родительского пути). Если путь, по которому находится v , уже содержит корень R (поскольку узлы имеют ключ по глубине, это будет самый левый узел во вспомогательном дереве), указатель родительского пути будет нулевым, и доступ будет завершен. В противном случае мы следуем за указателем на некоторый узел по другому пути w . Мы хотим сломать старый предпочтительный путь w и снова соединить его с путем v . Для этого мы расширяем w и отключаем его правое поддерево, устанавливая указатель родительского пути на w . Поскольку все узлы имеют ключ глубины, и каждый узел на пути v глубже, чем каждый узел на пути w (поскольку они являются дочерними элементами w в представленном дереве), мы просто соединяем дерево v как правого дочернего элемента. из ш . Мы снова расширяем v , что, поскольку v является дочерним элементом корня w , просто поворачивает v до корня. Мы повторяем весь этот процесс до тех пор, пока указатель родительского пути v имеет значение null, и в этот момент он находится на том же предпочтительном пути, что и корень представленного дерева R .

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

Найтикорень

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

Резать

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

Связь

Если v — корень дерева, а w — вершина другого дерева, свяжите деревьясодержащий v и w, путем добавления ребра(v, w), делая w родительским элементом v .Для этого мы обращаемся к v и w в их соответствующих деревьях и делаем w левымребенок В. Поскольку v является корнем, а узлы вспомогательного дерева имеют ключи по глубине, доступ к v означаетчто у v не будет левого дочернего элемента во вспомогательном дереве (поскольку в качестве корня это минимальная глубина). Добавление w как левогоchild фактически делает его родителем v в представленном дереве.

Путь

Для этой операции мы хотим выполнить некоторую агрегатную функцию для всех узлов (или ребер) на пути от корня R до узла v (например, «сумма», «мин», «макс», «увеличение» и т. д.). Для этого мы обращаемся к v , что дает нам вспомогательное дерево со всеми узлами на пути от корня R до узла v . Структура данных может быть дополнена данными, которые мы хотим получить, например минимальными или максимальными значениями или суммой затрат в поддереве, которые затем можно вернуть по заданному пути за постоянное время.

Псевдокод операций

Switch-Preferred-Child(x, y):    if (right(x) is not null)        path-parent(right(x)) = x    right(x) = y    if (y is not null)        parent(y) = x

Access(v):    splay(v)    Switch-Preferred-Child(v, null)    if (path-parent(v) is not null)         w = path-parent(v)        splay(w)        Switch-Preferred-Child(w, v)        Access(v)

Link(v, w):    Access(v)    Access(w)    left(v) = w    parent(w) = v

Cut(v):    Access(v)    if (left(v) is not null)        path-parent(left(v)) = path-parent(v)        left(v) = null    path-parent(v) = null

Анализ

Стоимость вырезания и связи составляет O (1) плюс стоимость доступа. FindRoot имеет амортизированную верхнюю границу O (log n ) плюс стоимость доступа. Структура данных может быть дополнена дополнительной информацией (например, узлом с минимальным или максимальным значением в его поддеревьях или суммой), в зависимости от реализации. Таким образом, Path может возвращать эту информацию за постоянное время плюс ограничение доступа.

Так что осталось привязать доступ , чтобы узнать наше время работы.

Access использует расширение, которое, как мы знаем, имеет амортизированную верхнюю границу O (log n ). Итак, оставшийся анализ касается того, сколько раз нам нужно сыграть. Это равно количеству изменений предпочтительных дочерних элементов (количеству ребер, измененных на предпочтительном пути) при движении вверх по дереву.

Мы ограничили доступ , используя технику под названием Heavy-Light Decomposition .

Тяжело-легкое разложение

Этот метод называет ребро тяжелым или легким в зависимости от количества узлов в поддереве. ⁠ $Size(v)$ ⁠ представляет количество узлов в поддереве v в представленном дереве. Ребро называется тяжелым, если size(v) > Размер 1 ⁄ 2 (родитель(v)). Таким образом, мы видим, что каждый узел может иметь не более 1 тяжелого ребра. Край, который не является тяжелым , называется легким .

относится Глубина света к количеству световых ребер на заданном пути от корня до вершины v . Глубина света ≤ lg n , потому что каждый раз, когда мы пересекаем светлое ребро, мы уменьшаем количество узлов как минимум в 2 раза (поскольку оно может иметь не более половины узлов родителя).

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

Сначала мы докажем $O(\log ^{2}n)$ верхняя граница.

О (лог. ² п ) верхняя граница

Операция расширения доступа дает нам log n , поэтому нам нужно ограничить количество обращений к log n, чтобы доказать O (log ² n ) верхняя граница.

Каждое изменение предпочтительного края приводит к формированию нового предпочтительного края. Итак, мы подсчитываем количество образовавшихся предпочтительных ребер. Поскольку на любом заданном пути имеется не более log n легких ребер, то не более log n легких ребер становятся предпочтительными.

Число тяжелых ребер, которые становятся предпочтительными, может составлять ⁠ $O(n)$ ⁠ для любой данной операции, но это ⁠ $O(\log n)$ ⁠ амортизируется. За серию выполнений мы можем добиться, чтобы n -1 тяжелых ребер стали предпочтительными (поскольку в представленном дереве всего не более n -1 тяжелых ребер), но с этого момента количество тяжелых ребер, которые станут предпочтительными, будет равно числу тяжелых краев, которые стали нежелательными на предыдущем этапе. Для каждого тяжелого преимущества, которое становится непредпочтительным, легкое преимущество должно стать предпочтительным. Мы уже видели, что число легких ребер, которые могут стать предпочтительными, не превосходит log n . Таким образом, количество тяжелых ребер, которые становятся предпочтительными для m операций, равно ⁠ $m(\log n)+(n-1)$ ⁠ . Более чем достаточно операций ( ⁠ $m>n-1$ ⁠ ) это в среднем составляет ⁠ $O(\log n)$ ⁠ .

до O (log n ) Улучшение верхней границы

Мы ограничили количество предпочтительных дочерних изменений ⁠ $O(\log n)$ ⁠ , поэтому, если мы сможем показать, что каждое предпочтительное дочернее изменение имеет амортизированную стоимость O(1), мы можем ограничить операцию доступа в ⁠ $O(\log n)$ ⁠ . Это делается с помощью потенциального метода .

Пусть s(v) — количество узлов под v в дереве вспомогательных деревьев. Тогда потенциальная функция $\Phi =\sum _{v}\log {s(v)}$ . Мы знаем, что амортизированная стоимость расширения ограничена:

cost(splay(v))\leq 3\left(\log {s(root(v))}-\log {s(v)}\right)+1

Мы знаем, что после расширения v является дочерним элементом своего родительского узла w . Итак, мы знаем, что:

s(v)\leq s(w)

Мы используем это неравенство и амортизированную стоимость доступа для получения телескопической суммы, которая ограничена:

3\left(\log {s(R)}-\log {s(v)}\right)+O({\text{number of preferred child changes}})

где R — корень представленного дерева, и мы знаем, что количество предпочтительных дочерних изменений равно ⁠ $O(\log n)$ ⁠ . s ( R ) знак равно n , поэтому мы имеем ⁠ $O(\log n)$ ⁠ амортизируется.

Приложение

Деревья связей/разрезаний можно использовать для решения проблемы динамической связности ациклических графов. Учитывая два узла x и y, они соединены тогда и только тогда, когда FindRoot(x) = FindRoot(y). Другая структура данных, которую можно использовать для той же цели, — это дерево обхода Эйлера .

При решении задачи максимального потока деревья связей/разрезаний могут использоваться для улучшения времени работы алгоритма Динича с $O(V^{2}E)$ к $O(VE\log V)$ .

См. также

Дальнейшее чтение

Слейтор, Д.Д.; Тарьян, Р.Э. (1983). «Структура данных для динамических деревьев». Материалы тринадцатого ежегодного симпозиума ACM по теории вычислений - STOC '81 (PDF) . п. 114. дои : 10.1145/800076.802464 .
Слейтор, Д.Д.; Тарьян, Р.Э. (1985). «Самонастраивающиеся двоичные деревья поиска» (PDF) . Журнал АКМ . 32 (3): 652. дои : 10.1145/3828.3835 .
Гольдберг, А.В. ; Тарьян, Р.Э. (1989). «Нахождение минимальных тиражей путем отмены отрицательных циклов». Журнал АКМ . 36 (4): 873. дои : 10.1145/76359.76368 . – Применение к минимально-стоимостному обращению
Деревья Link-Cut в: конспекты лекций по расширенным структурам данных, весна 2012 г., лекция 19. Проф. Эрик Демейн, Писцы: Писцы: Джастин Холмгрен (2012), Цзин Цзянь (2012), Максим Степаненко (2012), Машхуд Ишак (2007). ).
https://jeffe.cs.illinois.edu/teaching/datastructures/2006/notes/07-linkcut.pdf

v т и Древовидные структуры данных
Поиск деревьев ( динамические наборы / ассоциативные массивы )	2–3 2–3–4 АА (а, б) АВЛ Б B+ Б* Б ^х ( Оптимально ) Бинарный поиск Танцы HTree Интервал Статистика заказов Палиндром ( Наклон влево ) Красно-черный козел отпущения Распространение Т Треп УБ Сбалансированный по весу
Кучи	Двоичный Биномиальный Мостовая долина д -и Фибоначчи Левый Сопряжение Наклонный бином Перекос от Эмде Боас Слабый
Пытается	Деревня C-trie (сжатый ADT) Хэш Радикс Суффикс Троичный поиск X-быстрый Y-быстро
пространственных данных Деревья разделения	Мяч БК БСП декартовский Гильберт Р. k -d ( неявный k -d ) М Метрика MVP Октри PH Приоритет Р Четырехместный Р Р+ Р* Сегмент вице-президент Х
Другие деревья	Крышка Экспоненциальный Фенвик Палец Индекс фрактального дерева Слияние хеш-календарь iDistance К-и Левый ребенок, правый брат Связать/вырезать Лог-структурированное слияние Меркле ПК Диапазон SPQR Вершина