Rotación de árboles

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

Existe una inconsistencia en diferentes descripciones en cuanto a la definición de la dirección de las rotaciones. Algunos dicen que la dirección de la rotación depende del lado que los nodos del árbol se desplazan al mismo tiempo que otros dicen que depende de qué nodo toma el lugar de la raíz (enfrente de la primera). En este artículo se adopta el enfoque del lado a donde los nodos quedan cambiados.

Ilustración

Animation of tree rotations taking place.

La operación de rotación a la derecha, como se muestra en la imagen de la derecha se realiza con Q como la raíz y por lo tanto es un giro a la derecha en, o enraizado en, resultados Q. Esta operación en una rotación del árbol en el sentido horario. La operación inversa es la rotación a la izquierda, lo que resulta en un movimiento en sentido contrario a las agujas del reloj (la rotación izquierda se muestra más arriba tiene sus raíces en P). La clave para entender cómo funciona una rotación es entender sus limitaciones. En particular, el orden de las hojas del árbol (cuando se lee de izquierda a derecha, por ejemplo) no se puede cambiar (otra forma de pensar de él es que el orden en que las hojas se pueden visitar en un recorrido en el orden debe ser el mismo después de la operación como antes). Otra limitación es la característica principal de un árbol de búsqueda binaria, es decir, que el hijo derecho es mayor que el padre y el niño queda es menor que la de los padres. Observe que el hijo derecho de un hijo izquierdo de la raíz de un sub-árbol (por ejemplo nodo B en el diagrama de árbol con raíz en Q) puede convertirse en el hijo izquierdo de la raíz, que en sí mismo se convierte en el hijo derecho de la "nueva "root en el sub-árbol girado, sin violar ninguna de esas limitaciones. Como se puede ver en el diagrama, el orden de las hojas no cambia. La operación opuesta también conserva el orden y es el segundo tipo de rotación.

Asumiendo que esto es un árbol de búsqueda binaria, como se ha dicho, los elementos deben ser interpretados 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 a la derecha, los caracteres alfabéticos de capital se utilizan como marcadores de posición variables, mientras que las letras griegas minúsculas son marcadores de posición para todo un conjunto de variables. Los círculos representan los nodos individuales y los triángulos representan subárboles. Cada subárbol podría estar vacío, consistir en un único nodo, o consistir en cualquier número de nodos.

Ilustración detallada

Pictorial description of how rotations are made.

Cuando se hace girar un subárbol, el lado subárbol sobre la cual se hace girar aumenta su altura por un nodo mientras que el otro subárbol disminuye su altura. Esto hace que las rotaciones de árboles útiles para el reequilibrio de un árbol.

Utilizando la terminología de raíz para el nodo padre de los subárboles para girar, Pivot para el nodo que se convertirá en el nuevo nodo padre, RS lado rotación a girar y OS para el lado opuesto de la rotación. En el diagrama anterior para la raíz Q, el RS es C y el sistema operativo es P. El pseudo código para la rotación es:

Pivote = Root.OS Root.OS = Pivot.RS Pivot.RS = Raíz Root = Pivot

Esta es una operación constante de tiempo.

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

Invarianza en orden

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

Left tree: ((A, P, B), Q, C)        Right tree: (A, P, (B, Q, C))

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

def right_rotation(treenode):
  left, Q, C = treenode
  A, P, B = left
  return (A, P, (B, Q, C))

Otra forma de verlo es:

Giro a derechas del nodo Q:

Let P be Q's left child.
Set Q's left child to be P's right child.
Set P's right child to be Q.

Rotación izquierda del nodo P:

Let Q be P's right child.
Set P's right child to be Q's left child.
Set Q's left child to be P.

Todas las demás conexiones se dejan tal cual.

También hay rotaciones dobles, que son combinaciones de rotaciones de izquierda y derecha. Un doble rotación a la izquierda en X puede ser definido como una rotación a la derecha en el hijo derecho de X seguida de una rotación a la izquierda en X; Del mismo modo, una doble rotación a la derecha en X puede ser definido como una rotación a la izquierda en el hijo izquierdo de X seguida de una rotación a la derecha en X.

Rotaciones de reequilibrio

Pictorial description of how rotations cause rebalancing in an AVL tree.

Un árbol puede reequilibrarse mediante rotaciones. Después de una rotación, el lado de la rotación aumenta su altura por 1, mientras que el lado opuesto a la rotación disminuye su altura de manera similar. Por lo tanto, se puede aplicar estratégicamente rotaciones para nodos cuyos izquierda infantil y derecho difieren en altura por más de 1. auto-equilibrio árboles binarios de búsqueda aplicar esta operación automáticamente. Un tipo de árbol que utiliza esta técnica 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 una en la otra. Con esta distancia, el conjunto de los árboles binarios de n-nodo se convierte en un espacio métrico: la distancia es simétrica y positiva cuando se les da dos árboles diferentes, y satisface la desigualdad triangular.

Es un problema abierto si existe un algoritmo de tiempo polinómico para el cálculo de la distancia de rotación.

Daniel Sleator, Robert Tarjan y William Thurston mostraron que la distancia de rotación entre dos árboles n-nodo (para n = 11) es a lo sumo 2n - 6, y que un número infinito de pares de árboles son tan separados. ^[1]

Véase también

Portal:Ciencias de la Computación. Contenido relacionado con Ciencias de la Computación.
árbol AVL, árbol rojo-negro, y árbol ensanchamiento, tipos de estructuras de datos árbol binario de búsqueda que utilizan rotaciones para mantener el equilibrio.
Asociatividad de una operación binaria significa que la realización de una rotación de árbol en él no cambia el resultado final.
El algoritmo Day-Stout-Warren equilibra un BST desequilibrada.
Látice de Tamari, un conjunto parcialmente ordenado en el que los elementos pueden ser definidos como árboles binarios y el orden entre los elementos se definen por la rotación del árbol.

Referencias

↑ Sleator, Daniel D.; Tarjan, Robert E.; Thurston, William P. (1988), «Rotation distance, triangulations, and hyperbolic geometry», Journal of the American Mathematical Society (American Mathematical Society) 1 (3): 647-681, JSTOR 1990951, MR 928904, doi:10.2307/1990951 ..

Enlaces externos

Java applets demonstrating tree rotations
The AVL Tree Rotations Tutorial Archivado el 6 de febrero de 2012 en Wayback Machine. (RTF) by John Hargrove

Datos: Q541347

[1] Sleator, Daniel D.; Tarjan, Robert E.; Thurston, William P. (1988), «Rotation distance, triangulations, and hyperbolic geometry», Journal of the American Mathematical Society (American Mathematical Society) 1 (3): 647-681, JSTOR 1990951, MR 928904, doi:10.2307/1990951 ..

[1]