Алгоритмы дерева на основе соединений - Join-based tree algorithms

В Информатика, древовидные алгоритмы на основе соединений представляют собой класс алгоритмов для самобалансирующиеся бинарные деревья поиска. Эта структура направлена на разработку высокопараллельных алгоритмов для различных сбалансированных двоичных деревьев поиска. Алгоритмическая структура основана на одной операции присоединиться.^[1] В рамках этой структуры присоединиться операция фиксирует все критерии балансировки различных схем балансировки и все другие функции присоединиться имеют общую реализацию в разных схемах балансировки. В основанные на соединениях алгоритмы может применяться как минимум к четырем схемам балансировки: Деревья АВЛ, красно-черные деревья, деревья со сбалансированным весом и Treaps.

В присоединиться ${ displaystyle (L, k, R)}$ операция принимает на вход два двоичных сбалансированных дерева ${ displaystyle L}$ и ${ displaystyle R}$ такой же схемы балансировки, и ключ ${ displaystyle k}$ , и выводит новое сбалансированное двоичное дерево ${ displaystyle t}$ чья обход по порядку это обход ${ displaystyle L}$ , тогда ${ displaystyle k}$ затем обход по порядку ${ displaystyle R}$ . В частности, если деревья деревья поиска, что означает, что порядок деревьев поддерживает общий заказ на ключах он должен удовлетворять условию, что все ключи в ${ displaystyle L}$ меньше чем ${ displaystyle k}$ и все ключи в ${ displaystyle R}$ больше чем ${ displaystyle k}$ .

История

В присоединиться операция была впервые определена Тарьяном ^[2] на красно-черные деревья, который выполняется в наихудшем логарифмическом времени. Позже Слеатор и Тарджан ^[3] описал присоединиться алгоритм для растопыренные деревья который работает в амортизированном логарифмическом времени. Позже Адамс ^[4] расширенный присоединиться к деревья со сбалансированным весом и использовал его для быстрых функций настройки, включая союз, пересечение и установить разницу. В 1998 году Blelloch и Reid-Miller расширили присоединиться на Treaps, и доказал, что оценка функций множества ${ Displaystyle О (м журнал (1 + { гидроразрыва {п} {м}}))}$ для двух деревьев размером ${ displaystyle m}$ и ${ Displaystyle п ( GEQ м)}$ , что оптимально в сравнительной модели. Они также подняли параллелизм в алгоритме Адамса, используя схема "разделяй и властвуй". В 2016 году Blelloch et al. официально предложили алгоритмы, основанные на соединениях, и формализовали присоединиться алгоритм для четырех различных схем балансировки: Деревья АВЛ, красно-черные деревья, деревья со сбалансированным весом и Treaps. В той же работе они доказали, что алгоритмы Адамса на объединении, пересечении и разности оптимальны для работы на всех четырех схемах балансировки.

Алгоритмы соединения

Функция присоединиться ${ displaystyle (t_ {1}, k, t_ {2})}$ учитывает перебалансировку дерева и, следовательно, зависит от схемы балансировки ввода. Если два дерева сбалансированы, присоединиться просто создает новый узел с левым поддеревом $т 1$ , корень $k$ и правое поддерево $т 2$ . Предположим, что $т 1$ тяжелее (это «тяжелее» зависит от схемы балансировки), чем $т 2$ (другой случай - симметричный). Присоединиться следует за правым позвоночником $т 1$ до узла $c$ который сбалансирован с $т 2$ . На этом этапе новый узел с левым дочерним элементом $c$ , корень $k$ и правильный ребенок $т 2$ создан для замены c. Новый узел может аннулировать инвариант балансировки. Это можно исправить поворотами.

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

В присоединиться алгоритм для деревьев AVL:

функция joinRightAVL (T_L, k, Т_р) (l, k ', c) = выставить (T_L)    если (h (c) <= h (T_р) + 1) T '= Узел (c, k, T_р) если (h (T ') <= h (l) + 1), то вернуть Узел (l, k ', T') иначе вернуть rotateLeft (Узел (l, k ', rotateRight (T'))) еще         T '= joinRightAVL (c, k, T_р) Т = Узел (l, k ', T')        если (h (T ') <= h (l) + 1) вернуть Т        еще вернуть rotateLeft (T)функция joinLeftAVL (T_L, k, Т_р) / * симметрично joinRightAVL * /функция присоединиться (T_L, k, Т_р)    если (ч (т_L)> h (T_р) + 1) вернуть joinRightAVL (T_L, k, Т_р)    если (ч (т_р)> h (T_L) + 1) вернуть joinLeftAVL (T_L, k, Т_р)    вернуть Узел (T_L, k, Т_р)

Вот ${ displaystyle h (v)}$ узла ${ displaystyle v}$ высота ${ displaystyle v}$ . expose (v) = (l, k, r) означает извлечь узел дерева ${ displaystyle v}$ левый ребенок ${ displaystyle l}$ , ключ узла ${ displaystyle k}$ , и правильный ребенок ${ displaystyle r}$ . Узел (l, k, r) означает создание узла левого потомка ${ displaystyle l}$ , ключ ${ displaystyle k}$ , и правый ребенок ${ displaystyle r}$ .

В присоединиться алгоритм для красно-черных деревьев:

функция joinRightRB (T_L, k, Т_р)    если г (т_L) = ⌊R (T_L)/2⌋ × 2:        вернуть Узел (T_L, ⟨K, красный⟩, T_р)    еще         (L ', ⟨k', c'⟩, R ') = выставить (T_L) T '= Узел (L', ⟨k ', c'⟩, joinRightRB (R', k, T_р)        если (c '= черный) и (T'.right.color = T'.right.right.color = красный): T'.right.right.color = черный вернуть rotateLeft (T ') еще return T 'функция joinLeftRB (T_L, k, Т_р) / * симметрично joinRightRB * /функция присоединиться (T_L, k, Т_р)    если ⌊R (T_L) / 2⌋> ⌊r (T_р) / 2⌋ × 2: T '= joinRightRB (T_L, k, Т_р)        если (T'.color = red) и (T'.right.color = red): T'.color = black return T ' иначе если ⌊R (T_L) / 2⌋> ⌊r (T_L) / 2⌋ × 2 / * симметричный * / иначе если (Т_L.color = черный) и (T_р = черный) Узел (T_L, ⟨K, красный⟩, T_р)    еще        Узел (T_L, ⟨K, черный⟩, T_р)

Вот ${ Displaystyle г (v)}$ узла ${ displaystyle v}$ означает удвоенную высоту черного черного узла и вдвое большую высоту черного красного узла. expose (v) = (l, ⟨k, c⟩, r) означает извлечь узел дерева ${ displaystyle v}$ левый ребенок ${ displaystyle l}$ , ключ узла ${ displaystyle k}$ , цвет узла ${ displaystyle c}$ и правильный ребенок ${ displaystyle r}$ . Узел (l, ⟨k, c⟩, r) означает создание узла левого потомка ${ displaystyle l}$ , ключ ${ displaystyle k}$ , цвет ${ displaystyle c}$ и правильный ребенок ${ displaystyle r}$ .

В присоединиться алгоритм для сбалансированных по весу деревьев:

функция joinRightWB (T_L, k, Т_р) (l, k ', c) = выставить (T_L)    если баланс (| T_L|, | Т_L|) вернуть Узел (T_L, k, Т_р)    еще         Т '= joinRightWB (c, k, T_р) (l₁, k₁, р₁) = выставить (T ') если (баланс (l, T ')) вернуть Узел (l, k ', T') иначе если (баланс (| l |, | l₁|) и баланс (| l | + | l₁|, | г₁|))            вернуть rotateLeft (Узел (l, k ', T')) еще return rotateLeft (Узел (l, k ', rotateRight (T'))функция joinLeftWB (T_L, k, Т_р) / * симметрично joinRightWB * /функция присоединиться (T_L, k, Т_р)    если (тяжелый (T_L, Т_р)) вернуть joinRightWB (T_L, k, Т_р)    если (тяжелый (T_р, Т_L)) вернуть joinLeftWB (T_L, k, Т_р) Узел (T_L, k, Т_р)

Здесь баланс ${ Displaystyle (х, у)}$ означает два веса ${ displaystyle x}$ и ${ displaystyle y}$ сбалансированы. expose (v) = (l, k, r) означает извлечь узел дерева ${ displaystyle v}$ левый ребенок ${ displaystyle l}$ , ключ узла ${ displaystyle k}$ и правильный ребенок ${ displaystyle r}$ . Узел (l, k, r) означает создание узла левого потомка ${ displaystyle l}$ , ключ ${ displaystyle k}$ и правильный ребенок ${ displaystyle r}$ .

Алгоритмы на основе соединения

Далее expose (v) = (l, k, r) означает извлечение узла дерева. ${ displaystyle v}$ левый ребенок ${ displaystyle l}$ , ключ узла ${ displaystyle k}$ и правильный ребенок ${ displaystyle r}$ . Узел (l, k, r) означает создание узла левого потомка ${ displaystyle l}$ , ключ ${ displaystyle k}$ и правильный ребенок ${ displaystyle r}$ . правильно( ${ displaystyle v}$ ) и влево( ${ displaystyle v}$ ) извлекает правый дочерний элемент и левый дочерний элемент узла дерева ${ displaystyle v}$ соответственно. ${ Displaystyle к (v)}$ извлечь ключ узла ${ displaystyle v}$ . Многие алгоритмы на основе соединений параллельны. " ${ displaystyle s_ {1} || s_ {2}}$ "означает, что два утверждения ${ displaystyle s_ {1}}$ и ${ displaystyle s_ {2}}$ может работать параллельно.

Трещина

Чтобы разделить дерево на два дерева, меньшие, чем ключ Икс, и те, которые больше ключа Икс, мы сначала рисуем путь от корня, вставляя Икс в дерево. После этой вставки все значения меньше, чем Икс будут найдены слева от пути, и все значения больше чем Икс будет находиться справа. Применяя Присоединиться, все поддеревья на левой стороне объединяются снизу вверх с использованием ключей на пути в качестве промежуточных узлов снизу вверх, чтобы сформировать левое дерево, а правая часть асимметрична. Для некоторых приложений Трещина также возвращает логическое значение, обозначающее, если Икс появляется в дереве. Цена Трещина является ${ Displaystyle О ( журнал п)}$ , порядок высоты дерева.

Алгоритм разделения следующий:

функция разделить (T, k) если (T = nil) return (nil, false, nil) (L, m, R) = выставить (T) если (k = m) return (L, истина, R) если (k вернуть (L ', b, присоединиться (R', m, R)) если (k> m) (L ', b, R') = разделить (R, k) вернуть (присоединиться (L, m, L '), b, R'))

Присоединиться2

Эта функция определяется аналогично присоединиться но без средней клавиши. Сначала он отделяет последний ключ ${ displaystyle k}$ левого дерева, а затем соедините оставшуюся часть левого дерева с правым деревом с ${ displaystyle k}$ . Алгоритм следующий:

функция splitLast (T) (L, k, R) = выставить (T) если (R = ноль) вернуть (L, k) (T ', k') = splitLast (R) вернуть (присоединиться (L, k, T '), k')функция соединение2 (L, R) если (L = ноль) вернуть R (L ', k) = splitLast (L) вернуть присоединиться (L ', k, R)

Стоимость составляет ${ Displaystyle О ( журнал п)}$ для дерева размером ${ displaystyle n}$ .

Вставить и удалить

Алгоритмы вставки и удаления при использовании присоединиться может быть независимым от схем балансировки. Для вставки алгоритм сравнивает вставляемый ключ с ключом в корне, вставляет его в левое / правое поддерево, если ключ меньше / больше, чем ключ в корне, и соединяет два поддерева обратно с корнем. . При удалении удаляемый ключ сравнивается с ключом в корне. Если они равны, верните join2 для двух поддеревьев. В противном случае удалите ключ из соответствующего поддерева и снова присоедините два поддерева к корню. Алгоритмы следующие:

функция вставить (T, k) если (T = ноль) вернуть Узел (nil, k, nil) (L, k ', R) = expose (T) если (к <к ') вернуть присоединиться (вставить (L, k), k ', R) если (к> к ') вернуть присоединиться (L, k ', вставить (R, k)) вернуть Тфункция удалить (T, k) если (T = ноль) вернуть nil (L, k ', R) = выставить (T) если (к <к ') вернуть присоединиться (удалить (L, k), k ', R) если (к> к ') вернуть присоединиться (L, k ', удалить (R, k)) вернуть соединение2 (L, R)

И для вставки, и для удаления требуется ${ Displaystyle О ( журнал п)}$ время, если ${ displaystyle | T | = n}$ .

Установить – установить функции

Несколько операций над множеством были определены на деревьях с балансировкой веса: союз, пересечение и установить разницу. Объединение двух сбалансированных по весу деревьев $т 1$ и $т 2$ представляющие наборы $А$ и $B$ , это дерево $т$ что представляет $А \cup B$ . Следующая рекурсивная функция вычисляет это объединение:

функция союз (т₁, т₂):    если т₁ = ноль: вернуть т₂    если т₂ = ноль: вернуть т₁    (т_<, б, т_>) = разделить t₂ на т₁.root nl = union (left (t₁), т_<) || nr = union (right (t₁), т_>)    вернуть присоединиться (nl, t₁.root, номер)

Аналогично, алгоритмы пересечения и разности множеств следующие:

функция пересечение (t₁, т₂):    если (т₁ = ноль или t₂ = ноль) вернуть ноль (т_<, б, т_>) = разделить t₂ на т₁.root nl = пересечение (left (t₁), т_<) || nr = пересечение (right (t₁), т_>)    если (б) вернуть присоединиться (nl, t₁.root, номер) еще вернуть join2 (NL, NR)функция разница (т₁, т₂):    если (т₁ = ноль) вернуть ноль если (т₂ = ноль) вернуть т₁    (т_<, б, т_>) = разделить t₂ на т₁.root nl = разница (left (t₁), т_<) || nr = разница (справа (t₁), т_>)    вернуть join2 (NL, NR)

Сложность каждого из объединения, пересечения и различия равна ${ Displaystyle О влево (м журнал влево ({п над м} +1 вправо) вправо)}$ для двух взвешенных по размеру деревьев ${ displaystyle m}$ и ${ Displaystyle п ( GEQ м)}$ . Эта сложность оптимальна по количеству сравнений. Что еще более важно, поскольку рекурсивные вызовы объединения, пересечения или различия не зависят друг от друга, они могут быть выполнены в параллели с параллельная глубина ${ Displaystyle О ( журнал м журнал п)}$ .^[1] Когда ${ displaystyle m = 1}$ , реализация на основе соединения применяет те же вычисления, что и при вставке или удалении одного элемента, если корень большего дерева используется для разделения меньшего дерева.

Построить

Алгоритм построения дерева может использовать алгоритм объединения и схему «разделяй и властвуй»:

функция build (A [], n): если (п = 0) вернуть ноль если (n = 1) вернуть Узел (nil, A [0], nil) L = build (A, n / 2) || R = (A + n / 2, n-n / 2) вернуть союз (L, R)

Этот алгоритм стоит ${ Displaystyle О (п журнал п)}$ работа и имеет ${ Displaystyle О ( журнал ^ {3} п)}$ глубина. Более эффективный алгоритм использует алгоритм параллельной сортировки.

функция buildSorted (A [], n): если (п = 0) вернуть ноль если (n = 1) вернуть Узел (nil, A [0], nil) L = build (A, n / 2) || R = (А + п / 2 + 1, п-п / 2-1) вернуть присоединиться (L, A [n / 2], R)функция build (A [], n): A '= sort (A, n) вернуть buildSorted (A, n)

Этот алгоритм стоит ${ Displaystyle О (п журнал п)}$ работа и имеет ${ Displaystyle О ( журнал п)}$ глубина при условии, что алгоритм сортировки ${ Displaystyle О (п журнал п)}$ работа и ${ Displaystyle О ( журнал п)}$ глубина.

Фильтр

Эта функция выбирает все записи в дереве, удовлетворяющие индикатору ${ displaystyle f}$ , и вернуть дерево, содержащее все выбранные записи. Он рекурсивно фильтрует два поддерева и объединяет их с корнем, если корень удовлетворяет ${ displaystyle f}$ , в противном случае join2 два поддерева.

функция filter (T, f): если (T = ноль) вернуть nil L = filter (left (T), f) || R = (справа (T), f) если (f (k (T)) вернуть присоединиться (L, k (T), R) еще вернуть соединение2 (L, R)

Этот алгоритм стоит работы ${ Displaystyle О (п)}$ и глубина ${ Displaystyle О ( журнал п)}$ на дереве размера ${ displaystyle n}$ , предполагая ${ displaystyle f}$ имеет постоянную стоимость.

Используется в библиотеках

Алгоритмы на основе соединений применяются для поддержки интерфейса для наборы, карты, и дополненные карты ^[5] в библиотеках, таких как Взлом, SML / NJ, и PAM.^[5]

Заметки

использованная литература

^ ^а ^б Blelloch, Guy E .; Феризович, Даниэль; Сунь, Ихан (2016), «Просто присоединяйтесь к параллельным упорядоченным множествам», Симпозиум по параллельным алгоритмам и архитектурам, Proc. 28-го симпозиума ACM. Параллельные алгоритмы и архитектуры (SPAA 2016), ACM, стр. 253–264, arXiv:1602.02120, Дои:10.1145/2935764.2935768, ISBN 978-1-4503-4210-0
^ Тарьян, Роберт Эндре (1983), «Структуры данных и сетевые алгоритмы», Структуры данных и сетевые алгоритмы, Siam, стр. 45–56.
^ Слеатор, Дэниел Доминик; Тарьян, Роберт Эндре (1985), «Самонастраивающиеся деревья двоичного поиска», Журнал ACM, Сиам
^ Адамс, Стивен (1992), «Эффективная реализация наборов на функциональном языке», Эффективная реализация наборов на функциональном языке, Citeseer, CiteSeerX 10.1.1.501.8427.
^ ^а ^б Blelloch, Guy E .; Феризович, Даниэль; Sun, Yihan (2018), "PAM: параллельные дополненные карты", Материалы 23-го симпозиума ACM SIGPLAN по принципам и практике параллельного программирования, ACM, стр. 290–304.

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

PAM, параллельная расширенная библиотека карт.
Взлом, Контейнеры в Hackage

[join-based-1] а ^б Blelloch, Guy E .; Феризович, Даниэль; Сунь, Ихан (2016), «Просто присоединяйтесь к параллельным упорядоченным множествам», Симпозиум по параллельным алгоритмам и архитектурам, Proc. 28-го симпозиума ACM. Параллельные алгоритмы и архитектуры (SPAA 2016), ACM, стр. 253–264, arXiv:1602.02120, Дои:10.1145/2935764.2935768, ISBN 978-1-4503-4210-0

[join-tarjan-2] Тарьян, Роберт Эндре (1983), «Структуры данных и сетевые алгоритмы», Структуры данных и сетевые алгоритмы, Siam, стр. 45–56.

[splaytree-3] Слеатор, Дэниел Доминик; Тарьян, Роберт Эндре (1985), «Самонастраивающиеся деревья двоичного поиска», Журнал ACM, Сиам

[adams-4] Адамс, Стивен (1992), «Эффективная реализация наборов на функциональном языке», Эффективная реализация наборов на функциональном языке, Citeseer, CiteSeerX 10.1.1.501.8427.

[pam-5] а ^б Blelloch, Guy E .; Феризович, Даниэль; Sun, Yihan (2018), "PAM: параллельные дополненные карты", Материалы 23-го симпозиума ACM SIGPLAN по принципам и практике параллельного программирования, ACM, стр. 290–304.

[1]

[2]

[3]

[4]

[5]

Примечательный структуры данных
Типы	Коллекция Контейнер
Абстрактные	Ассоциативный массив Multimap Список Стек Очередь Двусторонняя очередь Приоритетная очередь Двусторонняя приоритетная очередь Набор Multiset Непересекающееся множество
Массивы	Битовый массив Круглый буфер Динамический массив Хеш-таблица Дерево хешированных массивов Разреженная матрица
Связано	Список ассоциаций Связанный список Пропустить список Развернутый связанный список Связанный список XOR
Деревья	B-дерево Дерево двоичного поиска Дерево AA AVL дерево Красно-черное дерево Самобалансирующееся дерево Splay tree Куча Двоичная куча Биномиальная куча Куча Фибоначчи R-дерево R * дерево R + дерево R-дерево Гильберта Trie Хеш-дерево
Графики	Диаграмма двоичного решения Направленный ациклический граф Направленный ациклический граф слов
Список структур данных