Dlaczego algorytm rotacji drzewa splay uwzględnia zarówno węzeł nadrzędny, jak i dziadek?

Nie do końca rozumiem, dlaczego rotacja w strukturze danych drzewa splay uwzględnia nie tylko element nadrzędny węzła oceniającego, ale także dziadka (operacja zygzak i zig-zig). Dlaczego następujące elementy nie działają:

Gdy wstawiamy na przykład nowy węzeł do drzewa, sprawdzamy, czy wstawiamy do lewego lub prawego poddrzewa. Jeśli wstawimy w lewo, obrócimy wynik PRAWO i odwrotnie dla prawego poddrzewa. Rekurencyjnie byłoby tak

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

To powinno unikać całej procedury „splay”, nie sądzisz?

Prostszy algorytm równoważenia może wymagać w najgorszym przypadku zamortyzowanego czasu na obrót. Załóżmy, że drzewo jest po prostu całkowicie niezrównoważoną ścieżką właściwych dzieci; żaden węzeł nie ma lewego dziecka. Jedynym liściem tego drzewa jest drzewo z maksymalnym kluczem. Jeśli obrócisz ten krok po kroku do korzenia, użyjesz n - 1 obrotu, a wynikowe drzewo nadal będzie całkowicie niezrównoważone.$\Omega(n)$$n-1$

$n^2/2$$\Omega(n)$$\Omega(n)$

Ten zły przykład pojawia się w oryginalnym papierze Splay drzewa Sleatora i Tarjana.

$x$$x$$x$

Zaletą tego bardziej złożonego algorytmu jest to, że nie tylko przenosi on dostęp do węzła do katalogu głównego, ale także przenosi każdego przodka dostępnego węzła mniej więcej w połowie drogi do katalogu głównego , ale nigdy nie przenosi żadnego węzła o więcej niż stałą liczbę poziomów od korzeń.

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

W skrócie: Rozgrywka przesuwa węzły szybko w górę i powoli w dół.