Por que o algoritmo de rotação da árvore de reprodução leva em consideração o nó pai e o avô?

Não entendo bem por que a rotação na estrutura de dados da árvore de splay está levando em consideração não apenas o pai do nó de classificação, mas também o avô (operação em zig-zag e zig-zig). Por que o seguinte não funcionaria:

À medida que inserimos, por exemplo, um novo nó na árvore, verificamos se inserimos na subárvore esquerda ou direita. Se inserirmos à esquerda, giramos o resultado para a DIREITA e vice-versa para a subárvore direita. Recursivamente seria sth assim

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

Isso deve evitar todo o procedimento "splay", você não acha?

O algoritmo de balanceamento mais simples pode exigir tempo amortizado por rotação no pior caso. Suponha que a árvore seja apenas um caminho totalmente desequilibrado de crianças certas; nenhum nó tem um filho esquerdo. A única folha nesta árvore é a árvore com a chave máxima. Se você girar esse passo a passo até a raiz, usou rotações e a árvore resultante ainda está totalmente desequilibrada.$\Omega(n)$$n-1$

Agora, suponha que promovamos repetidamente todos os nós da árvore, um de cada vez, em ordem decrescente de chave, usando o algoritmo mais simples. Após todas as promoções, a árvore retornou ao seu estado original e usamos aproximadamente rotações. Assim, em média, cada promoção nesta sequência requer rotações ; além disso, posso repetir esse padrão para sempre. Portanto, o custo amortizado para esse algoritmo de promoção é .$n^2/2$$\Omega(n)$$\Omega(n)$

Este mau exemplo aparece no artigo original da árvore de espalhamento de Sleator e Tarjan.

O algoritmo splay considera não apenas um nó por vez, mas dois nós por vez. Em particular, se o nó que está sendo exibido é o filho certo de um filho certo, o algoritmo de espalhamento primeiro gira o pai de e, em seguida, somente .$x$$x$$x$

A vantagem desse algoritmo mais complexo é que ele não apenas traz o nó acessado para a raiz, mas também move todos os ancestrais do nó acessado aproximadamente até a metade da raiz , mas nunca move qualquer nó a mais do que um número constante de níveis para longe da raiz . raiz.

Sleator e Tarjan provam que o tempo amortizado por jogada é apenas . (A prova usa uma análise de caso tediosa usando uma função de potencial mágico; honestamente, se você estiver curioso, basta ler o artigo original.) É claro que uma única exibição pode levar o tempo , mas começando com uma árvore vazia, você precisa executar muitas inserções e splays para configurar um exemplo tão ruim.$O(\log n)$$\Omega(n)$

Mais brevemente: a distribuição move os nós para cima rapidamente e para baixo lentamente.