Schnellere Verknüpfung von treapartigen Datenstrukturen mit ungefähr derselben Größe

16

Gegeben seien zwei AVL - Bäume T1 und T2 , und ein Wert tr so dass xT1,yT2,x<tr<y , ist es einfach , eine neue AVL - Baum enthält , zu konstruieren , tr und die Werte in T1 und T2 in der Zeit Ö(1+|h(T1)-h(T2)|) , wobeih(T) die Höhe eines BaumesT (solange Bäume ihre Höhe speichern).

Dies ist auch für rot-schwarze Bäume möglich, und ich gehe auch von vielen anderen Arten ausgewogener Bäume aus.

Ist dies für Treaps oder treapartige Datenstrukturen möglich? Was ist, wenn wir tr ?

Ö(Mindest(h(T1),h(T2))) erwartete Zeit. Wenn es einen Weg gibt , erwartet auszuführen O (1) auf treaps verbinden (oder Treap artigen Datenstrukturen) mit etwa gleicher Größe (oder Root - Priorität) Ich denke, es könnte möglich sein, einen Trick von Kaplan & Tarjan zu verwenden, bei dem die Stacheln gebootet werden, um Treaps (oder treapähnliche Datenstrukturen) mit doppelt logarithmischer Verknüpfung zu erstellen.

Apfel
quelle
Hier ist ein Haskell-Code, den ich geschrieben habe und der eine schnelle Verknüpfung von AVL-Bäumen mit ungefähr derselben Größe zeigt: haskell.pastebin.com/nfGV8Ffz
jbapple
Ich bezweifle, dass dies möglich ist, da es den Anschein hat (ohne Beweis), dass die erwartete Tiefe des neuen Knotens (der den Wert t_r enthält) mehr als eine Konstante ist, selbst wenn h (T_1) = h (T_2).
Tsuyoshi Ito
Tsuyoshi Ito: Ich stimme zu, wenn Sie dem neuen Knoten die gleiche Priorität zuweisen, wie Sie anderen Knoten Prioritäten zuweisen. Was ist, wenn Sie ihm eine Priorität zuweisen, die garantiert höher ist als die der Stammknoten? Das zerstört die IID-Natur der Prioritäten, aber was ist, wenn Sie dann die anderen Prioritäten als verschoben markieren, so wie Pfade in beständigen rot-schwarzen Bäumen an den Endpunkten markiert werden? Oder was ist, wenn man die Werte nur in den Blättern eines Treaps speichert und einen Join ohne t_r ausführt?
Jbapple
Knoten in Gruppen mit n Nachkommen haben Nachkommen mit einer Wahrscheinlichkeit von 1 / n verlassen. Dies kann auch bei Treaps gleicher Größe zu langen Zusammenführungszeiten führen. Wenn Sie eine neue Wurzel auswählen, müssen Sie zu dieser navigieren. Da die durchschnittliche Tiefe im Baum Theta (lg n) ist, dauert dies auch Theta (lg n). Was ist, wenn ein Treap-Knoten mit n Nachkommen Kinder mit einer Wahrscheinlichkeit (n wähle i) / 2 ^ n hinterlassen hat und die Werte nur an Blättern wie in einem B + -Baum gespeichert werden. Durch das Zusammenfügen von zwei gleich großen Elementen wird eine kleine Anzahl von Elementen erwartungsgemäß von einem Baum auf einen anderen umverteilt.
Jbapple
Wenn meine Berechnungen korrekt sind, ist die erwartete Anzahl umverteilter Elemente Theta (sqrt n), was unter der Annahme, dass alles andere (wie die Fingersucheigenschaft) berechnet werden könnte, immer noch Theta (lg n) -Zeit in Anspruch nehmen würde. Was ist mit einer noch engeren Verteilung?
Jbapple

Antworten:

3

Nein, das ist mit normalen Treaps nicht möglich, wenn die Prioritäten zufällig sind.

Die genaue Behauptung, die ich machen werde, ist, dass eine solche Zusammenführung von zwei gleich großen Treaps mit zufälligen Prioritäten eine Aktualisierung von Zeigern in Erwartung erfordert .Θ(Logn)

Hier ist eine grobe Beweisskizze:

Berücksichtigen Sie die Anzahl der Zeiger, die Sie in der Erwartung ändern müssen, um die Operation auszuführen. Es ist einfacher, eine -Grenze zu beweisen , wenn wir nicht t r einfügen, sondern nur T 1 und T 2 zusammenführen . Betrachten Sie den rechten Rücken S 1 von T 1 und den linken Rücken S 2 von T 2 . Färbe die Elemente von S 1 rot und die von S 2 blau. Ordnung S 1S 2Θ(Logn)trT1T2S1T1S2T2S1S2S1S2nach Priorität. Wir müssen jedes Mal einen Zeiger ändern, wenn sich die Farbe in dieser Reihenfolge ändert. Da beide Stacheln mit hoher Wahrscheinlichkeit die Größe haben und die Prioritäten zufällig sind, ist es nicht schwer zu erkennen, dass die Anzahl der Farbänderungen in der Sequenz auch Θ ( log n ) beträgt . Wir müssen also Θ ( log n ) Zeiger für die Zusammenführung aktualisieren (ohne t r hinzuzufügen ).Θ(Logn)Θ(Logn)Θ(Logn)tr

Jetzt hilft es nicht viel, während des Zusammenführens hinzuzufügen . Die Anzahl der Zeigeränderungen kann in diesem Fall wie folgt niedriger sein: Reihenfolge S 1S 2{ t r } nach Priorität. Löschen Sie alles, was in der Sequenz weniger als t r ist. Dann ist die Anzahl der Farbänderungen in der resultierenden Sequenz unsere Untergrenze. Da t r Zufalls Priorität hat, ist die erwartete Höhe des Teilbaums an ihn in der endgültigen Treap verwurzelten O ( 1 ) , so dass es nur über O ( 1 ) Knoten von S 1trS1S2{tr}trtrÖ(1)Ö(1). mit niedrigerer Priorität als erwartet, so dass wir nur O ( 1 ) Zeigeränderungen in unserer unteren Schranke verloren haben, wennwir t r addierenS1S2Ö(1)tr

Nun, das heißt, es gibt wahrscheinlich eine Möglichkeit, eine "treap-ähnliche" Datenstruktur zu erhalten, die konstante erwartete Zeitverschmelzungen ermöglicht.


quelle
Ja, ich suche eine "treapartige" Datenstruktur. Obwohl ich dies in den Kommentaren und meiner ungültigen Antwort erwähnt habe, habe ich es nicht in den Titel oder die Frage eingefügt.
Jbapple
Danke für deine Antwort. Ich habe den Titel und den Text der Frage so geändert, dass sie nicht mehr so ​​eindeutig sind.
Jbapple
1

Update: Im Folgenden finden Sie ein Update zur Fehlerhaftigkeit dieses Join-Vorgangs

Hier ist eine sehr grobe Skizze einer möglichen Lösung:

Ich glaube, ich habe eine Lösung für dieses Problem mit einer Art zufällig ausgewogenem B + -Baum. Diese Bäume haben wie Treaps eine einzigartige Repräsentation. Im Gegensatz zu Treaps speichern sie einige Schlüssel mehrmals. Es könnte möglich sein, dies mit einem Trick aus Bent et al. "Biased Search Trees" zu beheben, bei dem jeder Schlüssel nur in der höchsten (dh der Wurzel nächstgelegenen) Ebene gespeichert wird, in der er erscheint.

Ein Baum für einen geordneten Satz eindeutiger Werte wird erstellt, indem zunächst jedem Wert ein Bitstrom zugeordnet wird, ähnlich wie jedem Wert in einem Treap eine Priorität zugeordnet wird. Jeder Knoten im Baum enthält sowohl einen Schlüssel als auch einen Bitstrom. Nicht-Blattknoten enthalten zusätzlich eine natürliche Zahl, die die Höhe des Baums angibt, der an diesem Knoten verwurzelt ist. Interne Knoten können eine beliebige Anzahl von Kindern ungleich Null haben. Wie bei B + -Bäumen ist jeder sich nicht selbst schneidende Pfad von der Wurzel zu einem Blatt gleich lang.

Jeder interne Knoten enthält (wie in B + -Bäumen) den größten Schlüssel k seiner Nachkommenblätter. Jedes enthält auch eine natürliche Zahl i , die die Höhe des Baums angibt, der bei v verwurzelt ist , und den Strom von Bits, die mit k ab dem i + 1- ten Bit verknüpft sind. Wenn jeder Schlüssel in dem Baum, der mit v verwurzelt ist, dasselbe erste Bit in seinem Bitstrom hat, ist jedes Kind von v ein Blatt und i ist 1 . Andernfalls sind die Kinder von v interne Knoten, von denen alle das gleiche i- te Bit in dem ihrem Schlüssel zugeordneten Bitstrom haben.vkichvkich+1vvich1vich

Um einen Baum aus einer sortierten Liste von Schlüsseln mit zugeordneten Bitströmen zu erstellen, sammeln Sie zuerst die Schlüssel in zusammenhängenden Gruppen basierend auf dem ersten Bit in ihren Streams. Erstellen Sie für jede dieser Gruppen ein übergeordnetes Element mit dem Schlüssel und dem Bitstrom des größten Schlüssels in der Gruppe, aber ohne das erste Bit des Stroms. Führen Sie nun das gleiche Gruppierungsverfahren für die neuen Eltern durch, um Großeltern zu erstellen. Fahren Sie fort, bis nur noch ein Knoten übrig ist. Das ist die Wurzel des Baumes.

Die folgende Liste der Schlüssel und (Anfangs-) Bitströme wird durch den Baum darunter dargestellt. In den Bitstrom-Präfixen ist ein '.' bedeutet ein bisschen. Das heißt, jeder Bitstrom für den Schlüssel A mit einer 0 erzeugt an erster Stelle den gleichen Baum wie jeder andere, vorausgesetzt, kein Bitstrom eines anderen Schlüssels ist unterschiedlich.

A 0...
B 00..
C 10..
D 0...
E 0011
F 1...
G 110.
H 0001


        ____H____
       /         \
      E           H
      |          / \
    __E__       G   H
   /  |  \      |   |
  B   C   E     G   H
 / \  |  / \   / \  |
A   B C D   E F   G H

Jedes Kind eines bestimmten internen Knotens hat an erster Stelle seines Bitstroms das gleiche Bit. Dies nennt man die "Farbe" des Elternteils - 0 ist rot, 1 ist grün. Das Kind hat einen "Geschmack", der vom ersten Bit seines Bitstroms abhängt - 0 ist Kirsche, 1 ist Minze. Blätter haben Aromen, aber keine Farbe. Per Definition kann ein Kirschknoten keinen grünen Elternknoten und ein Minzknoten keinen roten Elternknoten haben.

n21-n (n-1ich-1)(n+1)/2n234nÖ(lgn)

Um zwei Bäume gleicher Höhe zu verbinden, prüfen Sie zunächst, ob ihre Wurzeln die gleiche Farbe haben. Wenn ja, trennen Sie von der linken Wurzel das am weitesten rechts stehende Kind und von der rechten Wurzel das am weitesten links stehende Kind, und verbinden Sie diese beiden Bäume rekursiv. Das Ergebnis ist ein Baum mit der gleichen Höhe oder einer Höhe, da die Bäume den gleichen Geschmack haben (siehe unten). Wenn das Ergebnis des rekursiven Verbindens der beiden Bäume dieselbe Höhe hat wie die beiden abgetrennten Kinder, machen Sie es zum mittleren Kind einer Wurzel, wobei die verbleibenden Kinder der linken Wurzel davor und die verbleibenden Kinder der rechten Wurzel danach liegen. Wenn es um 1 größer ist, machen Sie seine Kinder zu den mittleren Kindern einer Wurzel mit den verbleibenden Kindern der linken Wurzel davor und den verbleibenden Kindern der rechten Wurzel danach. Wenn die Wurzeln unterschiedliche Farben haben, prüfen Sie, ob sie den gleichen Geschmack haben. Wenn sie es tun, Geben Sie ihnen ein neues übergeordnetes Element mit dem Schlüssel und dem Bitstrom der rechten Wurzel, wobei das erste Bit entfernt wird. Wenn dies nicht der Fall ist, geben Sie jeder Wurzel ein neues übergeordnetes Element mit dem Schlüssel und dem Bitstrom der alten Wurzel (wobei jedes erste Bit entfernt wird) und verbinden Sie diese Bäume dann rekursiv.

1/21/2Ö(1)1/4und nachfolgende rekursive Aufrufe beziehen sich immer auf Bäume mit unterschiedlichen Farben, sodass die gleiche Analyse angewendet wird.

1/2Ö(1)

Ö(1)

a 01110
b 110..
c 10...
d 00000

Der von gemachte Baum [a,b]hat eine Höhe von 2, der von gemachte Baum [c,d]hat eine Höhe von 2 und der von gemachte Baum joinEqual (tree [a,b]) (tree [c,d])hat eine Höhe von 3. Der von gemachte Baum [a,b,c,d]hat jedoch eine Höhe von 5.

Hier ist der Code, mit dem ich diesen Fehler gefunden habe .

Apfel
quelle