Warum wird std :: map als rot-schwarzer Baum implementiert?

193

Warum wird std::mapes als rot-schwarzer Baum implementiert ?

Es gibt mehrere ausgeglichene binäre Suchbäume (BSTs). Was waren Design-Kompromisse bei der Auswahl eines rot-schwarzen Baums?

Denis Gorodetskiy
quelle
26
Obwohl alle Implementierungen, die ich gesehen habe, einen RB-Baum verwenden, beachten Sie, dass dies immer noch implementierungsabhängig ist.
Thomas
3
@Thomas. Es ist implementierungsabhängig. Warum verwenden alle Implementierungen RB-Bäume?
Denis Gorodetskiy
1
Ich würde wirklich gerne wissen, ob ein STL-Implementierer über die Verwendung einer Überspringliste nachgedacht hat.
Matthieu M.
2
Die Karte und das Set von C ++ sind tatsächlich geordnete Map und geordnetes Set. Sie werden nicht mit Hash-Funktionen implementiert. Jede Abfrage würde dauern O(logn)und nicht O(1), aber die Werte werden immer sortiert. Ab C ++ 11 (glaube ich) gibt es unordered_mapund unordered_set, die mit Hash-Funktionen implementiert werden, und obwohl sie nicht sortiert sind, sind die meisten Abfragen und Operationen in O(1)(durchschnittlich)
SomethingSomething
@ Thomas das ist wahr, aber in der Praxis nicht so interessant. Der Standard bietet Komplexitätsgarantien für einen bestimmten Algorithmus oder eine Reihe von Algorithmen.
Justin Meiners

Antworten:

125

Wahrscheinlich sind die beiden häufigsten selbstausgleichenden Baumalgorithmen Rot-Schwarz-Bäume und AVL-Bäume . Um den Baum nach dem Einfügen / Aktualisieren auszugleichen, verwenden beide Algorithmen den Begriff der Rotationen, bei denen die Knoten des Baums gedreht werden, um den Neuausgleich durchzuführen.

Während in beiden Algorithmen die Einfüge- / Löschoperationen O (log n) sind, ist im Fall einer Rot-Schwarz-Baum-Neuausgleichsrotation eine O (1) -Operation, während dies bei AVL eine O (log n) -Operation ist, wodurch die Rot-Schwarz-Baum effizienter in diesem Aspekt der Neuausgleichsphase und einer der möglichen Gründe, warum er häufiger verwendet wird.

Rot-Schwarz-Bäume werden in den meisten Sammlungsbibliotheken verwendet, einschließlich der Angebote von Java und Microsoft .NET Framework.

Chris Taylor
quelle
54
Sie lassen es so klingen, als könnten rot-schwarze Bäume in O (1) -Zeit Baumänderungen vornehmen, was nicht stimmt. Baummodifikationen sind O (log n) für Rot-Schwarz- und AVL-Bäume. das macht es fraglich, ob der ausgleichende Teil der Baummodifikation O (1) oder O (log n) ist, da die Hauptoperation bereits O (log n) ist. Selbst nach all der etwas zusätzlichen Arbeit, die AVL-Bäume leisten, führt dies zu einem ausgeglicheneren Baum, der zu etwas schnelleren Suchvorgängen führt. Es ist also ein absolut gültiger Kompromiss und macht AVL-Bäume rot-schwarzen Bäumen nicht unterlegen.
Nekromant
35
Sie müssen über die Komplexität der tatsächlichen Laufzeit hinausblicken, um einen Unterschied festzustellen. AVL-Bäume haben im Allgemeinen eine niedrigere Gesamtlaufzeit, wenn viel mehr Suchvorgänge als Einfügungen / Löschungen vorhanden sind. RB-Bäume haben eine niedrigere Gesamtlaufzeit, wenn viel mehr Einfügungen / Löschungen vorhanden sind. Das genaue Verhältnis, in dem die Unterbrechung auftritt, hängt natürlich von vielen Details der Implementierung, der Hardware und der genauen Verwendung ab. Da Bibliotheksautoren jedoch eine Vielzahl von Verwendungsmustern unterstützen müssen, müssen sie eine fundierte Vermutung anstellen. AVL ist auch etwas schwieriger zu implementieren, daher möchten Sie möglicherweise einen nachgewiesenen Nutzen daraus ziehen.
Steve Jessop
6
Der RB-Baum ist keine "Standardimplementierung". Jeder Implementierer wählt eine Implementierung aus. Soweit wir wissen, haben sich alle für RB-Bäume entschieden. Vermutlich dient dies entweder der Leistung oder der einfachen Implementierung / Wartung. Wie gesagt, der Haltepunkt für die Leistung bedeutet möglicherweise nicht, dass sie glauben, dass es mehr Einfügungen / Löschungen als Suchvorgänge gibt, nur dass das Verhältnis zwischen beiden über dem Niveau liegt, auf dem RB wahrscheinlich AVL übertrifft.
Steve Jessop
9
@Denis: Leider besteht die einzige Möglichkeit, Zahlen zu erhalten, darin, eine Liste der std::mapImplementierungen zu erstellen , die Entwickler aufzuspüren und sie zu fragen, nach welchen Kriterien sie die Entscheidung getroffen haben. Dies bleibt also Spekulation.
Steve Jessop
4
Bei alledem fehlen die Kosten pro Knoten für die Speicherung der Zusatzinformationen, die für die Entscheidung über das Gleichgewicht erforderlich sind. Rot-Schwarz-Bäume benötigen 1 Bit, um die Farbe darzustellen. AVL-Bäume benötigen mindestens 2 Bits (um -1, 0 oder 1 darzustellen).
SJHowe
46

Es kommt wirklich auf die Verwendung an. Der AVL-Baum weist normalerweise mehr Rotationen des Ausgleichs auf. Wenn Ihre Anwendung nicht über zu viele Einfüge- und Löschvorgänge verfügt, die Suche jedoch stark belastet, ist der AVL-Baum wahrscheinlich eine gute Wahl.

std::map Verwendet den Rot-Schwarz-Baum, da ein angemessener Kompromiss zwischen der Geschwindigkeit des Einfügens / Löschens von Knoten und der Suche erzielt wird.

Webbertiger
quelle
1
Bist du dir da sicher??? Ich persönlich denke, dass der rot-schwarze Baum entweder oder komplexer ist, niemals einfacher. Das einzige, was in Rd-Black Tree ist, ist ein erneuter Ausgleich weniger häufig als bei AVL.
Eric Ouellet
1
@Eric Theoretisch haben sowohl der R / B-Baum als auch der AVL-Baum die Komplexität O (log n)) zum Einfügen und Löschen. Ein großer Teil der Betriebskosten ist jedoch die Rotation, die sich zwischen diesen beiden Bäumen unterscheidet. Weitere Informationen finden Sie unter Diskussion.fogcreek.com/joelonsoftware/…. Zitat: "Das Ausbalancieren eines AVL-Baums kann O (log n) -Drehungen erfordern, während ein rot-schwarzer Baum höchstens zwei Umdrehungen benötigt, um ihn ins Gleichgewicht zu bringen (obwohl dies möglicherweise erforderlich ist) Untersuchen Sie O (log n) Knoten, um zu entscheiden, wo die Rotationen erforderlich sind. " Meine Kommentare wurden entsprechend bearbeitet.
Webbertiger
26

AVL-Bäume haben eine maximale Höhe von 1,44 logn, während RB-Bäume eine maximale Höhe von 2 logn haben. Das Einfügen eines Elements in eine AVL kann eine Neuausrichtung an einer Stelle im Baum bedeuten. Die Neuausrichtung beendet das Einfügen. Nach dem Einfügen eines neuen Blattes muss die Aktualisierung der Vorfahren dieses Blattes bis zur Wurzel oder bis zu einem Punkt erfolgen, an dem die beiden Teilbäume gleich tief sind. Die Wahrscheinlichkeit, k Knoten aktualisieren zu müssen, beträgt 1/3 ^ k. Das Ausbalancieren ist O (1). Das Entfernen eines Elements kann mehr als eine Neuausrichtung bedeuten (bis zur halben Tiefe des Baums).

RB-Bäume sind B-Bäume der Ordnung 4, die als binäre Suchbäume dargestellt werden. Ein 4-Knoten im B-Baum führt zu zwei Ebenen in der äquivalenten BST. Im schlimmsten Fall sind alle Knoten des Baums 2 Knoten mit nur einer Kette von 3 Knoten bis zu einem Blatt. Dieses Blatt befindet sich in einem Abstand von 2 logn von der Wurzel.

Wenn man von der Wurzel zur Einfügemarke hinuntergeht, muss man 4 Knoten in 2 Knoten ändern, um sicherzustellen, dass eine Einfügung ein Blatt nicht sättigt. Nach dem Einfügen müssen alle diese Knoten analysiert werden, um sicherzustellen, dass sie 4 Knoten korrekt darstellen. Dies kann auch im Baum geschehen. Die globalen Kosten sind gleich. Es gibt kein freies Mittagessen! Das Entfernen eines Elements aus dem Baum erfolgt in derselben Reihenfolge.

Alle diese Bäume erfordern, dass Knoten Informationen zu Größe, Gewicht, Farbe usw. enthalten. Nur Splay-Bäume sind frei von solchen zusätzlichen Informationen. Aber die meisten Menschen haben Angst vor Spreizbäumen, weil ihre Struktur so weitläufig ist!

Schließlich können Bäume auch Gewichtsinformationen in den Knoten tragen, was einen Gewichtsausgleich ermöglicht. Es können verschiedene Schemata angewendet werden. Man sollte neu ausbalancieren, wenn ein Teilbaum mehr als die dreifache Anzahl von Elementen des anderen Teilbaums enthält. Das Ausbalancieren erfolgt erneut entweder durch einfache oder doppelte Umdrehung. Dies bedeutet einen Worst-Case von 2,4 logn. Man kann mit 2 statt 3 davonkommen, ein viel besseres Verhältnis, aber es kann bedeuten, dass hier und da etwas weniger als 1% der Teilbäume aus dem Gleichgewicht geraten. Tricky!

Welche Baumart ist die beste? AVL sicher. Sie sind am einfachsten zu codieren und haben ihre schlechteste Höhe, die der Logn am nächsten kommt. Für einen Baum mit 1000000 Elementen hat eine AVL höchstens die Höhe 29, eine RB 40 und ein Gewicht, das je nach Verhältnis zwischen 36 und 50 liegt.

Es gibt viele andere Variablen: Zufälligkeit, Verhältnis von Hinzufügen, Löschen, Suchen usw.

user847376
quelle
2
Gute Antwort. Aber wenn AVLs die besten sind, warum implementiert die Standardbibliothek std :: map als RB-Baum?
Denis Gorodetskiy
13
Ich bin nicht der Meinung, dass AVL-Bäume zweifellos die besten sind. Obwohl sie eine geringe Höhe haben, erfordern sie (insgesamt) mehr Arbeit zum Nachrüsten als rot / schwarze Bäume (O (log n) Ausgleichsarbeiten gegenüber O (1) amortisierten Ausgleichsarbeiten). Spreizbäume könnten viel, viel besser sein, und Ihre Behauptung, dass die Menschen Angst vor ihnen haben, ist unbegründet. Es gibt kein universelles "bestes" Baumausgleichsschema.
Templatetypedef
Fast perfekte Antwort. Warum hast du gesagt, dass AVL das Beste ist? Das ist einfach falsch und deshalb verwendet die meiste allgemeine Implementierung einen Rot-Schwarz-Baum. Sie müssen ein ziemlich höheres Verhältnis der Überlesemanipulation haben, um AVL zu wählen. Außerdem hat AVL etwas weniger Speicherbedarf als RB.
Eric Ouellet
Ich stimme zu, dass AVL in den meisten Fällen besser ist, da Bäume normalerweise häufiger durchsucht als eingefügt werden. Warum wird der RB-Baum so häufig als besser angesehen, wenn er im Fall des Schreibens einen leichten Vorteil und im Fall des Lesens einen geringfügigen Nachteil aufweist? Wird wirklich angenommen, dass Sie mehr einfügen, als Sie finden?
Doug65536
25

Die vorherigen Antworten befassen sich nur mit Baumalternativen und Rot-Schwarz bleibt wahrscheinlich nur aus historischen Gründen.

Warum nicht eine Hash-Tabelle?

Für einen Typ muss nur der <Operator (Vergleich) als Schlüssel in einem Baum verwendet werden. Für Hash-Tabellen muss jedoch für jeden Schlüsseltyp eine hashFunktion definiert sein. Für eine generische Programmierung ist es sehr wichtig, die Typanforderungen auf ein Minimum zu beschränken, damit Sie sie mit einer Vielzahl von Typen und Algorithmen verwenden können.

Das Entwerfen einer guten Hash-Tabelle erfordert genaue Kenntnisse des Kontexts, in dem sie verwendet wird. Sollte es offene Adressierung oder verknüpfte Verkettung verwenden? Welche Belastungsstufen sollte es vor dem Ändern der Größe akzeptieren? Sollte es einen teuren Hash verwenden, der Kollisionen vermeidet, oder einen, der rau und schnell ist?

Da die STL nicht vorhersehen kann, welche die beste Wahl für Ihre Anwendung ist, muss die Standardeinstellung flexibler sein. Bäume "funktionieren einfach" und skalieren gut.

(C ++ 11 hat Hash-Tabellen mit hinzugefügt unordered_map. Sie können der Dokumentation entnehmen , dass Richtlinien festgelegt werden müssen, um viele dieser Optionen zu konfigurieren.)

Was ist mit anderen Bäumen?

Rot-Schwarz-Bäume bieten eine schnelle Suche und sind im Gegensatz zu BSTs selbstausgleichend. Ein anderer Benutzer wies auf seine Vorteile gegenüber dem selbstausgleichenden AVL-Baum hin.

Alexander Stepanov (der Schöpfer von STL) sagte, dass er einen B * -Baum anstelle eines Rot-Schwarz-Baums verwenden würde, wenn er std::maperneut schreiben würde, da dies für moderne Speicher-Caches freundlicher ist.

Eine der größten Änderungen seitdem war das Wachstum von Caches. Cache-Fehler sind sehr kostspielig, daher ist die Referenzlokalität jetzt viel wichtiger. Knotenbasierte Datenstrukturen mit geringer Referenzlokalität sind viel weniger sinnvoll. Wenn ich heute STL entwerfen würde, hätte ich einen anderen Satz von Containern. Beispielsweise ist ein speicherinterner B * -Baum eine weitaus bessere Wahl als ein rot-schwarzer Baum für die Implementierung eines assoziativen Containers. - Alexander Stepanov

Sollten Karten immer Bäume verwenden?

Eine andere mögliche Kartenimplementierung wäre ein sortierter Vektor (Einfügungssortierung) und eine binäre Suche. Dies funktioniert gut für Container, die nicht häufig geändert, aber häufig abgefragt werden. Ich mache das oft in C as qsortund bin bsearcheingebaut.

Muss ich überhaupt eine Karte verwenden?

Cache Überlegungen bedeuten , es selten sinnvoll Gebrauch macht std::listoder std::dequeüber std:vectorselbst für jene Situationen , die wir in der Schule gelernt hatten (wie zum Beispiel ein Element aus der Mitte der Liste zu entfernen). Wenn Sie dieselbe Argumentation anwenden, ist die Verwendung einer for-Schleife für die lineare Suche in einer Liste häufig effizienter und sauberer als die Erstellung einer Karte für einige Suchvorgänge.

Natürlich ist die Auswahl eines lesbaren Containers normalerweise wichtiger als die Leistung.

Justin Meiners
quelle
3

Update 14.06.2017: webbertiger bearbeitet seine Antwort, nachdem ich einen Kommentar abgegeben habe. Ich sollte darauf hinweisen, dass die Antwort für meine Augen jetzt viel besser ist. Aber ich habe meine Antwort nur als zusätzliche Information behalten ...

Aufgrund der Tatsache, dass ich denke, dass die erste Antwort falsch ist (Korrektur: nicht mehr beide) und die dritte eine falsche Bestätigung hat. Ich habe das Gefühl, ich musste Dinge klären ...

Die 2 beliebtesten Bäume sind AVL und Red Black (RB). Der Hauptunterschied liegt in der Nutzung:

  • AVL: Besser, wenn das Verhältnis der Konsultation (Lesen) größer ist als die Manipulation (Modifikation). Der Speicherbedarf ist etwas geringer als bei RB (aufgrund des zum Färben erforderlichen Bits).
  • RB: Besser in allgemeinen Fällen, in denen ein Gleichgewicht zwischen Konsultation (Lesen) und Manipulation (Modifikation) oder mehr Modifikation gegenüber Konsultation besteht. Ein etwas größerer Speicherbedarf aufgrund der Speicherung der rot-schwarzen Flagge.

Der Hauptunterschied liegt in der Färbung. Sie haben im RB-Baum weniger Neuausgleichsaktionen als in AVL, da Sie durch die Färbung manchmal Neuausgleichsaktionen überspringen oder verkürzen können, die relativ hohe Kosten verursachen. Aufgrund der Färbung hat der RB-Baum auch eine höhere Knotenebene, da er rote Knoten zwischen schwarzen Knoten aufnehmen kann (mit der Möglichkeit von ~ 2x mehr Ebenen), was das Suchen (Lesen) etwas weniger effizient macht ... aber weil es eine ist konstant (2x), bleibt es in O (log n).

Wenn Sie den Leistungstreffer für eine Änderung eines Baums (signifikant) im Vergleich zum Leistungstreffer bei der Konsultation eines Baums (fast unbedeutend) betrachten, ist es für einen allgemeinen Fall selbstverständlich, RB gegenüber AVL zu bevorzugen.

Eric Ouellet
quelle
2

Es ist nur die Wahl Ihrer Implementierung - sie können als jeder ausgeglichene Baum implementiert werden. Die verschiedenen Auswahlmöglichkeiten sind alle mit geringfügigen Unterschieden vergleichbar. Deshalb ist jeder so gut wie jeder.

Nekromant
quelle