Rotación de árboles

Rotación de árboles genéricos.

En matemáticas discretas, la rotación de árboles es una operación en un árbol binario que cambia la estructura sin interferir con el orden de los elementos. Una rotación de árbol mueve un nodo hacia arriba en el árbol y un nodo hacia abajo. Se utiliza para cambiar la forma del árbol y, en particular, para disminuir su altura moviendo los subárboles más pequeños hacia abajo y los subárboles más grandes hacia arriba, lo que da como resultado un rendimiento mejorado de muchas operaciones del árbol.

Existe una inconsistencia en las diferentes descripciones en cuanto a la definición de la dirección de rotación. Algunos dicen que la dirección de rotación refleja la dirección en la que se mueve un nodo al rotar (un hijo izquierdo que gira hacia la ubicación de su padre es una rotación derecha), mientras que otros dicen que la dirección de rotación refleja qué subárbol está girando (un el subárbol izquierdo que gira hacia la ubicación de su padre es una rotación a la izquierda, lo opuesto al anterior). Este artículo adopta el enfoque del movimiento direccional del nodo giratorio.

Ilustración

La operación de rotación a la derecha, como se muestra en la imagen adyacente, se realiza con Q como raíz y, por lo tanto, es una rotación a la derecha sobre, o enraizada en, Q. Esta operación da como resultado una rotación del árbol en el sentido de las agujas del reloj. La operación inversa es la rotación a la izquierda, que da como resultado un movimiento en sentido contrario a las agujas del reloj (la rotación a la izquierda que se muestra arriba tiene su raíz en P). La clave para entender cómo funciona una rotación es entender sus restricciones. En particular, el orden de las hojas del árbol (cuando se lee de izquierda a derecha, por ejemplo) no puede cambiar (otra forma de pensarlo es que el orden en que se visitarían las hojas en un recorrido en orden debe ser el mismo después de la funcionamiento como antes). Otra restricción es la propiedad principal de un árbol de búsqueda binario, a saber, que el hijo derecho es mayor que el padre y el hijo izquierdo es menor que el padre. Observe que el hijo derecho de un hijo izquierdo de la raíz de un subárbol (por ejemplo, el nodo B en el diagrama del árbol con raíz en Q) puede convertirse en el hijo izquierdo de la raíz, que a su vez se convierte en el hijo derecho de & #34;nuevo" root en el subárbol rotado, sin violar ninguna de esas restricciones. Como puede ver en el diagrama, el orden de las hojas no cambia. La operación opuesta también preserva el orden y es el segundo tipo de rotación.

Suponiendo que se trata de un árbol de búsqueda binario, como se indicó anteriormente, los elementos deben interpretarse como variables que se pueden comparar entre sí. Los caracteres alfabéticos de la izquierda se utilizan como marcadores de posición para estas variables. En la animación de la derecha, los caracteres alfabéticos en mayúsculas se utilizan como marcadores de posición de variables, mientras que las letras griegas en minúsculas son marcadores de posición para un conjunto completo de variables. Los círculos representan nodos individuales y los triángulos representan subárboles. Cada subárbol puede estar vacío, constar de un solo nodo o constar de cualquier número de nodos.

Ilustración detallada

Descripción ilustrativa de cómo se hacen las rotaciones.

Cuando se gira un subárbol, el lado del subárbol sobre el que se gira aumenta su altura en un nodo mientras que el otro subárbol disminuye su altura. Esto hace que las rotaciones de árboles sean útiles para reequilibrar un árbol.

Considere la terminología de Raíz para el nodo principal de los subárboles a rotar, Pivote para el nodo que se convertirá en el nuevo nodo principal, RS para el lado de rotación y OS para el lado opuesto de rotación. Para la raíz Q en el diagrama anterior, RS es C y OS es P. Usando estos términos, el pseudocódigo para la rotación es:

Pivot = Root.OS
Root.OS = Pivot.RS
Pivot.RS = Root
Root = Pivot

Esta es una operación de tiempo constante.

El programador también debe asegurarse de que el padre de la raíz apunte al pivote después de la rotación. Además, el programador debe tener en cuenta que esta operación puede dar como resultado una nueva raíz para todo el árbol y tener cuidado de actualizar los punteros en consecuencia.

Invariancia en el orden

La rotación del árbol hace que el recorrido en orden del árbol binario sea invariante. Esto implica que el orden de los elementos no se ve afectado cuando se realiza una rotación en cualquier parte del árbol. Aquí están los recorridos en orden de los árboles que se muestran arriba:

Árbol izquierdo: (A, P, B), Q, C) Árbol derecho: (A, P, (B, Q, C))

Calcular uno a partir del otro es muy simple. El siguiente es un ejemplo de código de Python que realiza ese cálculo:

def right_rotation()Treenode): ""Rotar el árbol especificado a la derecha."" izquierda, Q, C = Treenode A, P, B = izquierda retorno ()A, P, ()B, Q, C)

Otra forma de verlo es:

Rotación derecha del nodo Q:

Deja que P sea el hijo izquierdo de Q.
Ponga el niño izquierdo de Q para ser el hijo derecho de P.
[Padre de hijo derecho de Set P a Q]
El niño adecuado de P es Q.
[Padre de Set Q a P]

Rotación a la izquierda del nodo P:

Deja que Q sea el hijo adecuado de P.
El niño derecho de P es el hijo izquierdo de Q.
[El padre del hijo izquierdo de Set Q a P]
Ponga el niño izquierdo de Q para ser P.
[Padre de Set P a Q]

Todas las demás conexiones se dejan como están.

También hay rotaciones dobles, que son combinaciones de rotaciones izquierda y derecha. Una rotación doble a la izquierda en X puede definirse como una rotación a la derecha en el hijo derecho de X seguida de una rotación a la izquierda en X; De manera similar, una rotación doble a la derecha en X se puede definir como una rotación a la izquierda en el hijo izquierdo de X seguida de una rotación a la derecha en X.

Las rotaciones de árboles se utilizan en varias estructuras de datos de árboles, como árboles AVL, árboles rojo-negro, árboles WAVL, árboles splay y treaps. Solo requieren tiempo constante porque son transformaciones locales: solo operan en 5 nodos y no necesitan examinar el resto del árbol.

Rotaciones para reequilibrio

Descripción ilustrativa de cómo las rotaciones causan rebalanzamiento en un árbol AVL.

Un árbol se puede reequilibrar mediante rotaciones. Después de una rotación, el lado de la rotación aumenta su altura en 1, mientras que el lado opuesto a la rotación disminuye su altura de manera similar. Por lo tanto, se pueden aplicar estratégicamente rotaciones a los nodos cuyo hijo izquierdo y derecho difieren en altura en más de 1. Los árboles de búsqueda binarios autoequilibrados aplican esta operación automáticamente. Un tipo de árbol que utiliza esta técnica de reequilibrio es el árbol AVL.

Distancia de rotación

La distancia de rotación entre dos árboles binarios con el mismo número de nodos es el número mínimo de rotaciones necesarias para transformar uno en el otro. Con esta distancia, el conjunto de árboles binarios de n-nodos se convierte en un espacio métrico: la distancia es simétrica, positiva cuando se dan dos árboles diferentes y satisface la desigualdad del triángulo.

Es un problema abierto si existe un algoritmo de tiempo polinomial para calcular la distancia de rotación. Sin embargo, el algoritmo de Fordham calcula una distancia en tiempo lineal, pero solo permite dos tipos de rotaciones: (ab)c = a(bc) y a((bc)d) = a(b(cd)). El algoritmo de Fordham se basa en una clasificación de nodos en 7 tipos, y se usa una tabla de búsqueda para encontrar el número de rotaciones necesarias para transformar un nodo de un tipo en otro.

Daniel Sleator, Robert Tarjan y William Thurston demostraron que la distancia de rotación entre dos árboles de nodos n cualesquiera (para n ≥ 11) es como máximo 2 n − 6, y que algunos pares de árboles están tan separados tan pronto como n es lo suficientemente grande. Lionel Pournin demostró que, de hecho, tales pares existen siempre que n ≥ 11.