Unterbereich eines roten und schwarzen Baumes

14

Während ich versuchte, einen Fehler in einer Bibliothek zu beheben, suchte ich erfolglos nach Artikeln über das Auffinden von Unterbereichen auf roten und schwarzen Bäumen. Ich überlege mir eine Lösung mit Reißverschlüssen und etwas ähnlichem wie beim normalen Anhängen von Löschalgorithmen für unveränderliche Datenstrukturen, frage mich jedoch immer noch, ob es einen besseren Ansatz gibt, den ich nicht finden konnte, oder auch nur eine minimale Komplexitätsgrenze bei einer solchen Operation?

Um es klar auszudrücken, ich spreche von einem Algorithmus, der bei einem rot-schwarzen Baum und zwei Grenzen einen neuen rot-schwarzen Baum mit allen Elementen des ersten Baums erzeugt, die innerhalb dieser Grenzen liegen.

Eine Obergrenze für die Komplexität wäre natürlich die Komplexität, einen Baum zu durchqueren und den anderen durch Hinzufügen von Elementen zu konstruieren.

Daniel C. Sobral
quelle
3
@Radu: Es gibt einen Fehler in der Kommentarbearbeitungsfunktion. Wenn Sie in einem Kommentar Latex verwenden und den Kommentar bearbeiten, sehen Sie seltsames Verhalten, wie Vervielfältigung usw.
Aryabhata
@Radu Ich habe ein paar Absätze hinzugefügt, um meine Frage besser zu erklären.
Daniel C. Sobral
Sind Bäume unveränderlich?
Tsuyoshi Ito
Meinten Sie im letzten Absatz auch Obergrenze statt Untergrenze?
Tsuyoshi Ito
2
Es scheint, dass die Aufteilungsoperation für rot-schwarze Bäume in der schlechtesten Zeit O (log n) implementiert werden kann, wobei n die Anzahl der Elemente in einem Baum ist. Diese Behauptung findet sich in der Einleitung der Arbeit „Rein funktionale, zeitlich kettenpflichtige, sortierte Worst-Case-Listen“ von Gerth Stølting Brodal, Christos Makris und Kostas Tsichlas, ESA 2006: cs.au.dk/~gerth/pub/esa06trees.html . Wie ich in meinem vorherigen Kommentar erwähnt habe, ermöglicht dies eine Implementierung der Unterbereichsoperation in O (log n) -Zeit im ungünstigsten Fall.
Tsuyoshi Ito

Antworten:

10

Diese Antwort kombiniert einige meiner Kommentare zu der Frage und erweitert sie.

Die Unterbereichsoperation für rot-schwarze Bäume kann im ungünstigsten Fall (log n) ausgeführt werden, wobei n die Anzahl der Elemente im ursprünglichen Baum ist. Da der resultierende Baum einige Knoten mit dem ursprünglichen Baum gemeinsam hat, ist dieser Ansatz nur geeignet, wenn Bäume unveränderlich sind (oder Bäume veränderlich sind, der ursprüngliche Baum jedoch nicht mehr benötigt wird).

Beachten Sie zunächst, dass die Unterbereichsoperation durch zwei Teiloperationen implementiert werden kann. Hier nimmt die Aufteilungsoperation einen rot-schwarzen Baum T und einen Schlüssel x und erzeugt zwei Bäume L und R, so dass L aus allen Elementen von T kleiner als x und R aus den Elementen von T größer als x besteht. Daher ist es unser Ziel, die Aufteilungsoperation für rot-schwarze Bäume im ungünstigsten Fall (log n) zu implementieren.

Wie führen wir die Aufteilungsoperation für rot-schwarze Bäume in der Zeit O (log n) durch? Nun, es stellte sich heraus, dass es eine bekannte Methode gab. (Ich wusste es nicht, aber ich bin kein Experte für Datenstrukturen.) Betrachten Sie die Verknüpfungsoperation , bei der zwei Bäume L und R so verwendet werden, dass jeder Wert in L kleiner als jeder Wert in R ist und ein Baum erzeugt wird, der aus allen besteht Werte in L und R. Die Verknüpfungsoperation kann in der ungünstigsten Zeit O (| r L - r R | +1) implementiert werden , wobei r L und r Rsind die Ränge von L bzw. R (dh die Anzahl der schwarzen Knoten auf dem Pfad von der Wurzel zu jedem Blatt). Die Aufteilungsoperation kann unter Verwendung der O-Zeiten (log n) der Verknüpfungsoperation implementiert werden, und die Gesamtzeit im ungünstigsten Fall ist unter Berücksichtigung einer Teleskopsumme immer noch O (log n).

In den Abschnitten 4.1 und 4.2 eines Buches [Tar83] von Tarjan wird beschrieben, wie die Verknüpfungs- und die Aufteilungsoperationen für rot-schwarze Bäume in der ungünstigsten Zeit O (log n) implementiert werden. Diese Implementierungen zerstören Originalbäume, aber es ist einfach, sie in unveränderliche, funktionale Implementierungen zu konvertieren, indem Knoten kopiert werden, anstatt sie zu ändern.

Als Randnotiz bieten das Set- und das Map-Modul von Objective Caml die Aufteilungsoperation sowie andere Standardoperationen für (unveränderliche) ausgeglichene binäre Suchbäume. Obwohl sie keine rot-schwarzen Bäume verwenden (sie verwenden ausgeglichene binäre Suchbäume mit der Einschränkung, dass sich die linke und die rechte Höhe um höchstens 2 unterscheiden), kann es auch nützlich sein, ihre Implementierungen zu betrachten. Hier ist die Implementierung des Set-Moduls .

Verweise

[Tar83] Robert Endre Tarjan. Datenstrukturen und Netzwerkalgorithmen . Band 44 der CBMS-NSF-Regionalkonferenzreihe für Angewandte Mathematik , SIAM, 1983.

Tsuyoshi Ito
quelle
@Radu GRIGore: Ja, es sei denn, mir fehlt etwas.
Tsuyoshi Ito
@Radu GRIGore: Oder vielleicht auch nicht, jetzt bin ich mir nicht sicher. Diese Implementierung der Aufteilungsoperation weist O (log n) neue Knoten für den Ausgabebaum zu, aber ich denke, dass die gesamte Operation wahrscheinlich rekursiv implementiert werden kann und nur O (1) Arbeitsraum benötigt. Wenn dies richtig ist, hängt die Antwort auf Ihre Frage davon ab, was Sie mit "zusätzlichen Speicherplatz" meinen.
Tsuyoshi Ito
@ Radu GRIGore: In diesem Fall denke ich, dass zusätzlicher Speicherplatz O (1) ist, obwohl ich es nicht sorgfältig überprüft habe.
Tsuyoshi Ito
@Radu GRIGore: Ich kann den Grund nicht erkennen, warum man sich um die Größe des Arbeitsbereichs kümmert, ohne sich um die Größe des Speicherbereichs zu kümmern, der zum Speichern des Ergebnisses selbst benötigt wird. In der Komplexitätstheorie gibt das Problem normalerweise an, was das Ergebnis ist, und daher hängt der zum Speichern des Ergebnisses erforderliche Speicherplatz nicht von Algorithmen ab. Bei dem aktuellen Problem gibt es jedoch viele Möglichkeiten, die erforderliche Operation zu implementieren, und einige Implementierungen benötigen mehr Speicherplatz zum Speichern des Ergebnisses als andere. Wenn Sie den Unterschied dieser Menge an Speicherplatz ignorieren, kann ich nicht nachvollziehen, warum es Sie interessiert, wie viel Arbeitsbereich wir benötigen.
Tsuyoshi Ito
Das Problem für unveränderliche Bäume unterscheidet sich von dem für veränderliche Bäume. Ich verstehe den Unterschied und hatte nichts zu fragen. Wenn Sie nun eines der beiden Probleme näher betrachten, müssen zwei Aspekte besprochen werden: Gedächtnis und Zeit. Sie haben nicht angegeben, wie viel Speicher Sie verwenden, und es schien mir nicht klar zu sein, wie die Antwort lautet. Deshalb habe ich gefragt. Ich verstehe nicht, wie es Sie zu der Annahme brachte, dass ich den Unterschied zwischen den beiden Problemen ignoriere.
Radu GRIGore
8

Die Lösung ist, keine rot-schwarzen Bäume zu verwenden. In Splay-Bäumen und AVL-Bäumen ist der Code zum Teilen und Verbinden sehr einfach. Ich verweise Sie auf die folgenden URLs mit Java-Code für Splay-Bäume und AVL-Bäume, die dies unterstützen. Gehen Sie zur folgenden URL und überprüfen Sie Set.java (avl trees) und SplayTree.java (splay trees).

ftp://ftp.cs.cmu.edu/usr/ftp/usr/sleator/splaying/

--- Danny Sleator

Danny Sleator
quelle
5
Willkommen auf der Seite, Danny!
Suresh Venkat
2
Wie wird dies dazu beitragen, die Scala Red Black-Implementierung dahingehend zu ändern, dass ein Unterbereich von weniger als unterstützt wird O(n)? Ich habe nicht gefragt, welche Art von Bäumen einfache Implementierungen von Unterbereichen aufweisen, da dies kein Problem darstellt. Diese Antwort ist zwar gut gemeint, aber nicht thematisch und für das vorliegende Problem unbrauchbar.
Daniel C. Sobral
6

(Dies soll ein Kommentar sein, aber ich bin zu neu, um einen Kommentar zu hinterlassen.)

Ich möchte lediglich darauf hinweisen, dass Sie möglicherweise auch an der Operation "Ausschneiden" interessiert sind, bei der der Unterbereich als neuer Baum und der Eingabebaum ohne Unterbereich als anderer zurückgegeben werden. Sie müssen jedoch die Kontrolle über die zugrunde liegende Darstellung des Baums haben, da die bekannte Methode auf Ebenenverknüpfungen beruht. Die Exzision verläuft zeitlogarithmisch zur Größe des kleineren Baumes, wenn auch im amortisierten Sinne ("amortisiert" ist iirc, weil ich keinen Zugang mehr zum Papier habe).

K. Hoffman, K. Mehlhorn, P. Rosenstiehl und RE Tarjan, Sorting Jordan Sequenzen in linearer Zeit mit Level Linked Search Trees, Information and Control, 68 (1986), 170-184

PS Das obige Zitat stammt aus Seidels Aufsatz. Treaps unterstützen auch die Exzision.

Maverick Woo
quelle
Diese Methode setzt voraus, dass man bereits Zeiger (oder "Finger") auf die beiden Grenzen hat.
Jbapple
3

nm[ein,b]

  1. Ö(lgn)einein
  2. Ö(m)
  3. Ö(m)

Ö(m+lgn)Ö(n+mlgm)

Ö(m)Ω(lgm)klgm

Ich habe die Details nicht ausgearbeitet, daher bin ich mir nicht sicher, wie sich die zusätzliche Buchhaltung auf die Laufzeit auswirkt.

Ö(1)Ω(lgm)

Radu GRIGore
quelle
Wenn ich darüber nachdenke, denke ich, dass ich eine grobe Zählung bekommen könnte O(logn), mit der ich das temporäre Array vermeiden könnte.
Daniel C. Sobral
Sie können die Zählung in O (lg n) erhalten, indem Sie die Teilbaumgrößen in ihren Wurzeln speichern.
Radu GRIGore
... aber das Speichern von Größen in Knoten widerspricht dem Erfordernis, keinen zusätzlichen Speicherplatz zu verwenden, weshalb meine Beobachtung Ihre Sorge um den Speicher nicht berücksichtigt.
Radu GRIGore
1
Binäre Bäume können mit nur KONSTANTEM zusätzlichen Platz (zusätzlich zum Baum selbst) perfekt
ausbalanciert werden
Ö(m+lgn)Ö(1)