Zusammenführen von zwei binären Suchbäumen

17

Ich suche nach einem Algorithmus, um zwei binäre Suchbäume beliebiger Größe und Reichweite zusammenzuführen. Der naheliegende Weg, dies zu implementieren, wäre, ganze Teilbäume zu finden, deren Bereich in einen beliebigen externen Knoten im anderen Baum passen kann. Die Laufzeit im ungünstigsten Fall für diese Art von Algorithmus scheint jedoch in der Größenordnung von O(n+m)wo nund mwie groß jeder Baum ist.

Mir wurde jedoch gesagt, dass dies in erfolgen könnte O(h), wo hdie Höhe des Baumes mit der größeren Höhe ist. Und ich bin völlig verfahren, wie das möglich ist. Ich habe versucht, zuerst einen der Bäume zu drehen, aber einen Baum in eine Wirbelsäule zu drehen, ist bereits O (h).

efritz
quelle
Ich weiß nicht, erick, ich habe auch die gleiche Frage.
Um fair zu sein, war dies eine Frage, die in einer Hausaufgabe des Algorithmus gestellt wurde. Es stellt sich heraus, dass O (h) eine zu strenge Laufzeit hat, da die Frage vergessen hat , mehr notwendige Informationen zu liefern: Alle Schlüssel eines Baums waren kleiner als alle Schlüssel im rechten Baum.
Efritz
Fehlt mir etwas O(log n)? Wäre es nicht einfach, binäre Bäume mit einer einfachen Funktion zum Verschieben von Knoten zusammenzuführen?
AT
@AT Ja, aber wir wussten nicht, dass sich die Schlüssel von einem BST gegenseitig ausschließen.
Efritz
1
Dies ist ein rot-schwarzer Baum, kein BST. Ein rotes Schwarz (sowie AVL-Bäume und -Haufen) sind spezielle Baumarten, die eine höhengebundene Eigenschaft behalten. Vanille BSTs können eine einzelne Wirbelsäule sein. Wenn Sie eine nicht absteigende oder nicht ansteigende Reihe von Zahlen in eine BST einfügen, werden Sie feststellen, dass die Höhe dieser Bäume tatsächlich ist n. Nur vollständige oder vollständige Binärbäume haben einen Höhenlogarithmus zu ihrer Gesamtzahl von Knoten.
Efritz

Antworten:

24

In ArXiv: 1002.4248 beschreiben John Iacono und Özgür Özkan einen relativ einfachen Algorithmus zum Zusammenführen zweier binärer Suchbäume in -amortisierter Zeit. Die Analyse ist der schwierige Teil. [ Update: Wie Joe in seiner Antwort richtig bemerkt, ist dieser Algorithmus auf Brown und Tarjan zurückzuführen.] Sie beschreiben auch eine kompliziertere Wörterbuchdatenstruktur, die auf verzerrten Überspringlisten basiert und das Zusammenführen in O ( log n ) -amortisierter Zeit unterstützt.O(log2n) O(logn)

Andererseits ist eine Worst-Case-Grenze von unmöglich. Man betrachte zwei binäre Suchbäume mit n Knoten, von denen einer die geraden Ganzzahlen zwischen 2 und 2 n und der andere die ungeraden Ganzzahlen zwischen 1 und 2 n - 1 speichert . Durch das Zusammenführen der beiden Bäume wird ein neuer binärer Suchbaum erstellt, in dem alle Ganzzahlen zwischen 1 und 2 n gespeichert sind . In einem solchen Baum hat ein konstanter Bruchteil der Knoten eine andere Parität als ihre Eltern. (Beweis: Die Eltern eines ungeraden Blattes müssen gerade sein.) Das Zusammenführen der geraden und ungeraden Bäume erfordert daher eine ÄnderungO(logn)n22n12n112n Zeiger.Ω(n)

Jeffε
quelle
Ein Hinweis: Wenn ich die Beschreibung in diesem Dokument richtig gelesen habe, unterstützen diese Bäume das Einfügen und Löschen nicht. Das Zusammenführen von folgt einfach dem Verfahren zum Zusammenführen von Fingersuchbäumen (beschrieben in Joes Antwort). Der eingeschränkte Satz von Operationen ermöglicht eine bessere Analyse als der O ( n lg mO(lg2n)eins. O(nlgmn)
jbapple
1
Die verbesserte Analyse beruht auf Abschreibungen, nicht auf einer Einschränkung der zulässigen Vorgänge. Einfügungen und Löschungen können mit Teilungen und Zusammenführungen (tatsächlich "Verknüpfungen") in derselben amortisierten -Zeitspanne unterstützt werden. O(logn)
Jeffs
Ω(n)
Standardmäßig sind "binäre Suchbäume" Zeiger-basierte Strukturen (keine "verknüpften Listen"). Jeder Knoten zeigt auf seine zwei Kinder und möglicherweise auf sein übergeordnetes Element. Die Untergrenze hängt jedoch nicht von der genauen Darstellung ab. Es gibt Möglichkeiten, zwei binäre Suchbäume mit Knoten zusammenzuführen, sodass jeder vergleichsbasierte Algorithmus mindestens Vergleiche, um die richtige zu wählen. (2nn)nlog2(2nn)2nO(logn)
Jeffs
1
@ Jɛ ɛ E: Ich bin damit einverstanden, dass Teilungen und Verknüpfungen unterstützt werden, aber ich denke nicht, dass das Erstellen oder Zerstören von Bäumen so ist. Wenn ich beispielsweise "x" aus dem Alphabet löschen möchte, erhalte ich nicht nur "a..wyz", sondern auch "x". Die Größe des Universums (das ist , siehe Abschnitt 2.1) ändert sich nicht. Das Intro zu Abschnitt 1 stellt außerdem fest, dass die Mengen das Universum aufteilen müssen, was ich (möglicherweise falsch) interpretiere, um zu bedeuten, dass sich jedes Element im Universum in einem Baum befindet. So wie ich es lese, funktioniert diese Konstruktion nicht über unbegrenzte Universen. So sollte ich meinen Kommentar oben schreiben. n
Jbapple
9

Diese Referenz könnte hilfreich sein: Brown und Tarjan, ein Algorithmus zum schnellen Zusammenführen , in dem die Autoren zeigen, wie ausgeglichene Binärbäume (AVL) in das optimal ist (z vergleichsbasierte Algorithmen). und sind die Längen der sortierten Listen, die durch die binären Suchbäume dargestellt werden, und es wird angenommen, dass .O(nlogmn)mnmn

In Abschnitt 11.5 dieses Dokuments zu Fingersuchbäumen können Sie auch eine Diskussion über verschiedene Techniken zum Zusammenführen geordneter Mengen sehen

Joe
quelle
2
Sowohl die -Zeitgrenze als auch die übereinstimmende Untergrenze setzen voraus, dass . O(nlogmn)mn
Jeffs
Ich dachte, dass das durch die Zeitspanne impliziert war, aber ich habe die Frage bearbeitet, um sie explizit zu machen.
Joe
0

Sie können Bäume in der Worst-Case-Zeit zusammenführen und dabeiO(1) Folgendes unterstützen: Einfügen, Löschen und Suchen in .O(log n)

Brodal, Gerth Stølting, Christos Makris und Kostas Tsichlas. 'Rein funktionaler Worst Case Konstante zeitlich verkettbare sortierte Listen' . In Proceedings of the 14th Conference on Annual European Symposium - Volume 14, 172–183. ESA'06. London, UK, UK: Springer-Verlag, 2006. [ PDF ]

BEIM
quelle
1
Ihre Datenstruktur unterstützt Join in O (1) -amortisierter Zeit, nicht Zusammenführen. Alle Elemente in einem Baum müssen kleiner sein als alle Elemente im anderen.
Jeffs
Ahh, stimmt. Musste den Artikel noch einmal lesen: "Join ( , ), verbindet die beiden Bäume in einem Baum. Die Bäume und sind in dem Sinne geordnet, dass alle Elemente von entweder kleiner oder größer als das kleinste oder größte Element von . Es sei angenommen , ohne Beschränkung der Allgemeinheit , dass . In diesem Fall Baum ist an Baum , und das Ergebnis dieser Operation ist der Baum zu einem Knoten auf dem Rücken angebracht ist . " TiTjTiTjTjTiw(Ti)=w(Tj)TjTiTiTjTi
AT