Roter schwarzer Baum über avl Baum

107

AVL- und Rotschwarzbäume gleichen sich beide selbst aus, mit Ausnahme der roten und schwarzen Farbe in den Knoten. Was ist der Hauptgrund für die Wahl von roten schwarzen Bäumen anstelle von AVL-Bäumen? Was sind die Anwendungen von roten schwarzen Bäumen?

algorithm data-structures red-black-tree suren
quelle
2
Mögliches Duplikat von Warum wird std :: map als rot-schwarzer Baum implementiert?
Lior Kogan
1
Abgesehen davon haben die Rust-Entwickler für ihre standardmäßig geordnete Karte einen B-Baum anstelle eines dieser Bäume verwendet.
Tom Anderson

Antworten:

120

Was ist der Hauptgrund für die Wahl von roten schwarzen Bäumen anstelle von AVL-Bäumen?

Sowohl rot-schwarze Bäume als auch AVL-Bäume sind die am häufigsten verwendeten ausgeglichenen binären Suchbäume und unterstützen das Einfügen, Löschen und Nachschlagen garantiert O(logN) time. Es gibt jedoch folgende Vergleichspunkte zwischen den beiden:

  • AVL-Bäume sind starrer ausbalanciert und bieten daher schnellere Suchvorgänge. Verwenden Sie daher für eine nachschlagintensive Aufgabe einen AVL-Baum.
  • Verwenden Sie für intensive Aufgaben zum Einfügen einen Rot-Schwarz-Baum.
  • AVL-Bäume speichern den Ausgleichsfaktor an jedem Knoten. Dies nimmt O(N)zusätzlichen Platz in Anspruch. Wenn wir jedoch wissen, dass die Schlüssel, die in den Baum eingefügt werden, immer größer als Null sind, können wir das Vorzeichenbit der Schlüssel verwenden, um die Farbinformationen eines rot-schwarzen Baums zu speichern. In solchen Fällen nimmt der rot-schwarze Baum keinen zusätzlichen Platz ein.

Was ist die Anwendung von Red Black Tree?

Rot-schwarze Bäume sind allgemeiner Zweck. Sie eignen sich relativ gut zum Hinzufügen, Entfernen und Nachschlagen, aber AVL-Bäume haben schnellere Nachschlagen auf Kosten eines langsameren Hinzufügens / Entfernens. Der rot-schwarze Baum wird im Folgenden verwendet:

  • Java : java.util.TreeMap,java.util.TreeSet
  • C ++ STL (in den meisten Implementierungen): Map, Multimap, Multiset
  • Linux-Kernel: völlig fairer Scheduler, linux / rbtree.h
Nikunj Banka
quelle
42
In general, the rotations for an AVL tree are harder to implement and debug than that for a Red-Black tree.ist nicht wahr.
Jingguo Yao
9
Um pedantisch zu sein, schreibt der C ++ - Standard dies nicht vor std:: mapund Freunde verwenden eine bestimmte Struktur. Das bleibt der Implementierung überlassen, obwohl libstdc ++ und Dinkumware zumindest rot-schwarze Bäume verwenden und es scheint, als ob Sie in der Praxis Recht haben.
Mbozzi
25
Der in jedem Knoten eines AVL-Baums gespeicherte Ausgleichsfaktor beträgt zwei Bits (-1 / 0 / +1). Ein rot-schwarzer Baum speichert ein Bit Farbinformation in jedem Knoten. Insgesamt benötigen beide Bäume O (N) Speicher für die zusätzlichen Informationen.
Seppo Enarvi
5
"Verwenden Sie für intensive Aufgaben zum Einfügen einen Rot-Schwarz-Baum." Warum? Das Einfügen eines AVL-Baums dauert im schlimmsten Fall nur eine Umdrehung, während ein rot-schwarzer Baum zwei Umdrehungen ausführen kann.
Daniel
3
Dies sollte gemäß der Analyse der BST-Leistung von Ben Pfaff aus dem Jahr 2003 aktualisiert werden. AVL-Bäume sind allgemeiner und bieten eine bessere Leistung. Es wäre interessant, genaue historische Gründe dafür zu finden, dass Java, C ++ und der Linux-Kernel die langsamere Implementierung wählen.
David McManamon
15

Versuchen Sie, diesen Artikel zu lesen

Es bietet einige gute Einblicke in Unterschiede, Ähnlichkeiten, Leistung usw.

Hier ist ein Zitat aus dem Artikel:

RB-Bäume sind ebenso wie AVL-Bäume selbstausgleichend. Beide bieten eine O (log n) -Such- und Einfügeleistung.

Der Unterschied besteht darin, dass RB-Bäume O (1) -Drehungen pro Einfügevorgang garantieren. Das kostet tatsächlich Leistung in realen Implementierungen.

Vereinfacht ausgedrückt erhalten RB-Bäume diesen Vorteil, indem sie konzeptionell 2-3 Bäume sind, ohne den Overhead dynamischer Knotenstrukturen mit sich herumzutragen. Physikalisch werden RB-Bäume als Binärbäume implementiert, die roten / schwarzen Flags simulieren 2-3 Verhalten

Nach meinem eigenen Verständnis sind AVL- und RB-Bäume in Bezug auf die Leistung nicht sehr weit entfernt. Ein RB-Baum ist einfach eine Variante eines B-Baums und das Balancing wird anders implementiert als ein AVL-Baum.

Jordanien
quelle
1
AFIAK, ein AVL-Baum hat auch eine O (1) -Rotation pro Einfügung. Für RB-Baum und AVL kann eine Einfügung 1 oder 0 Umdrehungen haben. Wenn eine Rotation stattfindet, werden die Algorithmen gestoppt. Wenn dies nicht der Fall ist, überprüfen / streichen Algorithmen normalerweise weiterhin Knoten von unten bis zur Wurzel des Baums. Daher kann die Drehung O (1) manchmal besser sein, da das Scannen der verbleibenden Elemente O (log (n)) entfällt. Da der AVL-Baum im Durchschnitt mehr Rotation ausführt, weist der AVL-Baum normalerweise ein besseres Gleichgewicht von ~ 1,44 log (N) auf als der RB-Baum 2 log (N).
Sergey Shandar
4

Unser Verständnis der Leistungsunterschiede hat sich im Laufe der Jahre verbessert, und jetzt besteht der Hauptgrund für die Verwendung von rot-schwarzen Bäumen über AVL darin, keinen Zugriff auf eine gute AVL-Implementierung zu haben, da diese möglicherweise etwas seltener sind, weil sie nicht in CLRS behandelt werden.

Beide Bäume werden heute als Formen von Bäumen mit ausgewogenem Rang betrachtet, aber rot-schwarze Bäume sind in realen Tests durchweg um etwa 20% langsamer . Oder sogar 30-40% langsamer, wenn sequentielle Daten eingefügt werden .

Menschen, die rot-schwarze Bäume, aber keine AVL-Bäume untersucht haben, tendieren dazu, rot-schwarze Bäume zu wählen. Die Hauptverwendungen für rot-schwarze Bäume sind im Wikipedia-Eintrag für sie aufgeführt .

David McManamon
quelle
1
Komisch! In meiner Lektüre scheint der libavl-Artikel zu sagen, dass AVL und RB Kopf an Kopf stehen und keines von beiden deutlich besser ist als das andere im Allgemeinen (welches besser ist, hängt von der Arbeitsbelastung ab). Ich sehe nirgendwo eine Behauptung, dass AVL insgesamt etwa 20% schneller ist.
Stefan
3

Andere Antworten hier fassen die Vor- und Nachteile von RB- und AVL-Bäumen gut zusammen, aber ich fand diesen Unterschied besonders interessant:

AVL-Bäume unterstützen keine konstanten amortisierten Aktualisierungskosten [rot-schwarze Bäume jedoch]

Quelle: Mehlhorn & Sanders (2008) (Abschnitt 7.4)

Während sowohl RB- als auch AVL-Bäume O (log (N)) Worst-Case-Zeit für das Nachschlagen, Einfügen und Löschen garantieren, kann die Wiederherstellung der AVL / RB-Eigenschaft nach dem Einfügen oder Löschen eines Knotens in O (1) amortisierter Zeit für erfolgen rot-schwarze Bäume.

emanek
quelle
Ich glaube, dass das Einfügen von AVL-Bäumen die gleichen / ähnlichen amortisierten Kosten hat, aber einen besser ausgeglichenen Baum erzeugt (1,44 log (N) gegenüber 2 log (N)). Gleichzeitig erfordert das Löschen im AVL-Baum möglicherweise mehr Rotationen. IMHO, dies wird in WAVL en.wikipedia.org/wiki/WAVL_tree
Sergey Shandar
1

Programmierer möchten Speicher im Allgemeinen nicht dynamisch zuweisen. Das Problem mit dem avl-Baum ist, dass Sie für "n" Elemente mindestens log2 (log2 (n)) ... (height-> log2 (n)) Bits benötigen, um die Höhe des Baums zu speichern! Wenn Sie also enorme Daten verarbeiten, können Sie nicht sicher sein, wie viele Bits für die Speicherhöhe an jedem Knoten zugewiesen werden sollen.

Zum Beispiel, wenn Sie 4 Bytes int (32 Bit) zum Speichern der Höhe verwenden. Die maximale Höhe kann sein: 2 ^ 32 und daher beträgt die maximale Anzahl von Elementen, die Sie im Baum speichern können, 2 ^ (2 ^ 32) - (scheint sehr groß zu sein, aber in diesem Zeitalter der Daten ist wohl nichts zu groß). Wenn Sie diese Grenze überschreiten, müssen Sie dynamisch mehr Platz für die Speicherhöhe zuweisen.

Dies ist eine Antwort eines Professors an meiner Universität, die mir vernünftig erschien! Hoffe ich mache Sinn.

Bearbeitungen: Die AVL-Bäume sind im Vergleich zu rot-schwarzen Bäumen ausgeglichener, können jedoch beim Einfügen und Löschen mehr Rotationen verursachen. Wenn Ihre Anwendung viele häufige Einfügungen und Löschungen umfasst, sollten rot-schwarze Bäume bevorzugt werden. Und wenn die Einfügungen und Löschungen weniger häufig sind und die Suche häufiger ausgeführt wird, sollte der AVL-Baum dem roten schwarzen Baum vorgezogen werden. --Quelle GEEKSFORGEEKS.ORG

Prakhar Agrawal
quelle
1
Ich würde sagen, das ist interessant, aber unpraktisch. Während es wahr ist, dass es im kompaktesten Fall eine schwierige Aufgabe wäre, die effizienteste Anzahl von Bits für die Höhe auszuwählen, wird in der Praxis jeder verbleibende Speicherplatz, der kleiner als ein Byte ist, definitiv nicht verwendet, und alles, was übrig bleibt in einem 4 oder sogar 8 Byte Speicherplatz wird mit ziemlicher Sicherheit ungenutzt bleiben. Der Speicher wird aus Leistungsgründen nicht unausgerichtet zugewiesen, was den Vorteil der Rückgewinnung einer kleinen Menge Speicherplatz stark außer Kraft setzt. Die Zeiger auf die untergeordneten Elemente und der Wert belegen 24 Byte. 8 weitere dürften keine praktischen Kosten verursachen.
Mumbleskates
4
you need need atleast log2(log2(n))...(height->log2(n)) bits to store the height of [an AVL] treeIch brauche nicht die Höhe eines Knotens in einem AVL-Baum, um ihn zu implementieren. Sie benötigen eine zusätzliche Information für jeden Knoten ( ICH BIN DER GRÖSSTE (das Geschwister mit dem höchsten Teilbaum)). Es ist sowohl bequemer als auch konventionell, zwei zusätzliche Bits zu haben (Kind ist höher für links und rechts), wie von AV & L. vorgestellt
Greybeard
4
2 ^ (2 ^ 32) Elemente sind eine Menge ... als ob Sie jedes einzelne Molekül im gesamten Universum und jedes mögliche Paar dieser Moleküle und jedes mögliche Tripel speichern könnten und immer noch nicht einmal annähernd in die Nähe kommen könnten innerhalb eines winzigen Bruchteils eines winzigen Prozentsatzes der gewürfelten Wurzel dieser Zahl geteilt durch hundert Billionen.
Semikolon
4
Das ist sehr irreführend. Erstens müssen wir die Höhe nicht in einem Knoten eines AVL-Baums speichern. Zweitens haben wir, selbst wenn wir dies getan haben und selbst wenn sich die typische Menge an verfügbarem Speicher jedes Jahr verdoppelt, noch 4 Milliarden Jahre Zeit, bis die Höhe unserer Bäume die in 32 Bit gespeicherte Höhe überschreitet.
Gassa
3
2 ^ (2 ^ 32) Objekte sind lächerlich, wahnsinnig, absolut mehr als jeder Computer, den wir uns derzeit vorstellen können, jemals halten kann. Wir sind bei so etwas wie 2 ^ 40. Überprüfen Sie, ob Sie wieder Mathe sind.
Stefan Reich
-1

Das Neuausgleichen des AVL-Baums sollte die folgende Eigenschaft erfüllen. (Wiki-Referenz - AVL-Baum )

In einem AVL-Baum unterscheiden sich die Höhen der beiden untergeordneten Teilbäume eines Knotens um höchstens eins. Wenn sie sich zu irgendeinem Zeitpunkt um mehr als eins unterscheiden, wird ein Neuausgleich durchgeführt, um diese Eigenschaft wiederherzustellen.

Dies bedeutet also, dass die Gesamthöhe des AVL-Baums nicht verrückt werden kann, dh, die Suche mit AVL-Bäumen wird besser. Und da zusätzliche Operationen (Rotationen) durchgeführt werden sollen, um die Höhe nicht verrückt werden zu lassen, können die Baummodifikationsoperationen etwas kostspielig sein.

samshers
quelle
Es wird an vielen anderen Orten erwähnt, aber der Grund, warum diese Antwort nicht sehr gut ist, ist, dass AVL-Bäume und RB-Bäume effektiv extrem ähnliche Einschränkungen beibehalten - RB-Bäume werden nicht mehr als das 2,0-fache der erforderlichen Höhe betragen, und für AVL-Bäume ist dies der Faktor ca. 1,44. Infolgedessen drehen sich AVL-Bäume etwas häufiger, aber die Kosten pro Umdrehung sind im Wesentlichen gleich. es ist nicht teuer.
Mumbleskates