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

В информатике алгоритмы деревьев на основе соединений представляют собой класс алгоритмов самобалансирующихся двоичных деревьев поиска . Целью этой структуры является разработка алгоритмов с высокой степенью параллелизма для различных сбалансированных деревьев двоичного поиска. Алгоритмическая основа основана на одной операции join . ^[1] В рамках этой структуры операция соединения фиксирует все критерии балансировки различных схем балансировки, а все остальные функции объединения имеют общую реализацию в разных схемах балансировки. Алгоритмы на основе соединений могут применяться как минимум к четырем схемам балансировки: деревьям AVL , красно-черным деревьям , деревьям со сбалансированным весом и трепам .

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

История

Операция соединения была впервые определена Тарьяном. ^[2] на красно-черных деревьях , который выполняется за логарифмическое время в худшем случае. Позже Слейтор и Тарьян ^[3] описал соединения алгоритм расширенных деревьев , который работает за амортизированное логарифмическое время. Позже Адамс ^[4] расширил соединение с деревьями со сбалансированным весом и использовал его для быстрых функций множества-множества, включая объединение , пересечение и разницу множеств . В 1998 году Блеллох и Рид-Миллер расширили соединение на Treaps и доказали, что граница функций множества равна $O(m\log(1+{\tfrac {n}{m}}))$ для двух деревьев размером $m$ и $n(\geq m)$ , что является оптимальным в модели сравнения. Они также реализовали параллелизм в алгоритме Адамса, используя схему «разделяй и властвуй» . В 2016 году Блеллох и др. формально предложил алгоритмы на основе соединений и формализовал алгоритм соединения для четырех различных схем балансировки: деревьев AVL , красно-черных деревьев , деревьев со сбалансированным весом и трепов . В той же работе они доказали, что алгоритмы Адамса объединения, пересечения и разности оптимальны по работе для всех четырех схем балансировки.

Присоединяйтесь к алгоритмам

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

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

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

function joinRightAVL(T_L, k, T_R)
    (l, k', c) := expose(T_L)
    if h(c) ≤ h(T_R) + 1
        T' := Node(c, k, T_R)
        if h(T') ≤ h(l) + 1
            return Node(l, k', T')
        else
            return rotateLeft(Node(l, k', rotateRight(T')))
    else 
        T' := joinRightAVL(c, k, T_R)
        T := Node(l, k', T')
        if h(T') ≤ h(l) + 1
            return T
        else
            return rotateLeft(T)

function joinLeftAVL(T_L, k, T_R)
    /* symmetric to joinRightAVL */

function join(T_L, k, T_R)
    if h(T_L) > h(T_R) + 1
        return joinRightAVL(T_L, k, T_R)
    else if h(T_R) > h(T_L) + 1
        return joinLeftAVL(T_L, k, T_R)
    else
        return Node(T_L, k, T_R)

Где:

$h(v)$ высота узла $v$ .
${\text{expose}}(v)$ извлекает левого дочернего элемента $l$ , ключ $k$ , и правый ребенок $r$ узла $v$ в кортеж $(l,k,r)$ .
${\text{Node}}(l,k,r)$ создает узел с левым дочерним элементом $l$ , ключ $k$ , и правый ребенок $r$ .

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

function joinRightRB(T_L, k, T_R)
    if T_L.color = black and ĥ(T_L) = ĥ(T_R)
        return Node(T_L, ⟨k, red⟩, T_R)
    else 
        (L', ⟨k', c'⟩, R') := expose(T_L)
        T' := Node(L', ⟨k', c'⟩, joinRightRB(R', k, T_R))
        if c' = black and T'.right.color = T'.right.right.color = red
            T'.right.right.color := black
            return rotateLeft(T')
        else
            return T'

function joinLeftRB(T_L, k, T_R)
    /* symmetric to joinRightRB */

function join(T_L, k, T_R)
    if ĥ(T_L) > ĥ(T_R)
        T' := joinRightRB(T_L, k, T_R)
        if (T'.color = red) and (T'.right.color = red)
            T'.color := black
        return T'
    else if ĥ(T_R) > ĥ(T_L)
        /* symmetric */
    else if T_L.color = black and T_R = black
        return Node(T_L, ⟨k, red⟩, T_R)
    else
        return Node(T_L, ⟨k, black⟩, T_R)

Где:

⁠ ${\hat {h}}(v)$ ⁠ — черная высота узла $v$ .
${\text{expose}}(v)$ извлекает левого дочернего элемента $l$ , ключ $k$ , цвет $c$ , и правый ребенок $r$ узла $v$ в кортеж $(l,\langle k,c\rangle ,r)$ .
⁠ ${\text{Node}}(l,\langle k,c\rangle ,r)$ ⁠ создает узел с левым дочерним элементом $l$ , ключ $k$ , цвет $c$ , и правый ребенок $r$ .

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

function joinRightWB(T_L, k, T_R)
    (l, k', c) := expose(T_L)
    if w(T_L) =_α w(T_R)
        return Node(T_L, k, T_R)
    else 
        T' := joinRightWB(c, k, T_R)
        (l₁, k₁, r₁) := expose(T')
        if w(l) =_α w(T')
            return Node(l, k', T')
        else if w(l) =_α w(l₁) and w(l)+w(l₁) =_α w(r₁)
            return rotateLeft(Node(l, k', T'))
        else
            return rotateLeft(Node(l, k', rotateRight(T'))

function joinLeftWB(T_L, k, T_R)
    /* symmetric to joinRightWB */

function join(T_L, k, T_R)
    if w(T_L) >_α w(T_R)
        return joinRightWB(T_L, k, T_R)
    else if w(T_R) >_α w(T_L)
        return joinLeftWB(T_L, k, T_R)
    else
        return Node(T_L, k, T_R)

Где:

$w(v)$ это вес узла $v$ .
$w_{1}=_{\alpha }w_{2}$ означает веса $w_{1}$ и $w_{2}$ являются α-весовыми сбалансированными.
$w_{1}>_{\alpha }w_{2}$ означает вес $w_{1}$ тяжелее веса $w_{2}$ относительно α-весового баланса.
${\text{expose}}(v)$ извлекает левого дочернего элемента $l$ , ключ $k$ , и правый ребенок $r$ узла $v$ в кортеж $(l,k,r)$ .
${\text{Node}}(l,k,r)$ создает узел с левым дочерним элементом $l$ , ключ $k$ и правильный ребенок $r$ .

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

В дальнейшем ${\text{expose}}(v)$ извлекает левого дочернего элемента $l$ , ключ $k$ , и правый ребенок $r$ узла $v$ в кортеж $(l,k,r)$ . ${\text{Node}}(l,k,r)$ создает узел с левым дочерним элементом $l$ , ключ $k$ и правильный ребенок $r$ . " $s_{1}||s_{2}$ " означает, что два утверждения $s_{1}$ и $s_{2}$ может работать параллельно.

Расколоть

Чтобы разделить дерево на два дерева: меньшее, чем ключ x , и большее, чем ключ x , мы сначала рисуем путь от корня, вставляя x в дерево. После этой вставки все значения меньше x будут найдены слева от пути, а все значения больше x будут найдены справа. При применении Join все поддеревья с левой стороны объединяются снизу вверх с использованием ключей на пути в качестве промежуточных узлов снизу вверх, чтобы сформировать левое дерево, а правая часть становится асимметричной. Для некоторых приложений Split также возвращает логическое значение, указывающее, присутствует ли x в дереве. Стоимость Сплита $O(\log n)$ , порядок высоты дерева.

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

function split(T, k)
    if (T = nil)
        return (nil, false, nil)
    else
        (L, m, R) := expose(T)
        if k < m
            (L', b, R') := split(L, k)
            return (L', b, join(R', m, R))
        else if k > m
            (L', b, R') := split(R, k)
            return (join(L, m, L'), b, R'))
        else
            return (L, true, R)

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

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

function splitLast(T)
    (L, k, R) := expose(T)
    if R = nil
        return (L, k)
    else
        (T', k') := splitLast(R)
        return (join(L, k, T'), k')

function join2(L, R)
    if L = nil
        return R
    else
        (L', k) := splitLast(L)
        return join(L', k, R)

Стоимость $O(\log n)$ для дерева размером $n$ .

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

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

function insert(T, k)
    if T = nil
        return Node(nil, k, nil)
    else
        (L, k', R) := expose(T)
        if k < k'
            return join(insert(L,k), k', R)
        else if k > k'
            return join(L, k', insert(R, k))
        else
            return T

function delete(T, k)
    if T = nil
        return nil
    else
        (L, k', R) := expose(T)
        if k < k'
            return join(delete(L, k), k', R)
        else if k > k'
            return join(L, k', delete(R, k))
        else
            return join2(L, R)

И вставка, и удаление требуют $O(\log n)$ время, если $|T|=n$ .

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

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

function union(t₁, t₂)
    if t₁ = nil
        return t₂
    else if t₂ = nil
        return t₁
    else
        (l₁, k₁, r₁) := expose(t₁)
        (t_<, b, t_>) := split(t₂, k₁)
        l' := union(l₁, t_<) || r' := union(r₁, t_>)
        return join(l', k₁, r')

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

function intersection(t₁, t₂)
    if t₁ = nil or t₂ = nil
        return nil
    else
        (l₁, k₁, r₁) := expose(t₁)
        (t_<, b, t_>) = split(t₂, k₁)
        l' := intersection(l₁, t_<) || r' := intersection(r₁, t_>)
        if b
            return join(l', k₁, r')
        else
            return join2(l', r')

function difference(t₁, t₂)
    if t₁ = nil
         return nil
    else if t₂ = nil
         return t₁
    else
        (l₁, k₁, r₁) := expose(t₁)
        (t_<, b, t_>) := split(t₂, k₁)
        l' = difference(l₁, t_<) || r' = difference(r₁, t_>)
        if b
            return join2(l', r')
        else
            return join(l', k₁, r')

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

Строить

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

function build(A[], n)
    if n = 0
        return nil
    else if n = 1
        return Node(nil, A[0], nil)
    else
        l' := build(A, n/2) || r' := (A+n/2, n-n/2)
        return union(L, R)

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

function buildSorted(A[], n)
    if n = 0
        return nil
    else if n = 1
        return Node(nil, A[0], nil)
    else
        l' := build(A, n/2) || r' := (A+n/2+1, n-n/2-1)
        return join(l', A[n/2], r')

function build(A[], n)
    A' := sort(A, n)
    return buildSorted(A, n)

Этот алгоритм стоит $O(n\log n)$ работать и имеет $O(\log n)$ глубина при условии, что алгоритм сортировки имеет $O(n\log n)$ работа и $O(\log n)$ глубина.

Фильтр

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

function filter(T, p)
    if T = nil
        return nil
    else
        (l, k, r) := expose(T)
        l' := filter(l, p) || r' := filter(r, p)
        if p(k)
            return join(l', k, r')
        else
            return join2(l', R)

Этот алгоритм стоит работы $O(n)$ и глубина $O(\log ^{2}n)$ на дереве размером $n$ , предполагая $p$ имеет постоянную стоимость.

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

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

Примечания

Ссылки

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

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

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

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

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

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

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

[pam-5] Перейти обратно: ^а ^б Блеллок, Гай Э.; Феризович, Дэниел; Сунь, Ихан (2018), «PAM: параллельные дополненные карты», Материалы 23-го симпозиума ACM SIGPLAN по принципам и практике параллельного программирования , ACM, стр. 290–304

[1]

[2]

[3]

[4]

[5]

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