Unterschied zwischen AVL-Bäumen und Splay-Bäumen

Ich studiere über die verschiedenen Bäume und kam in AVL-Bäumen und splay-Bäume. Ich will wissen,

  1. Was ist der Unterschied zwischen der AVL-Bäume und splay-Bäume????
  2. Auf welcher Grundlage wählen wir diese Bäume?
  3. Was positiv ist und negativ von diesen Bäumen?
  4. Was sind die Leistungen, die diese Bäume in Bezug auf die big-O-notation?

InformationsquelleAutor der Frage venkysmarty | 2011-09-19

  1. 62

    1. Beide splay-Bäume und AVL-Bäume sind binäre suchbäume mit hervorragender Leistung garantiert, aber Sie unterscheiden sich darin, wie Sie die Erreichung dieser Garantie, dass die Leistung. In einem AVL-Baum, die Form des Baums gebunden ist, zu allen Zeiten, so dass der Baum die Form ist symmetrisch, was bedeutet, dass die Höhe des Baumes nie mehr als O(log n). Diese Form wird beibehalten, auf Insertionen und Deletionen, und ändert sich nicht während des lookups. Splay-Bäume, auf der anderen Seite pflegen Sie effizient durch die Neugestaltung der Baum in Antwort auf-lookups auf. So, auf die Häufig zugegriffen Elemente bewegen sich in Richtung der Spitze des Baumes und haben bessere lookup-Zeiten. Die Form der splay-Bäume ist nicht begrenzt, und variiert basierend auf was lookups durchgeführt werden.

    2. Gibt es keine harte und schnelle Regel. Allerdings, ein wesentlicher Unterschied zwischen den Strukturen ist, dass AVL-Bäume garantieren einen schnellen lookup (O(log n)) auf jedem Betrieb, während splay-Bäume können nur garantieren, dass jede Folge von n Operationen dauert höchstens O(n log n) Zeit. Dies bedeutet, dass, wenn Sie brauchen, real-time-Abfragen, die den AVL-Baum ist wahrscheinlich besser. Jedoch, splay-Bäume sind in der Regel viel schneller im Durchschnitt, wenn Sie so wollen, zum minimieren der Gesamt-Laufzeit von tree-lookups, die splay-Baum ist wahrscheinlich besser. Zusätzlich, splay-Bäume unterstützen auch einige Operationen, wie das aufteilen und Zusammenführen sehr effizient, während die entsprechenden AVL-Baum-Operationen sind aufwendiger und weniger effizient. Splay-Bäume sind speichereffizienter als AVL-Bäume, weil Sie nicht brauchen, um zu speichern, balance-Informationen in den Knoten. Jedoch, AVL-Bäume, die nützlich sind in Multithread-Umgebungen mit vielen lookups, da die Suche in einem AVL-Baum kann parallel durchgeführt werden, während Sie nicht in splay-Bäumen. Da splay-Bäume umzugestalten, sich basierend auf Suchvorgänge, wenn Sie nur Zugriff auf eine kleine Teilmenge der Elemente des Baumes, oder wenn Sie den Zugriff auf bestimmte Elemente viel mehr als andere, die splay-Baum besser als der AVL-Baum. Schließlich, splay-Bäume oft einfacher zu implementieren als AVL-Bäume, da die rotation Logik ist viel einfacher.

    3. Siehe (2)

    4. AVL-Baum einfügen, löschen und suchen dauert O(log n) Zeit jeder. Splay-Bäume haben die gleichen Garantien, aber die Garantie ist nur in einem amortisierten Sinne. Eine lange Sequenz von Vorgängen, die in höchstens O(n log n) Zeit, aber die einzelnen Vorgänge dauern als viel als O(n) Zeit.

    Hoffe, das hilft!

    InformationsquelleAutor der Antwort templatetypedef

  2. 3

    1) Was ist der Unterschied zwischen der AVL-Bäume und splay-Bäume????

    Sie sind ähnlich in der Struktur und die Operationen rufen wir Sie. Der Unterschied ist, dass in splay-Bäumen, die nach jeder operation, die wir versuchen zu halten, der Baum nahezu perfekt ausbalanciert, so dass zukünftige Operationen weniger Zeit in Anspruch nehmen.

    2) Auf welcher Grundlage wählen wir diese Bäume?

    Splay-Bäume sind immer besser als die binäre Suche Bäume, wenn Ihre Anwendung befasst sich mit einer Menge von Daten in der Struktur, aber benötigen Zugriff auf eine Teilmenge der Daten, die sehr Häufig als andere. In diesem Fall werden die Daten, die Sie Häufig zugreifen wird kommen, in der Nähe der Wurzel, die ein Ergebnis der splay. Auch, jeder Knoten kann dann zugegriffen werden, mit weniger Zeit als vorher.

    Als Allgemeine Regel für die Auswahl dieser Bäume, wenn Sie müssen "Durchschnittliche" log(n) mal über einen Zeitraum von Baum-Operationen verwenden Sie dann splay-Baum. Binärer Baum kann dies nicht garantieren.

    3), Was positiv ist und negativ von diesen Bäumen?

    Positives für beide ist, dass Sie sich rund um log(n) in beiden Datenstrukturen theoretisch.

    So genannten splay-Bäume haben durchschnittlich log(n) über eine Anzahl von Operationen. Dies bedeutet, dass, vielleicht haben Sie n Zeit-Komplexität für einen Vorgang mindestens einmal in dem Satz. Das wird aber kompensiert werden, wenn der Zugriff auf die Häufig Elemente.

    Den negativen der binäre Suchbaum ist, dass Sie brauchen, um das Glück zu haben, log(n) immer. Wenn der Schlüssel nicht zufällig sind, dann wird der Baum zu reduzieren, um eine Liste wie die form mit nur einer Seite.

    4) Was sind die Leistungen, die diese Bäume in Bezug auf die big-O-notation?

    Splay-Baum Log(n) im Durchschnitt für eine Gruppe von Baum-Operationen.
    Binary tree Log(n) nur, wenn Sie Ihre Schlüssel in random.

    Die Ergebnisse auf die Laufzeit sind hier offensichtlichsplay-Baum Laufzeit-profiling
    Sie können finden Sie in der Laufzeit-Unterschied bei der Suche mit und ohne Spreizung.

    InformationsquelleAutor der Antwort Harisankar Krishna Swamy

Schreibe einen Kommentar