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

25

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?

Bober02
fonte

Respostas:

30

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.Ω(n)n1

mau exemplo por apenas girar

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 é .n2/2Ω(n)Ω(n)

mau exemplo continuou

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 .xxx

mostrando o mau exemplo

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(logn)Ω(n)

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

JeffE
fonte
Eu acho que os algoritmos de rotação são exatamente os mesmos, o meu é simplesmente mais curto e mais compreensível. Em vez de olhar para os avós, considero apenas os pais em uma etapa rotativa. Não produz exatamente o mesmo resultado?
precisa saber é o seguinte
Eu acho que você pode estar se referindo a dois algos de SPLAYING, um de cima para baixo, o outro de baixo para cima, e não o meu, está correto? Eu estava me referindo ao meu algo vs espalhar de baixo para cima
Bober02