Espalhe a árvore com um número ímpar de rotações

Ao inserir um item em uma árvore de dispersão, as rotações são realizadas em pares com base em um padrão em zig-zag ou zig-zig. Quando há um número ímpar de rotações a serem executadas, pode-se fazer a rotação extra começando na folha ou salvar a rotação extra e fazê-lo na raiz. Isso importa?

Por exemplo, na imagem anexada, insiro um 4 em um BST e o "splay" na raiz. Na parte superior da figura, localizo primeiro o par de zig-zig no nó da folha e faço a distribuição em zig-zag a partir do fundo, deixando uma rotação final correta na raiz. Na parte inferior da figura, primeiro faço a rotação ímpar a partir da folha e depois faço uma zig-zig na raiz.

Qual é correto? Ou os dois levarão ao desempenho habitual das árvores de jogo?

$1+3(r(t)-r(x))$$t$$r(u):=\lfloor \log (\text{weight of $u$'s subtree}) \rfloor$$\Phi(T)=\sum_{x \text{ node of } T} r(t)$

A prova do lema de acesso analisa os custos de uma única operação de zig / zig-zag / zig-zig etc. Você recebe

1. $1+3(r_+(u) - r(u))$$r_+$$u$

2. $3(r_+(u) - r(u))$

$1+3(r(t)-r(x))$

Se você alterar a ordem das rotações, obterá a mesma soma. A única diferença é que agora o '' +1 '' vem da primeira rotação e não da última rotação. Você pode até fazer a rotação em zigue-zague no meio. Todas as análises (clássicas) adicionais se baseiam no lema de acesso.

No entanto, a razão pela qual você executa a rotação única por último é que você não sabe se a profundidade do nó é par ou ímpar antecipadamente.