Algorytmy drzewa oparte na złączeniach - Join-based tree algorithms

W informatyce , algorytmy drzewo przyłączyć oparte są klasą algorytmów samobalansujący wyszukiwania binarnych drzew . Ta struktura ma na celu zaprojektowanie wysoce równoległych algorytmów dla różnych zrównoważonych drzew wyszukiwania binarnego. Algorytmiczne Ramy te są oparte na pojedynczej operacji przyłączyć . W tych ramach operacja łączenia przechwytuje wszystkie kryteria równoważenia różnych schematów równoważenia, a wszystkie inne funkcje łączenia mają ogólną implementację w różnych schematach równoważenia. Te algorytmy oparte dołączyć można stosować co najmniej cztery równoważenia schematów: AVL drzew , czerwono-czarny drzew , wagę, wynosi drzew i treaps .

Operacja łączenia przyjmuje jako dane wejściowe dwa zrównoważone drzewa binarne i tego samego schematu równoważenia oraz key i wyprowadza nowe zrównoważone drzewo binarne, którego przechodzenie w kolejności jest przechodzeniem w kolejności , a następnie przechodzeniem w kolejności . W szczególności, jeśli drzewa są drzewami wyszukiwania , co oznacza, że ​​kolejność drzew utrzymuje całkowitą kolejność kluczy, musi spełniać warunek, że wszystkie klucze in są mniejsze niż i wszystkie klucze in są większe niż . ${\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}$

Historia

Operacja łączenia została po raz pierwszy zdefiniowana przez Tarjana na czerwono-czarnych drzewach , która działa w najgorszym przypadku czasu logarytmicznego. Później Sleator i Tarjan opisali algorytm łączenia drzew splay, który działa w zamortyzowanym czasie logarytmicznym. Później Adams rozszerzył złączenie na drzewa o zrównoważonym ciężarze i używał go do szybkich funkcji zbiorów, w tym sumy , przecięcia i różnicy zbiorów . W 1998 roku Blelloch i Reid-Miller rozszerzyli łączenie na treapach i udowodnili, że granica funkcji zbioru wynosi dla dwóch drzew o wielkości i , co jest optymalne w modelu porównawczym. Wspomnieli również o paralelizmie w algorytmie Adamsa, używając schematu dziel i zwyciężaj . W 2016 r. Blelloch i in. formalnie zaproponowane algorytmy oparte na przyłączenia i sformalizował przyłączenia algorytm dla czterech różnych programów w oparciu o: drzew AVL , czerwono-czarny drzew , wagę, wynosi drzew i treaps . W tej samej pracy udowodnili, że algorytmy Adamsa dotyczące sumy, przecięcia i różnicy są optymalne do pracy we wszystkich czterech schematach równoważenia. ${\ Displaystyle O (m \ log (1+ {\ Frac {n} {m}}))}$${\ Displaystyle m}$${\displaystyle n(\geqm)}$

Dołącz do algorytmów

Funkcja join uwzględnia ponowne równoważenie drzewa, a zatem zależy od schematu równoważenia danych wejściowych. Jeśli oba drzewa są zrównoważone, join po prostu tworzy nowy węzeł z lewym poddrzewem t ₁ , korzeniem k i prawym poddrzewem t ₂ . Załóżmy, że t ₁ jest cięższy (ten „cięższy” zależy od schematu równoważenia) niż t ₂ (drugi przypadek jest symetryczny). Join podąża za prawym grzbietem t ₁ aż do węzła c, który jest zrównoważony przez t ₂ . W tym momencie tworzony jest nowy węzeł z lewym dzieckiem c , korzeniem k i prawym dzieckiem t _{2 w} celu zastąpienia c. Nowy węzeł może unieważnić niezmiennik równoważący. Można to naprawić za pomocą obrotów. ${\displaystyle (t_{1},k,t_{2})}$

Poniżej znajdują się algorytmy łączenia na różnych schematach równoważenia.

Dołączyć algorytm AVL drzew :

function joinRightAVL(TL, k, TR)
    (l, k', c) = expose(TL)
    if (h(c) <= h(TR) + 1)
        T' = Node(c, k, TR)
        if (h(T') <= h(l) + 1) then return Node(l, k', T')
        else return rotateLeft(Node(l, k', rotateRight(T')))
    else 
        T' = joinRightAVL(c, k, TR)
        T = Node(l, k', T')
        if (h(T') <= h(l) + 1) return T
        else return rotateLeft(T)

function joinLeftAVL(TL, k, TR)
    /* symmetric to joinRightAVL */

function join(TL, k, TR)
    if (h(TL) > h(TR) + 1) return joinRightAVL(TL, k, TR)
    if (h(TR) > h(TL) + 1) return joinLeftAVL(TL, k, TR)
    return Node(TL, k, TR)

Tutaj węzła o wysokości . ekspozycja(v)=(l,k,r) oznacza wyodrębnienie lewego dziecka węzła drzewa , klucza węzła i prawego dziecka . Node(l,k,r) oznacza utworzenie węzła lewego dziecka , klucza i prawego dziecka . ${\displaystyle h(v)}$${\displaystyle v}$${\displaystyle v}$${\displaystyle v}$${\displaystyle l}$${\displaystyle k}$${\ Displaystyle r}$${\displaystyle l}$${\displaystyle k}$${\ Displaystyle r}$

Dołączyć algorytm czerwono-czarny drzew :

function joinRightRB(TL, k, TR)
    if r(TL) = ⌊r(TL)/2⌋ × 2:
        return Node(TL, ⟨k, red⟩, TR)
    else 
        (L', ⟨k', c'⟩, R') = expose(TL)
        T' = Node(L', ⟨k', c'⟩, joinRightRB(R', k, TR)
        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(TL, k, TR)
    /* symmetric to joinRightRB */

function join(TL, k, TR)
    if ⌊r(TL)/2⌋ > ⌊r(TR)/2⌋ × 2:
        T' = joinRightRB(TL, k, TR)
        if (T'.color = red) and (T'.right.color = red):
            T'.color = black
        return T'
    else if ⌊r(TL)/2⌋ > ⌊r(TL)/2⌋ × 2
        /* symmetric */
    else if (TL.color = black) and (TR = black)
        Node(TL, ⟨k, red⟩, TR)
    else
        Node(TL, ⟨k, black⟩, TR)

Tutaj węzeł oznacza dwukrotność czarnej wysokości czarnego węzła i dwukrotność czarnej wysokości czerwonego węzła. ekspozycja(v)=(l,⟨k,c⟩,r) oznacza wyodrębnienie lewego dziecka węzła drzewa , klucza węzła , koloru węzła i prawego dziecka . Node(l,⟨k,c⟩,r) oznacza utworzenie węzła lewego dziecka , klucza , koloru i prawego dziecka . ${\displaystyle r(v)}$${\displaystyle v}$${\displaystyle v}$${\displaystyle l}$${\displaystyle k}$${\displaystyle c}$${\ Displaystyle r}$${\displaystyle l}$${\displaystyle k}$${\displaystyle c}$${\ Displaystyle r}$

Dołączyć algorytm dla kompleksów wagowych wynosi drzew :

function joinRightWB(TL, k, TR)
    (l, k', c) = expose(TL)
    if balance(|TL|, |TL|) return Node(TL, k, TR)
    else 
        T' = joinRightWB(c, k, TR)
        (l1, k1, r1) = expose(T')
        if (balance(l, T')) return Node(l, k', T')
        else if (balance(|l|, |l1|) and balance(|l|+|l1|, |r1|))
            return rotateLeft(Node(l, k', T'))
        else return rotateLeft(Node(l, k', rotateRight(T'))

function joinLeftWB(TL, k, TR)
    /* symmetric to joinRightWB */

function join(TL, k, TR)
    if (heavy(TL, TR)) return joinRightWB(TL, k, TR)
    if (heavy(TR, TL)) return joinLeftWB(TL, k, TR)
    Node(TL, k, TR)

Tutaj równowaga oznacza dwa ciężary i są zrównoważone. ekspozycja(v)=(l,k,r) oznacza wyodrębnienie lewego dziecka węzła drzewa , klucza węzła i prawego dziecka . Node(l,k,r) oznacza utworzenie węzła lewego dziecka , klucza i prawego dziecka . ${\displaystyle (x,y)}$${\displaystyle x}$${\displaystyle y}$${\displaystyle v}$${\displaystyle l}$${\displaystyle k}$${\ Displaystyle r}$${\displaystyle l}$${\displaystyle k}$${\ Displaystyle r}$

Algorytmy oparte na łączeniu

W poniższym tekście, ekspozycja(v)=(l,k,r) oznacza wyodrębnienie lewego dziecka węzła drzewa , klucza węzła i prawego dziecka . Node(l,k,r) oznacza utworzenie węzła lewego dziecka , klucza i prawego dziecka . right( ) i left( ) wyodrębniają odpowiednio prawe i lewe dziecko węzła drzewa . wyodrębnij klucz węzła . Wiele algorytmów opartych na łączeniu jest równoległych. „ ” oznacza, że ​​dwie instrukcje i mogą działać równolegle. ${\displaystyle v}$${\displaystyle l}$${\displaystyle k}$${\ Displaystyle r}$${\displaystyle l}$${\displaystyle k}$${\ Displaystyle r}$${\displaystyle v}$${\displaystyle v}$${\displaystyle v}$${\displaystyle k(v)}$${\displaystyle v}$${\displaystyle s_{1}||s_{2}}$${\displaystyle s_{1}}$${\displaystyle s_{2}}$

Rozdzielać

Aby podzielić drzewo na dwa drzewa, mniejsze niż key x i większe niż key x , najpierw rysujemy ścieżkę od korzenia, wstawiając x do drzewa. Po tym wstawieniu wszystkie wartości mniejsze niż x zostaną znalezione po lewej stronie ścieżki, a wszystkie wartości większe niż x zostaną znalezione po prawej stronie. Stosując Join , wszystkie poddrzewa po lewej stronie są scalane od dołu do góry za pomocą klawiszy na ścieżce jako węzłów pośrednich od dołu do góry, tworząc lewe drzewo, a prawa część jest asymetryczna. W przypadku niektórych aplikacji Split zwraca również wartość logiczną oznaczającą, czy x pojawia się w drzewie. Koszt Splitu to , rząd wysokości drzewa. ${\ Displaystyle O (\ log n)}$

Algorytm podziału jest następujący:

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

Dołącz2

Ta funkcja jest zdefiniowana podobnie jak join, ale bez środkowego klawisza. Najpierw oddziela ostatni klucz lewego drzewa, a następnie łączy pozostałą część lewego drzewa z prawym drzewem za pomocą . Algorytm wygląda następująco: ${\displaystyle k}$${\displaystyle k}$

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

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

Koszt dotyczy drzewa wielkości . ${\ Displaystyle O (\ log n)}$${\ Displaystyle n}$

Wstaw i usuń

Algorytmy wstawiania i usuwania przy korzystaniu z łączenia mogą być niezależne od schematów równoważenia. W celu wstawienia algorytm porównuje klucz do wstawienia z kluczem w korzeniu, wstawia go do lewego/prawego poddrzewa, jeśli klucz jest mniejszy/większy niż klucz w korzeniu, i łączy dwa poddrzewa z powrotem z korzeniem . Usunięcie porównuje klucz do usunięcia z kluczem w katalogu głównym. Jeśli są równe, zwróć join2 na dwóch poddrzewach. W przeciwnym razie usuń klucz z odpowiedniego poddrzewa i połącz dwa poddrzewa z powrotem z korzeniem. Algorytmy są następujące:

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

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

Zarówno wstawianie, jak i usuwanie wymaga czasu, jeśli . ${\ Displaystyle O (\ log n)}$${\displaystyle |T|=n}$

Ustaw-ustaw funkcje

Kilka operacji zbiorów zostało zdefiniowanych na drzewach zrównoważonych wagowo: suma , przecięcie i różnica zbiorów . Połączenie dwóch zrównoważonych wagowo drzew t ₁ i t ₂ reprezentujących zbiory A i B , jest drzewem t reprezentującym A ∪ B . Następująca funkcja rekurencyjna oblicza tę unię:

function union(t1, t2):
    if t1 = nil:
        return t2
    if t2 = nil:
        return t1
    (t<, b, t>) = split t2 on t1.root
    nl = union(left(t1), t<) || nr = union(right(t1), t>)
    return join(nl, t1.root, nr)

Podobnie algorytmy przecięcia i różnicy zbiorów są następujące:

function intersection(t1, t2):
    if (t1 = nil or t2 = nil) return nil
    (t<, b, t>) = split t2 on t1.root
    nl = intersection(left(t1), t<) || nr = intersection(right(t1), t>)
    if (b) return join(nl, t1.root, nr)
    else return join2(nl, nr)

function difference(t1, t2):
    if (t1 = nil) return nil
    if (t2 = nil) return t1
    (t<, b, t>) = split t2 on t1.root
    nl = difference(left(t1), t<) || nr = difference(right(t1), t>)
    return join2(nl, nr)

Złożoność każdego połączenia, skrzyżowania i różnicy dotyczy dwóch zrównoważonych wagowo drzew o rozmiarach i . Ta złożoność jest optymalna pod względem liczby porównań. Co ważniejsze, ponieważ rekurencyjne wywołania sumy, przecięcia lub różnicy są od siebie niezależne, mogą być wykonywane równolegle z równoległą głębokością . Gdy , implementacja oparta na łączeniu stosuje te same obliczenia, co przy wstawianiu lub usuwaniu pojedynczego elementu, jeśli do podziału mniejszego drzewa używany jest korzeń większego drzewa. ${\ Displaystyle O \ lewo (m \ log \ lewo ({n \ ponad m} + 1 \ po prawej) \ po prawej)}$${\ Displaystyle m}$${\displaystyle n(\geqm)}$ ${\ Displaystyle O (\ log m \ log n)}$${\ Displaystyle m = 1}$

Budować

Algorytm budowania drzewa może korzystać z algorytmu sumy i stosować schemat dziel i zwyciężaj:

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

Ten algorytm kosztuje pracę i ma głębię. Bardziej wydajny algorytm wykorzystuje algorytm sortowania równoległego. ${\ Displaystyle O (n \ log n)}$${\ Displaystyle O (\ log ^ {3}n)}$

function buildSorted(A[], n):
    if (n = 0) return nil
    if (n = 1) return Node(nil, A[0], nil)
    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)

Ten algorytm kosztuje pracę i ma głębokość, zakładając, że algorytm sortowania ma pracę i głębokość. ${\ Displaystyle O (n \ log n)}$${\ Displaystyle O (\ log n)}$${\ Displaystyle O (n \ log n)}$${\ Displaystyle O (\ log n)}$

Filtr

Ta funkcja wybiera wszystkie wpisy w drzewie, które spełniają wskaźnik , i zwraca drzewo zawierające wszystkie wybrane wpisy. Rekursywnie filtruje dwa poddrzewa i łączy je z korzeniem, jeśli korzeń spełnia wymagania , w przeciwnym razie łączy 2 dwa poddrzewa. ${\displaystyle f}$${\displaystyle f}$

function filter(T, f):
    if (T = nil) return nil
    L = filter(left(T), f) || R = (right(T), f)
    if (f(k(T)) return join(L, k(T), R)
    else return join2(L, R)

Ten algorytm kosztuje pracę i głębokość na drzewie o rozmiarze , zakładając, że ma stały koszt. ${\ Displaystyle O (n)}$${\ Displaystyle O (\ log n)}$${\ Displaystyle n}$${\displaystyle f}$

Używane w bibliotekach

Algorytmy oparte na łączeniu są stosowane do obsługi interfejsu dla zestawów , map i rozszerzonych map w bibliotekach takich jak Hackage , SML/NJ i PAM .

Uwagi

Bibliografia

Linki zewnętrzne

• PAM , równoległa biblioteka rozszerzonej mapy
• Hackage , Kontenery w Hackage