Zusammenführen von zwei binären Suchbäumen

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

ds.algorithms ds.data-structures tree 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 Ja, aber wir wussten nicht, dass sich die Schlüssel von einem BST gegenseitig ausschließen.

Efritz

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:

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 -amortisierter Zeit unterstützt. $O(\log^2 n)$ $O(\log n)$

Andererseits ist eine Worst-Case-Grenze von unmöglich. Man betrachte zwei binäre Suchbäume mit Knoten, von denen einer die geraden Ganzzahlen zwischen und und der andere die ungeraden Ganzzahlen zwischen und speichert . Durch das Zusammenführen der beiden Bäume wird ein neuer binärer Suchbaum erstellt, in dem alle Ganzzahlen zwischen und 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 Änderung $O(\log n)$ $n$ $2$ $2n$ $1$ $2n-1$ $1$ $2n$ Zeiger. $\Omega(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 (\lg^{2} n)

$O(\lg^2 n)$

eins.

O (n \lg \frac{m}{n})

$O(n \lg \frac{m}{n})$

jbapple

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 (l o g n)

$O(log n)$

Jeffs

Ω (n)

$\Omega(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.

(\binom{2 n}{n})

$\binom{2n}{n}$

n

$n$

\log_{2} (\binom{2 n}{n}) \geq 2 n - O (\log n)

$\log_2 \binom{2n}{n} \ge 2n - O(\log n)$

Jeffs

@ 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

$n$

Jbapple

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(n \log \frac{m}{n})$ $m$ $n$ $m \geq n$

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

Sowohl die -Zeitgrenze als auch die übereinstimmende Untergrenze setzen voraus, dass .

O (n \log \frac{m}{n})

$O(n\log \frac{m}{n})$

m \geq n

$m\ge n$

Jeffs

Ich dachte, dass das durch die Zeitspanne impliziert war, aber ich habe die Frage bearbeitet, um sie explizit zu machen.

Joe

Sie können Bäume in der Worst-Case-Zeit zusammenführen und dabei $\bf\mathcal{O}(1)$ Folgendes unterstützen: Einfügen, Löschen und Suchen in . $\mathcal{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

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 . "

T_{i}

$T_i$

T_{j}

$T_j$

T_{i}

$T_i$

T_{j}

$T_j$

T_{j}

$T_j$

T_{i}

$T_i$

w (T_{i}) = w (T_{j})

$w(T_i) = w(T_j)$

T_{j}

$T_j$

T_{i}

$T_i$

T_{i} \cdot T_{j}

$T_i \centerdot T_j$

T_{i}

$T_i$