Join-basierte Baumalgorithmen - Join-based tree algorithms

In der Informatik sind Join-basierte Baumalgorithmen eine Klasse von Algorithmen für selbstausgleichende binäre Suchbäume . Dieses Framework zielt darauf ab, hochparallelisierte Algorithmen für verschiedene ausgewogene binäre Suchbäume zu entwerfen. Das algorithmische Framework basiert auf einem Single-Operation- Join . Unter diesem Rahmen erfasst der Join- Vorgang alle Ausgleichskriterien verschiedener Ausgleichsschemata, und alle anderen Funktionen Join haben eine generische Implementierung über verschiedene Ausgleichsschemas hinweg. Die Join-basierten Algorithmen können auf mindestens vier Ausgleichsschemata angewendet werden: AVL-Bäume , Rot-Schwarz-Bäume , gewichtsausgeglichene Bäume und Treaps .

Die Verknüpfungsoperation nimmt als Eingabe zwei binäre ausgeglichene Bäume und des gleichen Ausgleichsschemas und einen Schlüssel und gibt einen neuen ausgeglichenen binären Baum aus, dessen Durchquerung in der Reihenfolge die Durchquerung von ist , dann die Durchquerung in der Reihenfolge von . Insbesondere wenn die Bäume Suchbäume sind , was bedeutet, dass die Reihenfolge der Bäume eine Gesamtordnung der Schlüssel beibehält , muss sie die Bedingung erfüllen, dass alle Schlüssel kleiner als und alle Schlüssel größer als sind . ${\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}$

Geschichte

Die Join- Operation wurde zuerst von Tarjan für Rot-Schwarz-Bäume definiert , die in logarithmischer Zeit im ungünstigsten Fall ausgeführt wird. Später beschrieben Sleator und Tarjan einen Join- Algorithmus für Spreizbäume, der in amortisierter logarithmischer Zeit läuft. Später erweiterte Adams Join auf gewichtsausgeglichene Bäume und benutzte ihn für schnelle Set-Set-Funktionen, einschließlich Vereinigung , Schnitt und Set-Differenz . 1998 erweiterten Belloch und Reid-Miller join auf treaps und bewiesen, dass die Schranke der Mengenfunktionen für zwei Bäume der Größe und gilt , was im Vergleichsmodell optimal ist. Sie brachten auch Parallelität in Adams' Algorithmus hervor, indem sie ein Teile-und-Herrsche-Schema verwendeten . 2016 haben Belloch et al. schlug formal die Join-basierten Algorithmen vor und formalisierte den Join- Algorithmus für vier verschiedene Ausgleichsschemata: AVL-Bäume , Rot-Schwarz-Bäume , gewichtsausgeglichene Bäume und Treaps . In derselben Arbeit bewiesen sie, dass Adams' Algorithmen zu Vereinigung, Schnitt und Differenz auf allen vier Ausgleichsschemata arbeitsoptimal sind. ${\displaystyle O(m\log(1+{\frac {n}{m}}))}$${\displaystyle m}$${\displaystyle n(\geq m)}$

Algorithmen beitreten

Die Funktion join hält Neugewichtung den Baum, und somit abhängig von der Eingangsausgleichsschema. Wenn die beiden Bäume ausgeglichen sind, erzeugt Join einfach einen neuen Knoten mit linkem Teilbaum t ₁ , Wurzel k und rechtem Teilbaum t ₂ . Angenommen, t ₁ ist schwerer (dieses "Schwerer" hängt vom Ausgleichsschema ab) als t ₂ (der andere Fall ist symmetrisch). Join folgt dem rechten Spine von t ₁ bis zu einem Knoten c, der mit t ₂ ausgeglichen ist . An diesem Punkt wird ein neuer Knoten mit linkem Kind c , Wurzel k und rechtem Kind t ₂ erzeugt, um c zu ersetzen. Der neue Knoten kann die Ausgleichsinvariante ungültig machen. Dies kann durch Drehungen behoben werden. ${\displaystyle (t_{1},k,t_{2})}$

Im Folgenden sind die Join- Algorithmen für verschiedene Ausgleichsschemata aufgeführt.

Der Join- Algorithmus für AVL-Bäume :

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)

Hier von einem Knoten der Höhe von . exponieren(v)=(l,k,r) bedeutet , das linke Kind eines Baumknotens , den Schlüssel des Knotens und das rechte Kind zu extrahieren . Node(l,k,r) bedeutet, einen Knoten von left child , key und right child zu erstellen . ${\displaystyle h(v)}$${\displaystyle v}$${\displaystyle v}$${\displaystyle v}$${\displaystyle l}$${\displaystyle k}$${\displaystyle r}$${\displaystyle l}$${\displaystyle k}$${\displaystyle r}$

Der Join- Algorithmus für Rot-Schwarz-Bäume :

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)

Hier bedeutet ein Knoten die doppelte schwarze Höhe eines schwarzen Knotens und die doppelte schwarze Höhe eines roten Knotens. exponieren(v)=(l,⟨k,c⟩,r) bedeutet , das linke Kind eines Baumknotens, den Schlüssel des Knotens , die Farbe des Knotens und das rechte Kind zu extrahieren . Node(l,⟨k,c⟩,r) bedeutet, einen Knoten mit linkem Kind , Schlüssel , Farbe und rechtem Kind zu erstellen . ${\displaystyle r(v)}$${\displaystyle v}$${\displaystyle v}$${\displaystyle l}$${\displaystyle k}$${\displaystyle c}$${\displaystyle r}$${\displaystyle l}$${\displaystyle k}$${\displaystyle c}$${\displaystyle r}$

Der Join- Algorithmus für Bäume mit Gewichtung :

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)

Balance bedeutet hier zwei Gewichte und sind ausbalanciert. exponieren(v)=(l,k,r) bedeutet , das linke Kind eines Baumknotens , den Schlüssel des Knotens und das rechte Kind zu extrahieren . Node(l,k,r) bedeutet, einen Knoten aus linkem Kind , Schlüssel und rechtem Kind zu erstellen . ${\displaystyle (x,y)}$${\displaystyle x}$${\displaystyle y}$${\displaystyle v}$${\displaystyle l}$${\displaystyle k}$${\displaystyle r}$${\displaystyle l}$${\displaystyle k}$${\displaystyle r}$

Join-basierte Algorithmen

Im Folgenden bedeutet exponieren(v)=(l,k,r) , das linke Kind eines Baumknotens , den Schlüssel des Knotens und das rechte Kind zu extrahieren . Node(l,k,r) bedeutet, einen Knoten aus linkem Kind , Schlüssel und rechtem Kind zu erstellen . right( ) und left( ) extrahiert das rechte Kind bzw. das linke Kind eines Baumknotens . den Schlüssel eines Knotens extrahieren . Viele der Join-basierten Algorithmen sind parallel. „ “ Bedeutet , dass zwei Aussagen und kann parallel ausgeführt werden . ${\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}}$

Teilt

Um einen Baum in zwei Bäume aufzuteilen, die kleiner als key x und solche größer als key x sind , zeichnen wir zuerst einen Pfad von der Wurzel, indem wir x in den Baum einfügen . Nach dieser Einfügung werden alle Werte kleiner als x auf der linken Seite des Pfades gefunden und alle Werte größer als x werden auf der rechten Seite gefunden. Durch Anwenden von Join werden alle Teilbäume auf der linken Seite von unten nach oben zusammengeführt, wobei Schlüssel auf dem Pfad als Zwischenknoten von unten nach oben verwendet werden, um den linken Baum zu bilden, und der rechte Teil ist asymmetrisch. Bei einigen Anwendungen gibt Split auch einen booleschen Wert zurück, der angibt, ob x in der Baumstruktur angezeigt wird. Die Kosten für Split betragen , in der Größenordnung der Höhe des Baumes. ${\displaystyle O(\log n)}$

Der Split-Algorithmus lautet wie folgt:

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'))

Join2

Diese Funktion ist ähnlich wie Join definiert , jedoch ohne die mittlere Taste. Es teilt zuerst den letzten Schlüssel des linken Baums auf und verbindet dann den restlichen Teil des linken Baums mit dem rechten Baum mit . Der Algorithmus lautet wie folgt: ${\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)

Die Kosten beziehen sich auf einen Baum der Größe . ${\displaystyle O(\log n)}$${\displaystyle n}$

Einfügen und löschen

Die Einfüge- und Löschalgorithmen können bei Verwendung von Join unabhängig von Ausgleichsschemata sein. Bei einer Einfügung vergleicht der Algorithmus den einzufügenden Schlüssel mit dem Schlüssel in der Wurzel, fügt ihn in den linken/rechten Teilbaum ein, wenn der Schlüssel kleiner/größer als der Schlüssel in der Wurzel ist, und verbindet die beiden Teilbäume wieder mit der Wurzel . Eine Löschung vergleicht den zu löschenden Schlüssel mit dem Schlüssel in der Wurzel. Wenn sie gleich sind, geben Sie join2 für die beiden Teilbäume zurück. Andernfalls löschen Sie den Schlüssel aus dem entsprechenden Teilbaum und verbinden die beiden Teilbäume wieder mit der Wurzel. Die Algorithmen sind wie folgt:

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)

Sowohl das Einfügen als auch das Löschen erfordern Zeit, wenn . ${\displaystyle O(\log n)}$${\displaystyle |T|=n}$

Funktionen einstellen

Für Bäume mit Gewichtungsausgleich wurden mehrere Mengenoperationen definiert: Vereinigung , Schnittmenge und Mengendifferenz . Die Vereinigung von zwei gewichten ausgeglichenen Bäumen t ₁ und t ₂ repräsentierten Sätze A und B , ist ein Baum t , der darstellt , A ∪ B . Die folgende rekursive Funktion berechnet diese Vereinigung:

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)

In ähnlicher Weise sind die Algorithmen für Schnitt und Mengendifferenz wie folgt:

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)

Die Komplexität von Vereinigung, Schnittmenge und Differenz gilt für zwei gewichtsausgeglichene Bäume der Größen und . Diese Komplexität ist hinsichtlich der Anzahl der Vergleiche optimal. Da die rekursiven Aufrufe von union, Intersektion oder Differenz unabhängig voneinander sind, können sie aber auch parallel mit paralleler Tiefe ausgeführt werden . Wenn wendet die Join-basierte Implementierung dieselbe Berechnung an wie beim Einfügen oder Löschen eines einzelnen Elements, wenn die Wurzel des größeren Baums verwendet wird, um den kleineren Baum zu teilen. ${\displaystyle O\left(m\log\left({n\over m}+1\right)\right)}$${\displaystyle m}$${\displaystyle n(\geq m)}$ ${\displaystyle O(\log m\log n)}$${\displaystyle m=1}$

Bauen

Der Algorithmus zum Erstellen eines Baums kann den Vereinigungsalgorithmus verwenden und das Teile-und-Herrsche-Schema verwenden:

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)

Dieser Algorithmus kostet Arbeit und hat Tiefe. Ein effizienterer Algorithmus verwendet einen parallelen Sortieralgorithmus. ${\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)

Dieser Algorithmus kostet Arbeit und hat Tiefe, vorausgesetzt, der Sortieralgorithmus hat Arbeit und Tiefe. ${\displaystyle O(n\log n)}$${\displaystyle O(\log n)}$${\displaystyle O(n\log n)}$${\displaystyle O(\log n)}$

Filter

Diese Funktion wählt alle Einträge in einem Baum aus, die einen Indikator erfüllen , und gibt einen Baum zurück, der alle ausgewählten Einträge enthält. Es filtert rekursiv die beiden Teilbäume und verbindet sie mit der Wurzel, wenn die Wurzel erfüllt , andernfalls verbinden2 die beiden Teilbäume. ${\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)

Dieser Algorithmus kostet Arbeit und Tiefe bei einem Baum der Größe , vorausgesetzt, er hat konstante Kosten. ${\displaystyle O(n)}$${\displaystyle O(\log n)}$${\displaystyle n}$${\displaystyle f}$

Wird in Bibliotheken verwendet

Die Join-basierten Algorithmen werden angewendet, um Schnittstellen für Sets , Maps und Augmented Maps in Bibliotheken wie Hackage , SML/NJ und PAM zu unterstützen .

Anmerkungen

Verweise

Externe Links

• PAM , die parallele erweiterte Kartenbibliothek
• Hackage , Container in Hackage