¿Por qué el algoritmo de rotación del árbol splay tiene en cuenta tanto el nodo padre como el abuelo?

25

No entiendo bien por qué la rotación en la estructura de datos del árbol de separación está teniendo en cuenta no solo al padre del nodo de calificación, sino también al abuelo (operación zig-zag y zig-zig). ¿Por qué no funcionaría lo siguiente?

A medida que insertamos, por ejemplo, un nuevo nodo en el árbol, verificamos si insertamos en el subárbol izquierdo o derecho. Si insertamos en la izquierda, rotamos el resultado DERECHA, y viceversa para el subárbol derecho. Recurrentemente sería algo así

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

Eso debería evitar todo el procedimiento de "separación", ¿no le parece?

Bober02
fuente

Respuestas:

30

El algoritmo de equilibrio más simple puede requerir tiempo amortizado por rotación en el peor de los casos. Supongamos que el árbol es solo un camino totalmente desequilibrado de niños correctos; ningún nodo tiene un hijo izquierdo. La única hoja en este árbol es el árbol con la clave máxima. Si gira este paso a paso hasta la raíz, ha utilizado rotaciones , y el árbol resultante todavía está totalmente desequilibrado.n - 1Ω(n)n1

mal ejemplo para solo rotar

Ahora supongamos que promovemos repetidamente cada nodo en el árbol, uno a la vez, en orden de teclas decreciente, usando el algoritmo más simple. Después de realizar todas las promociones, el árbol ha vuelto a su estado original, y hemos utilizado aproximadamente rotaciones. Por lo tanto, en promedio, cada promoción en esta secuencia requiere rotaciones ; Además, puedo repetir este patrón para siempre. Entonces, el costo amortizado para este algoritmo de promoción es .Ω ( n ) Ω ( n )n2/2Ω(n)Ω(n)

mal ejemplo continuado

Este mal ejemplo aparece en Sleator y el papel original del árbol de despliegue de Tarjan.

El algoritmo splay considera no solo un nodo a la vez, sino dos nodos a la vez. En particular, si el nodo está desplegando es el hijo derecho de un hijo derecho, el algoritmo de visualización primero gira al padre de , y solo luego gira .x xxxx

mostrando el mal ejemplo

La ventaja de este algoritmo más complejo es que no solo lleva el nodo accedido a la raíz, sino que también mueve a cada antepasado del nodo accedido aproximadamente a la mitad de la raíz , pero nunca mueve ningún nodo más que un número constante de niveles fuera del raíz.

Sleator y Tarjan prueban que el tiempo amortizado por juego es solo . (La prueba utiliza un tedioso análisis de casos utilizando una función de potencial mágico; sinceramente, si tiene curiosidad, simplemente lea el documento original). Por supuesto, una sola sesión puede llevar tiempo , pero comenzando con un árbol vacío, tienes que realizar muchas inserciones y splays para configurar un mal ejemplo.Ω ( n )O(logn)Ω(n)

Más brevemente: la propagación mueve los nodos hacia arriba rápidamente y hacia abajo lentamente.

JeffE
fuente
Creo que los algoritmos de rotación son exactamente los mismos, el mío es simplemente más corto y más comprensible. En lugar de mirar a los abuelos, solo considero a los padres en un solo paso rotativo. ¿No tiene exactamente el mismo resultado?
Bober02
Supongo que te estarías refiriendo a dos algos SPLAYING, uno de arriba hacia abajo y el otro de abajo hacia arriba, y no el mío, ¿es correcto? Me refería a mi algo vs juego de abajo hacia arriba
Bober02