Warum berücksichtigt der Spreizbaum-Rotationsalgorithmus sowohl den übergeordneten als auch den übergeordneten Knoten?

Ich verstehe nicht ganz, warum die Rotation in der Splay-Tree-Datenstruktur nicht nur das übergeordnete Element des Bewertungsknotens berücksichtigt, sondern auch das übergeordnete Element (Zick-Zack- und Zick-Zick-Operation). Warum würde das folgende nicht funktionieren:

Wenn wir beispielsweise einen neuen Knoten in den Baum einfügen, prüfen wir, ob wir ihn in den linken oder rechten Teilbaum einfügen. Wenn wir nach links einfügen, drehen wir das Ergebnis nach RECHTS und umgekehrt für den rechten Teilbaum. Rekursiv wäre es so

Tree insert(Tree root, Key k){
    if(k < root.key){
        root.setLeft(insert(root.getLeft(), key);
        return rotateRight(root);
    }
    //vice versa for right subtree
}

Das sollte das ganze "Spreiz" -Verfahren vermeiden, meinst du nicht auch?

Der einfachere Auswuchtalgorithmus kann im ungünstigsten Fall eine amortisierte Zeit von pro Umdrehung erfordern . Angenommen, der Baum ist nur ein völlig unausgeglichener Pfad der richtigen Kinder. Kein Knoten hat ein linkes Kind. Das einzige Blatt in diesem Baum ist der Baum mit dem maximalen Schlüssel. Wenn Sie diesen Schritt für Schritt bis zur Wurzel drehen, haben Sie n - 1 Rotationen verwendet, und der resultierende Baum ist immer noch völlig unausgeglichen.$\Omega(n)$$n-1$

Nehmen wir nun an, wir befördern jeden Knoten im Baum wiederholt nacheinander in absteigender Schlüsselreihenfolge und verwenden dabei den einfacheren Algorithmus. Nachdem alle Aktionen durchgeführt werden, hat der Baum in seinen ursprünglichen Zustand zurückgeführt , und wir haben ungefähr verwendet Umdrehungen. Daher erfordert jede Beförderung in dieser Sequenz im Durchschnitt Ω ( n $n^2/2$$\Omega(n)$$\Omega(n)$

Dieses schlechte Beispiel taucht in Sleators und Tarjans Original-Spreizbaum auf.

Der Spreizalgorithmus berücksichtigt nicht nur einen Knoten gleichzeitig, sondern zwei Knoten gleichzeitig. Insbesondere wenn der Knoten , der gespreizt wird, das rechte Kind eines rechten Kindes ist, dreht sich der Spreizalgorithmus zuerst$x$$x$$x$

Der Vorteil dieses komplexeren Algorithmus besteht darin, dass er nicht nur den Knoten, auf den zugegriffen wird, an die Wurzel bringt, sondern auch jeden Vorfahren des Knotens, auf den zugegriffen wird, ungefähr auf halber Strecke an die Wurzel , aber niemals mehr als eine konstante Anzahl von Ebenen vom Knoten entfernt Wurzel.

$O(\log n)$$\Omega(n)$

Kurz gesagt: Durch das Spreizen werden die Knoten langsam nach oben und nach unten verschoben.