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

Kann mir bitte jemand erklären, was die wichtigsten Unterschiede zwischen diesen zwei Daten-Strukturen sind? Ich habe versucht eine Quelle finden, online, highlights sind die Unterschiede/ähnlichkeiten, aber ich habe nicht gefunden, etwas zu informativ. In welchen Fällen würden Sie eine der anderen vorgezogen? Welche praktischen Situationen machen, die einen "besser" als die andere?

InformationsquelleAutor der Frage Bob John | 2013-04-27

  1. 91

    AVL-Bäume pflegen ein Starrer Ausgewogenheit, als rot-schwarz-Bäume. Der Pfad von der Wurzel zum tiefsten Blatt in einem AVL-Baum ist bei den meisten ~1.44 lg(n+2), während in rot-schwarz-Bäume sind es höchstens ~2 lg (n+1).

    Als ein Ergebnis, die Suche in einem AVL-Baum ist in der Regel schneller, aber das kommt auf Kosten der langsameren einfügen und löschen, die durch mehr rotation Operationen. So verwenden Sie ein AVL-Baum, wenn Sie erwarten, dass die Anzahl der lookups zu Dominieren, die Anzahl der updates, die zu dem Baum.

    InformationsquelleAutor der Antwort Fred Foo

  2. 41

    Für kleine Daten:

    einfügen: RB-Baum & avl-Baum hat eine Konstante Anzahl von max rotation aber RB-Baum wird schneller sein, weil im Durchschnitt RB-Baum weniger rotation.

    lookup: AVL-Baum ist schneller, weil der AVL-Baum hat weniger Tiefe.

    löschen: RB-Baum hat eine Konstante Anzahl von max rotation aber AVL-Baum kann O(log N) mal von der rotation als Schlimmste. und auf der mittleren RB-Baum hat auch weniger Drehzahl so RB-Baum ist schneller.

    für große Daten -:

    einfügen: AVL-Baum ist schneller. da müssen Sie zum suchen nach einem bestimmten Knoten vor dem einsetzen. wie Sie mehr Daten haben, die Zeitdifferenz auf der Suche bis die bestimmten Knoten wächst proportional zu O(log N). aber AVL-Baum & RB Baum noch, müssen nur konstanter Drehzahl im schlimmsten Fall. Also der Flaschenhals wird die Zeit, die Sie lookup für diesen bestimmten Knoten.

    lookup: AVL-Baum ist schneller. (die gleichen wie in den small-data-Fall)

    löschen: AVL-Baum schneller ist im Durchschnitt, aber im schlimmsten Fall RB-Baum ist schneller. da müssen Sie auch bei der Suche nach einer sehr tiefen Knoten zu vertauschen, bevor entfernen (ähnlich wie das Grund-insertion). im Durchschnitt sowohl Bäume mit konstanter Drehzahl. aber RB-Baum hat eine Konstante Obere Schranke für die rotation.

    InformationsquelleAutor der Antwort DU Jiaen

  3. 8

    Zitiert aus: Unterschied zwischen AVL-und Rot-Schwarz-Bäume

    RB-Bäume sind, ebenso wie AVL-Bäume, selbst-balancing. Beide bieten in O(log n) - lookup und insertion Leistung.
    Der Unterschied ist, dass RB-Bäume garantieren O(1) - umdrehungen pro insert-operation. Das ist das, was eigentlich auf Kosten der performance in realen Implementierungen.
    Vereinfachte, RB-Bäume gewinnen Sie diesen Vorteil aus konzeptionell als 2-3-Bäume, ohne das tragen um den overhead der dynamischen Knoten-Strukturen. Körperlich RB-Bäume implementiert sind als Binär-Bäume rot/schwarz-flags simulieren 2-3 Verhalten.

    per definition jeder AVL ist daher Teilmengen von Rot-Schwarz. Man sollte in der Lage sein, um Farbe, die kein AVL-Baum, ohne eine Umstrukturierung oder die rotation, die verwandeln es in ein Rot-Schwarz Baum.

    InformationsquelleAutor der Antwort taocp

  4. 3

    Die maximale Höhe der Bäume im Vordergrund steht wichtig, um die balance zu halten. Es entspricht nahezu 1.44 * log(n) für AVL, aber für RB-Baum, es ist 2 * log(n). Damit können wir die Schlussfolgerung, dass es besser ist die Nutzung der AVL bei der problem Suche, Dankeschön. Was zählt, ist eine andere Frage für AVL und RB-Baum. RB-Baum ist besser als der AVL beim Blick auf die random-insertion auf die geringeren Kosten der Drehung, aber der AVL, ist gut, legen Sie auf-oder absteigender Daten. Also, wenn das problem ist eine Einlage Anreiz, können wir mit RB-Baum.

    InformationsquelleAutor der Antwort zhpmatrix

  5. 2

    AVL-Bäume sind oft im Vergleich mit rot-schwarz-Bäume, weil beide unterstützen den gleichen Satz von Operationen und nehmen O(log n) Zeit für die grundlegenden Operationen. Für lookup-intensive Anwendungen, AVL-Bäume sind schneller als rot-schwarz-Bäume, weil Sie mehr starr ausgeglichen. Ähnlich wie rot-schwarz-Bäume, AVL-Bäume sind in der Höhe ausgeglichen. Beide sind im Allgemeinen nicht die Gewicht-ausgewogene noch μ-ausgewogen für alle μ ≤ ½; Geschwister-Knoten haben können äußerst unterschiedlicher Anzahl von Nachkommen.

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

    InformationsquelleAutor der Antwort user3078685

  6. 1

    Von dem, was ich gesehen habe, scheint es, dass AVL-Bäumen zu tun, wie viele Drehungen(rekursiv bis der Baum manchmal) wie nötig, um die gewünschte Höhe des AVL-Baum (Log n). Dies macht es mehr starr ausgeglichen.

    Für Rot-Schwarz-Bäume gibt es 5 Regeln, die Sie brauchen, um stellen Sie sicher, bleiben durch einführen und entfernen die Sie hier finden können http://en.wikipedia.org/wiki/Red-black_tree.

    Die Hauptsache ist, dass könnte Ihnen helfen, für rot-schwarz-Bäumen ist die Tatsache, dass in Abhängigkeit von diesen fünf Regeln kann man rekursiv Farbe der Baum bis zur Wurzel, wenn der Onkel ist rot. Wenn der Onkel ist schwarz, Sie gehen zu müssen zu tun, maximal zwei umdrehungen zu beheben, was Probleme, die Sie haben, aber nachdem diese ein oder zwei umdrehungen FERTIG. Packen Sie es an und sagen gute Nacht denn das ist das Ende der manipulation, die Sie tun müssen.

    Die Große Regel Nummer 5...
    "Mit jedem einfachen Pfad von einem gegebenen Knoten zu untergeordneten Blätter enthält die gleiche Anzahl schwarzer Knoten.

    Diese verursachen die meisten Rotationen youll brauchen, um den Baum arbeiten, und das bewirkt, dass der Baum nicht zu weit zu gehen aus dem Gleichgewicht.

    InformationsquelleAutor der Antwort Leon

  7. 1

    In der Zusammenfassung: AvlTrees sind etwas besser ausgewogen als RedBlackTrees. Beide Bäume brauchen O(log n) Zeit insgesamt für Suchvorgänge, Insertionen und Deletionen, aber für Einfügung und Löschung der ehemalige erfordert O(log n) Rotationen, während die letzteren dauert nur O(1) Rotationen.

    Da Rotationen bedeuten, das schreiben in den Speicher und schreiben in den Speicher ist teuer, RedBlackTrees sind in der Praxis schneller zu aktualisieren als AvlTrees

    InformationsquelleAutor der Antwort beanmoon

  8. 1

    Die Tatsache, dass Rotschwarz-Bäume haben weniger umdrehungen können Sie schneller auf fügt/löscht, aber .... . Da Sie in der Regel ein wenig tiefer können Sie auch langsamer bei Einfügungen und Löschungen. Jedes mal, wenn Sie gehen von einer Ebene in dem Baum zum nächsten, es ist eine große Veränderung, dass die angeforderten Informationen nicht im cache und muss vom RAM abgerufen.
    Damit die Zeit gewonnen, die auf weniger umdrehungen kann schon verloren gehen, da Sie, um zu navigieren tiefer und somit muss seinen cache aktualisieren öfter. Zu können, arbeiten aus dem cache oder nicht, macht einen großen Unterschied. Wenn die relevanten Informationen im cache, dann können Sie mehrere Rotationen Operationen, in der Zeit benötigt, um zu navigieren, eine weitere Ebene und die nächste Stufe information nicht im cache.
    Also in Fällen, Rotschwarz ist in der Theorie schneller, betrachtet man nur die Operationen, es könnte langsamer sein in der Praxis, aufgrund von cache-misses.

    InformationsquelleAutor der Antwort Jimmy Venema

  9. 0

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

    AVL sowie Rotschwarz-Bäume sind in der Höhe balanced Tree-Datenstrukturen. Sie sind ziemlich ähnlich, der eigentliche Unterschied besteht in der Anzahl der Drehung operation erfolgt bei jedem hinzufügen/entfernen-operation - höher im Fall von AVL, erhalten eine insgesamt homogenere balancing.

    Beide Implementierungen skalieren als O(lg N)wobei N die Anzahl von Blättern, aber in der Praxis ein AVL-Baum ist schneller auf-lookup-intensive Aufgaben: unter Ausnutzung der besseren balancing, der Baum traversalen sind kürzer, im Durchschnitt. Auf der anderen Seite, einfügen und löschen von wise, einem AVL-Baum langsamer ist: eine höhere Anzahl von umdrehungen erforderlich sind, um nachzujustieren, richtig Strukturierung der Daten nach der änderung.

    Allzweck-Implementierungen (d.h. a-priori nicht klar ist, ob lookups sind die dominierenden Operationen), Rotschwarz-Bäume werden bevorzugt: Sie sind einfacher zu implementieren und schneller auf die gemeinsamen Fälle -, wo die Daten-Struktur wird geändert, Häufig als gesucht. Ein Beispiel TreeMap und TreeSet in Java nutzen backing-Rotschwarz-Baum.

    InformationsquelleAutor der Antwort Paolo Maresca

Schreibe einen Kommentar