En matemáticas discretas , la rotación de árboles es una operación sobre 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 y otro 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 resulta en un mejor rendimiento de muchas operaciones del árbol.
Existe una inconsistencia en las diferentes descripciones en cuanto a la definición del sentido de rotación . Algunos dicen que la dirección de rotación refleja la dirección en la que se mueve un nodo al girar (un hijo izquierdo que gira hacia la ubicación de su padre es una rotación hacia la derecha), mientras que otros dicen que la dirección de rotación refleja qué subárbol está girando (un subárbol izquierdo que gira hacia la ubicación de su padre es una rotación hacia la izquierda, lo opuesto a la anterior). Este artículo adopta el enfoque del movimiento direccional del nodo giratorio.
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 o con raíz 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 hacia la izquierda, que da como resultado un movimiento en sentido contrario a las agujas del reloj (la rotación hacia la izquierda que se muestra arriba tiene su raíz en P ). La clave para comprender cómo funciona una rotación es comprender sus limitaciones. 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 del operación como antes). Otra restricción es la propiedad principal de un árbol de búsqueda binario, es decir, que todos los nodos del subárbol derecho son mayores que el padre y todos los nodos del subárbol izquierdo son menores 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 " nueva" raíz en el subárbol rotado, sin violar ninguna de esas restricciones. Como se ve 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úscula se utilizan como marcadores de posición de variables, mientras que las letras griegas 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 de cualquier número de nodos.
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 padre de los subárboles a rotar, Pivote para el nodo que se convertirá en el nuevo nodo padre, 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:
let Pivot = Root.OSRoot.OS = Pivote.RSPivote.RS = RaízRaíz = Pivote
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.
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 sencillo. El siguiente es un ejemplo de código Python que realiza ese cálculo:
def rotación_derecha ( nododeárbol ): """Gira el árbol especificado hacia la derecha.""" izquierda , Q , C = nodo de árbol A , P , B = izquierda return ( A , P , ( B , Q , C )) Otra forma de verlo es:
Rotación hacia la derecha del nodo Q:
Sea P el hijo izquierdo de Q.Establezca que el hijo izquierdo de Q sea el hijo derecho de P.[Establezca el padre del hijo derecho de P en Q]Establezca que el hijo derecho de P sea Q.[Establezca el padre de Q en P]
Rotación izquierda del nodo P:
Sea Q el hijo derecho de P.Establezca que el hijo derecho de P sea el hijo izquierdo de Q.[Establezca el padre del hijo izquierdo de Q en P]Establezca que el hijo izquierdo de Q sea P.[Establezca el padre de P en Q]
Todas las demás conexiones se dejan como están.
También hay rotaciones dobles , que son combinaciones de rotaciones hacia la izquierda y hacia la derecha. Una doble rotación a la izquierda en X se puede definir 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 doble rotación 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 . Sólo requieren un tiempo constante porque son transformaciones locales : sólo operan en 5 nodos y no necesitan examinar el resto del árbol.
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 rotaciones estratégicamente a los nodos cuyos hijos 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 .
¿Se puede calcular la distancia de rotación entre dos árboles binarios en tiempo polinómico?
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 polinómico para calcular la distancia de rotación, aunque varias variantes del problema de la distancia de rotación admiten algoritmos de tiempo polinómico. [1] [2] [3]
Daniel Sleator , Robert Tarjan y William Thurston demostraron que la distancia de rotación entre dos árboles de n -nodos 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 suficientemente grande. [4] Lionel Pournin demostró que, de hecho, tales pares existen siempre que n ≥ 11. [5]