Unterschied zwischen rot-schwarzen Bäumen und AVL-Bäumen

Kann jemand bitte erklären, was die Hauptunterschiede zwischen diesen beiden Datenstrukturen sind? Ich habe versucht, online eine Quelle zu finden, die die Unterschiede / Ähnlichkeiten hervorhebt, aber ich habe nichts zu informatives gefunden. In welchen Fällen würde einer dem anderen vorgezogen? Welche praktischen Situationen machen eine "besser" als die andere?

AVL-Bäume halten ein starreres Gleichgewicht als rot-schwarze Bäume. Der Weg von der Wurzel zum tiefsten Blatt in einem AVL-Baum beträgt höchstens ~ 1,44 lg (n + 2), während er in rot-schwarzen Bäumen höchstens ~ 2 lg (n + 1) beträgt.

Infolgedessen ist die Suche in einem AVL-Baum in der Regel schneller, dies geht jedoch zu Lasten eines langsameren Einfügens und Löschens aufgrund von mehr Rotationsvorgängen. Verwenden Sie daher einen AVL-Baum, wenn Sie erwarten, dass die Anzahl der Suchvorgänge die Anzahl der Aktualisierungen des Baums dominiert.

Für kleine Daten :

Einfügen : RB-Baum & AVL-Baum haben eine konstante Anzahl der maximalen Rotation, aber der RB-Baum ist schneller, da der RB-Baum im Durchschnitt weniger Rotation verwendet.

Nachschlagen : Der AVL-Baum ist schneller, da der AVL-Baum weniger Tiefe hat.

Löschen : Der RB-Baum hat eine konstante Anzahl maximaler Rotationen, aber der AVL-Baum kann O (log N) Rotationszeiten als schlechteste haben. und im Durchschnitt hat der RB-Baum auch eine geringere Anzahl von Rotationen, so dass der RB-Baum schneller ist.

für große Datenmengen :

Einfügen : AVL-Baum ist schneller. weil Sie vor dem Einfügen nach einem bestimmten Knoten suchen müssen. Wenn Sie mehr Daten haben, wächst der Zeitunterschied beim Nachschlagen des jeweiligen Knotens proportional zu O (log N). Der AVL-Baum und der RB-Baum benötigen jedoch im schlimmsten Fall nur eine konstante Anzahl von Rotationen. Somit wird der Flaschenhals zu der Zeit, in der Sie nach diesem bestimmten Knoten suchen.

Nachschlagen : AVL-Baum ist schneller. (wie im Fall von kleinen Daten)

Löschen : Der AVL-Baum ist im Durchschnitt schneller, aber im schlimmsten Fall ist der RB-Baum schneller. weil Sie auch nach einem sehr tiefen Knoten suchen müssen, um ihn vor dem Entfernen auszutauschen (ähnlich wie beim Einfügen). Im Durchschnitt haben beide Bäume eine konstante Anzahl von Rotationen. Der RB-Baum hat jedoch eine konstante Obergrenze für die Rotation.

Zitat daraus: Unterschied zwischen AVL und rot-schwarzen Bäumen

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 ist es, was die Leistung in realen Implementierungen tatsächlich kostet. 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 Flaggen simulieren 2-3 Verhalten.

Per Definition ist jede AVL daher eine Teilmenge von Rot-Schwarz. Man sollte in der Lage sein, jeden AVL-Baum ohne Umstrukturierung oder Rotation zu färben, um ihn in einen Rot-Schwarz-Baum umzuwandeln.

AVL-Bäume werden häufig mit rot-schwarzen Bäumen verglichen, da beide die gleichen Operationen unterstützen und O(log n)Zeit für die Grundoperationen benötigen. Für suchintensive Anwendungen sind AVL-Bäume schneller als rot-schwarze Bäume, da sie strenger ausbalanciert sind. Ähnlich wie rot-schwarze Bäume sind AVL-Bäume höhenausgeglichen. Beide sind im Allgemeinen weder gewichtsausgeglichen noch μ-ausgeglichen für μ ≤ ½; Das heißt, Geschwisterknoten können eine sehr unterschiedliche Anzahl von Nachkommen haben.

Aus dem Wikipedia-Artikel über AVL-Bäume

Die maximale Höhe der Bäume ist von größter Bedeutung, um das Gleichgewicht zu halten. Es ist fast gleich 1.44 * log(n)für AVL, aber für RB-Baum ist es 2 * log(n). So können wir den Schluss ziehen, dass es besser ist, die AVL zu verwenden, wenn das Problem ein Suchanreiz ist. Was zählt, ist eine andere Frage für den AVL- und RB-Baum. Der RB-Baum ist besser als die AVL, wenn die zufällige Einfügung zu geringeren Rotationskosten erfolgt, aber die AVL, mit der die aufsteigenden oder absteigenden Daten eingefügt werden können. Wenn das Problem also ein Anreiz zum Einfügen ist, können wir den RB-Baum verwenden.

Um eine Vorstellung davon zu bekommen, wie ein AVL-Baum funktioniert, hilft diese interaktive Visualisierung.

Sowohl AVL- als auch RedBlack-Bäume sind baumausgeglichene Baumdatenstrukturen. Sie sind sich ziemlich ähnlich, und der eigentliche Unterschied besteht in der Anzahl der Rotationsvorgänge, die bei jedem Hinzufügen / Entfernen ausgeführt werden - höher im Fall von AVL, um ein insgesamt homogeneres Auswuchten zu gewährleisten.

Beide Implementierungen werden als a skaliert O(lg N), wobei N die Anzahl der Blätter ist. In der Praxis ist ein AVL-Baum jedoch bei suchintensiven Aufgaben schneller: Aufgrund des besseren Ausgleichs sind die Baumdurchläufe im Durchschnitt kürzer. Auf der anderen Seite ist das Einfügen und Löschen eines AVL-Baums langsamer: Eine höhere Anzahl von Umdrehungen ist erforderlich, um die Datenstruktur beim Ändern richtig auszugleichen.

Für allgemeine Implementierungen (dh a priori ist nicht klar, ob Suchvorgänge die vorherrschenden Vorgänge sind) werden RedBlack-Bäume bevorzugt: Sie sind einfacher zu implementieren und in den gängigen Fällen schneller - überall dort, wo die Datenstruktur so häufig geändert wird, wie gesucht wird . Ein Beispiel, TreeMapund TreeSetin Java verwenden Sie einen unterstützenden RedBlack Tree.

Die Tatsache, dass RedBlack-Bäume weniger Rotationen aufweisen, kann sie beim Einfügen / Löschen jedoch schneller machen. Da sie normalerweise etwas tiefer sind, können sie beim Einfügen und Löschen auch langsamer sein. Jedes Mal, wenn Sie von einer Ebene im Baum zur nächsten wechseln, ändert sich erheblich, dass sich die angeforderten Informationen nicht im Cache befinden und aus dem RAM abgerufen werden müssen. Somit kann die Zeit, die mit weniger Umdrehungen gewonnen wird, bereits verloren gehen, da es tiefer navigieren und daher seinen Cache häufiger aktualisieren muss. Die Möglichkeit, aus dem Cache heraus zu arbeiten oder nicht, macht einen großen Unterschied. Wenn sich die relevanten Informationen im Cache befinden, können Sie in der Zeit, die zum Navigieren auf einer zusätzlichen Ebene erforderlich ist, mehrere Rotationsvorgänge ausführen, und die Informationen der nächsten Ebene befinden sich nicht im Cache. In Fällen, in denen RedBlack theoretisch schneller ist und nur die erforderlichen Operationen betrachtet, könnte es in der Praxis langsamer sein.

Nach dem, was ich gesehen habe, machen AVL-Bäume so viele Umdrehungen (manchmal rekursiv auf dem Baum) wie nötig, um die gewünschte Höhe des AVL-Baums zu erhalten (Log n). Dies macht es starrer ausbalanciert.

Für Red Black Trees gibt es 5 Regelsätze, die Sie benötigen, um sicherzustellen, dass Sie beim Einfügen und Entfernen bleiben. Diese finden Sie hier http://en.wikipedia.org/wiki/Red-black_tree .

Die Hauptsache, die Ihnen bei rot-schwarzen Bäumen helfen könnte, ist die Tatsache, dass Sie abhängig von diesen fünf Regeln den Baum rekursiv bis zur Wurzel färben können, wenn der Onkel rot ist. Wenn der Onkel schwarz ist, müssen Sie maximal zwei Umdrehungen ausführen, um alle Probleme zu beheben, aber nach diesen ein oder zwei Umdrehungen sind Sie fertig. Pack es ein und sag gute Nacht, denn das ist das Ende der Manipulation, die du machen musst.

Die große Regel ist Nummer 5 ... 'Jeder einfache Pfad von einem bestimmten Knoten zu einem seiner Nachkommenblätter enthält die gleiche Anzahl schwarzer Knoten'.

Dies führt dazu, dass die meisten Umdrehungen erforderlich sind, damit der Baum funktioniert, und dass der Baum nicht zu weit aus dem Gleichgewicht gerät.

Zusammenfassend: AvlTrees sind etwas ausgewogener als RedBlackTrees. Beide Bäume benötigen insgesamt O (log n) Zeit für das Nachschlagen, Einfügen und Löschen, aber für das Einfügen und Löschen erfordert der erstere O (log n) -Rotationen, während der letztere nur O (1) -Rotationen benötigt.

Da Rotationen das Schreiben in den Speicher bedeuten und das Schreiben in den Speicher teuer ist, lassen sich RedBlackTrees in der Praxis schneller aktualisieren als AvlTrees