Distancia de rotación

En matemáticas discretas e informática teórica , 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 un árbol en otro. Debido a una equivalencia combinatoria entre árboles binarios y triangulaciones de polígonos convexos, la distancia de rotación es equivalente a la distancia de inversión para triangulaciones de polígonos convexos .

La distancia de rotación fue definida por primera vez por Karel Čulík II y Derick Wood en 1982. ^{[ 1 ]} Cada par de árboles binarios de n nodos tiene una distancia de rotación de como máximo 2 n − 6 para todo n ≥ 11 , y algunos pares de árboles tienen exactamente esta distancia. Se desconoce la complejidad computacional del cálculo de la distancia de rotación. ^{[ 2 ]}

Un árbol binario es una estructura que consta de un conjunto de nodos, uno de los cuales se designa como nodo raíz, en el que cada nodo restante es hijo izquierdo o derecho de algún otro nodo, su padre , y en el que seguir los enlaces del padre desde cualquier nodo conduce finalmente al nodo raíz. (En algunas fuentes, los nodos descritos aquí se denominan "nodos internos"; existe otro conjunto de nodos denominados "nodos externos", cada nodo interno debe tener exactamente dos hijos, y cada nodo externo debe tener cero hijos. ^{[ 1 ]} La versión descrita aquí se puede obtener eliminando todos los nodos externos de dicho árbol).

Para cualquier nodo x en el árbol, existe un subárbol de la misma forma, con raíz en x y compuesto por todos los nodos que pueden alcanzar x siguiendo los enlaces padre. Cada árbol binario tiene un orden de izquierda a derecha de sus nodos, su recorrido en orden , que se obtiene recorriendo recursivamente el subárbol izquierdo (el subárbol del hijo izquierdo de la raíz, si existe tal hijo), luego listando la raíz misma y, finalmente, recorriendo recursivamente el subárbol derecho. En un árbol de búsqueda binaria , cada nodo está asociado con una clave de búsqueda, y el orden de izquierda a derecha debe ser consistente con el orden de las claves. ^{[ 2 ]}

Una rotación de árbol es una operación que cambia la estructura de un árbol binario sin modificar su orden de izquierda a derecha. Varias estructuras de datos de árboles de búsqueda binaria autoequilibrados utilizan estas rotaciones como una operación primitiva en sus algoritmos de reequilibrio. Una rotación opera sobre dos nodos x e y , donde x es el padre de y , y reestructura el árbol haciendo que y sea el padre de x y ocupe el lugar de x en el árbol. Para liberar uno de los enlaces hijos de y y crear espacio para enlazar x como hijo de y , esta operación también puede requerir que uno de los hijos de y se convierta en hijo de x . Existen dos variantes de esta operación: una rotación a la derecha , en la que y comienza como hijo izquierdo de x y x termina como hijo derecho de y , y una rotación a la izquierda, en la que y comienza como hijo derecho de x y x termina como hijo izquierdo de y . ^{[ 2 ]}

Dos árboles cualesquiera que tengan la misma secuencia de nodos de izquierda a derecha pueden transformarse uno en el otro mediante una secuencia de rotaciones. La distancia de rotación entre los dos árboles es el número de rotaciones en la secuencia más corta posible que realiza esta transformación. También puede describirse como la distancia del camino más corto en un grafo de rotación , un grafo que tiene un vértice por cada árbol binario en una secuencia de nodos de izquierda a derecha dada y una arista por cada rotación entre dos árboles. ^{[ 2 ]} Este grafo de rotación es exactamente el grafo de vértices y aristas de un asociaedro . ^{[ 3 ]}

Dada una familia de triangulaciones de un objeto geométrico, una inversión es una operación que transforma una triangulación en otra eliminando una arista entre dos triángulos y añadiendo la diagonal opuesta al cuadrilátero resultante. La distancia de inversión entre dos triangulaciones es el número mínimo de inversiones necesarias para transformar una triangulación en otra. También se puede describir como la distancia del camino más corto en un grafo de inversión , un grafo que tiene un vértice por cada triangulación y una arista por cada inversión entre dos triangulaciones. Las inversiones y las distancias de inversión se pueden definir de esta manera para varios tipos diferentes de triangulaciones, incluidas las triangulaciones de conjuntos de puntos en el plano euclidiano , las triangulaciones de polígonos y las triangulaciones de variedades abstractas .

Existe una correspondencia biunívoca entre las triangulaciones de un polígono convexo dado , con una arista raíz designada, y los árboles binarios, transformando las triangulaciones de polígonos de n lados en árboles binarios con n − 2 nodos. En esta correspondencia, cada triángulo de una triangulación corresponde a un nodo en un árbol binario. El nodo raíz es el triángulo que tiene la arista raíz designada como uno de sus lados, y dos nodos se vinculan como padre e hijo en el árbol cuando los triángulos correspondientes comparten una diagonal en la triangulación. Bajo esta correspondencia, las rotaciones en los árboles binarios corresponden exactamente a las inversiones en las triangulaciones correspondientes. Por lo tanto, la distancia de rotación en árboles de ( n − 2) nodos corresponde exactamente a la distancia de inversión en triangulaciones de polígonos convexos de n lados.

Čulík y Wood (1982) definen la "espina dorsal derecha" de un árbol binario como el camino que se obtiene partiendo de la raíz y siguiendo los enlaces de los hijos derechos hasta llegar a un nodo que no tiene hijos derechos. Si un árbol tiene la propiedad de que no todos los nodos pertenecen a la espina dorsal derecha, siempre existe una rotación a la derecha que aumenta la longitud de dicha espina. En este caso, existe al menos un nodo x en la espina dorsal derecha que tiene un hijo izquierdo y que no pertenece a ella. Al realizar una rotación a la derecha sobre x e y, se añade y a la espina dorsal derecha sin eliminar ningún otro nodo. Al aumentar repetidamente la longitud de la espina dorsal derecha, cualquier árbol de n nodos puede transformarse en un único árbol con el mismo orden de nodos en el que todos los nodos pertenecen a la espina dorsal derecha, en un máximo de n − 1 pasos. Dados dos árboles cualesquiera con el mismo orden de nodos, se puede transformar uno en el otro transformando el primer árbol en un árbol con todos los nodos en la columna vertebral derecha, y luego revirtiendo la misma transformación del segundo árbol, en un total de como máximo 2 n − 2 pasos. Por lo tanto, como demostraron Čulík y Wood (1982) , la distancia ^de rotación entre dos árboles cualesquiera es como máximo 2 n − 2. ^{[ 1} ]

Al considerar el problema en términos de volteos de polígonos convexos en lugar de rotaciones de árboles, Sleator, Tarjan y Thurston (1988) pudieron demostrar que la distancia de rotación es como máximo 2 n − 6 . En términos de triangulaciones de polígonos convexos, la espina derecha es la secuencia de triángulos incidentes al extremo derecho de la arista raíz, y el árbol en el que todos los vértices se encuentran en la espina corresponde a una triangulación en abanico para este vértice. La idea principal de su mejora es intentar voltear ambas triangulaciones dadas a una triangulación en abanico para cualquier vértice, en lugar de solo la del extremo derecho de la arista raíz. No es posible que todas estas opciones den simultáneamente la distancia en el peor caso n − 1 desde cada triangulación inicial, dando la mejora. ^{[ 2 ]}

Sleator, Tarjan y Thurston (1988) también utilizaron un argumento geométrico para demostrar que, para infinitos valores de n , la distancia máxima de rotación es exactamente 2n − 6. Nuevamente, utilizan la interpretación del problema en términos de giros de triangulaciones de polígonos convexos, e interpretan la triangulación inicial y final como las caras superior e inferior de un poliedro convexo , interpretando este último como un circuito hamiltoniano . Bajo esta interpretación, una secuencia de giros de una triangulación a otra puede traducirse en una colección de tetraedros que triangulan el poliedro tridimensional dado. Encuentran una familia de poliedros con la propiedad de que (en geometría hiperbólica tridimensional ) los poliedros tienen un gran volumen, pero todos los tetraedros dentro de ellos tienen un volumen mucho menor, lo que implica que se necesitan muchos tetraedros en cualquier triangulación. Los árboles binarios obtenidos al trasladar los conjuntos de caras superior e inferior de estos poliedros de nuevo a árboles tienen una gran distancia de rotación, al menos 2 n − 6 . ^{[ 2 ]}

Posteriormente, Pournin (2014) proporcionó una demostración de que para todo n ≥ 11 , la distancia máxima de rotación es exactamente 2n − 6. La demostración de Pournin es combinatoria y evita el uso de la geometría hiperbólica. ^{[ 3 ]}

Además de definir la distancia de rotación, Čulík y Wood (1982) preguntaron por la complejidad computacional de calcular la distancia de rotación entre dos árboles dados. La existencia de secuencias de rotación cortas entre cualquier par de árboles implica que comprobar si la distancia de rotación es como máximo k pertenece a la clase de complejidad NP , pero no se sabe que sea NP-completa , ni se sabe que sea resoluble en tiempo polinomial .

La distancia de rotación entre dos árboles cualesquiera puede acotarse inferiormente, en la vista equivalente de triangulaciones poligonales, por el número de diagonales que deben eliminarse de una triangulación y sustituirse por otras diagonales para producir la otra triangulación. También puede acotarse superiormente por el doble de este número, dividiendo el problema en subproblemas a lo largo de las diagonales compartidas entre ambas triangulaciones y aplicando el método de Čulík y Wood (1982) a cada subproblema. Este método proporciona un algoritmo de aproximación para el problema con una razón de aproximación de dos. ^{[ 4 ]} Un enfoque similar de partición en subproblemas a lo largo de diagonales compartidas conduce a un algoritmo tratable de parámetros fijos para calcular la distancia de rotación con exactitud. ^{[ 5 ] [ 6 ]}

Determinar la complejidad de calcular la distancia de rotación con exactitud sin parametrización sigue sin resolverse, y los mejores algoritmos conocidos actualmente para el problema se ejecutan en tiempo exponencial . ^{[ 7 ]}

Aunque se desconoce la complejidad de la distancia de rotación, existen varias variantes para las cuales la distancia de rotación se puede resolver en tiempo polinomial.

En álgebra abstracta , cada elemento del grupo F de Thompson tiene una presentación que utiliza dos generadores . Encontrar la longitud mínima de dicha presentación equivale a encontrar la distancia de rotación entre dos árboles binarios, permitiendo únicamente rotaciones en el nodo raíz y su hijo derecho. El algoritmo de Fordham calcula la distancia de rotación bajo esta restricción en tiempo lineal. El algoritmo clasifica los nodos del árbol en 7 tipos y utiliza una tabla de consulta para determinar el número de rotaciones necesarias para transformar un nodo de un tipo en otro. La suma de los costos de todas las transformaciones es la distancia de rotación. ^{[ 8 ]}

En dos variantes adicionales, una solo permite rotaciones tales que el pivote de la rotación sea un hijo no hoja de la raíz y el otro hijo de la raíz sea una hoja, mientras que la otra solo permite rotaciones en nodos del brazo derecho (nodos que están en el camino desde la raíz hasta su hoja más a la derecha). Ambas variantes dan como resultado un semirretículo de encuentro , cuya estructura se explota para derivar un${\displaystyle O(n^{2})}$algoritmo. ^{[ 9 ] [ 10 ]}