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 de árboles necesarias para reconfigurar 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 volteo 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 dos árboles binarios de n nodos tienen una distancia de rotación como máximo de 2 n - 6 , y algunos pares de árboles tienen exactamente esta distancia. Se desconoce la complejidad computacional de calcular la distancia de rotación. [2]
Definición
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 el hijo izquierdo o el hijo derecho de algún otro nodo, su padre , y en el que sigue al padre los enlaces de cualquier nodo eventualmente conducen al nodo raíz. (En algunas fuentes, los nodos descritos aquí se denominan "nodos internos", existe otro conjunto de nodos llamados "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, hay un subárbol de la misma forma, enraizado en x y que consta de todos los nodos que pueden llegar a x siguiendo los enlaces principales. Cada árbol binario tiene un ordenamiento de izquierda a derecha de sus nodos, su recorrido en orden , obtenido atravesando recursivamente el subárbol izquierdo (el subárbol en el hijo izquierdo de la raíz, si tal hijo existe), luego enumerando la raíz misma, y luego atravesar recursivamente el subárbol derecho. En un árbol de búsqueda binaria , cada nodo está asociado con una clave de búsqueda, y se requiere que el orden de izquierda a derecha sea 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 cambiar su orden de izquierda a derecha. Varias estructuras de datos de árbol de búsqueda binaria autoequilibradas utilizan estas rotaciones como una operación primitiva en sus algoritmos de reequilibrio. Una rotación opera en dos nodos x y Y , donde x es el padre de y , y reestructura el árbol por Cómo hacer y ser el padre de x y tomando el lugar de x en el árbol. Para liberar uno de los enlaces secundarios de y y hacer espacio para vincular x como un hijo de y , esta operación también puede necesitar mover uno de los hijos de y para que se convierta en un hijo de x . Hay dos variaciones de esta operación, una rotación a la derecha en la que Y comienza como el hijo izquierdo de x y x extremos como el hijo derecho de Y , y una rotación a la izquierda en la que Y comienza como el hijo derecho de x y x extremos como el hijo izquierdo de y . [2]
Dos árboles cualesquiera que tengan la misma secuencia de nodos de izquierda a derecha pueden transformarse entre sí mediante una secuencia de rotaciones. La distancia de rotación entre los dos árboles es el número de rotaciones en la secuencia de rotaciones más corta posible que realiza esta transformación. También se puede describir como la distancia de ruta más corta en un gráfico de rotación , un gráfico que tiene un vértice para cada árbol binario en una secuencia dada de nodos de izquierda a derecha y un borde para cada rotación entre dos árboles. [2] Este gráfico de rotación es exactamente el gráfico de vértices y aristas de un asociaedro . [3]
Equivalencia a la distancia de volteo
Dada una familia de triangulaciones de algún objeto geométrico, un giro es una operación que transforma una triangulación en otra quitando un borde entre dos triángulos y agregando la diagonal opuesta al cuadrilátero resultante. La distancia de volteo entre dos triangulaciones es el número mínimo de volteos necesarios para transformar una triangulación en otra. También se puede describir como la distancia de ruta más corta en un gráfico de volteo , un gráfico que tiene un vértice para cada triangulación y un borde para cada giro entre dos triangulaciones. Los giros y las distancias de giro se pueden definir de esta manera para varios tipos diferentes de triangulaciones, incluidas triangulaciones de conjuntos de puntos en el plano euclidiano , triangulaciones de polígonos y triangulaciones de variedades abstractas .
Existe una correspondencia uno a uno entre las triangulaciones de un polígono convexo dado , con un borde de raíz designado, y árboles binarios, tomando 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 el borde de la raíz designado como uno de sus lados, y dos nodos están vinculados 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 árboles binarios corresponden exactamente a volteos en las triangulaciones correspondientes. Por lo tanto, la distancia de rotación en árboles de ( n - 2) nodos corresponde exactamente a la distancia de giro en triangulaciones de polígonos convexos de n lados.
Valor máximo
Čulík y Wood (1982) definen la "columna derecha" de un árbol binario como la ruta obtenida partiendo de la raíz y siguiendo los enlaces secundarios derechos hasta llegar a un nodo que no tiene un hijo derecho. Si un árbol tiene la propiedad de que no todos los nodos pertenecen a la columna derecha, siempre existe una rotación derecha que aumenta la longitud de la columna derecha. Porque, en este caso, existe al menos un nodo x en la columna derecha que tiene un hijo izquierdo y que no está en la columna derecha. Realizar una rotación a la derecha en x e y se suma y de la columna derecha sin mover ningún otro nodo de la misma. Al aumentar repetidamente la longitud de la columna derecha, cualquier árbol de n nodos se puede transformar en un árbol único con el mismo orden de nodos en el que todos los nodos pertenecen a la columna derecha, en un máximo de n - 1 pasos. Dados cualesquiera dos árboles con el mismo orden de nodos, uno puede transformar uno en el otro transformando el primer árbol en un árbol con todos los nodos en la columna derecha, y luego invirtiendo 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 volteretas 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 columna derecha es la secuencia de triángulos que inciden en el extremo derecho del borde de la raíz, y el árbol en el que todos los vértices se encuentran en la columna 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 del borde de la raíz. No es posible que todas estas opciones den simultáneamente la distancia n - 1 del caso más desfavorable de cada triangulación inicial, lo que proporciona la mejora. [2]
Sleator, Tarjan y Thurston (1988) también utilizaron un argumento geométrico para mostrar que, para un número infinito de valores de n , la distancia máxima de rotación es exactamente 2 n - 6 . De nuevo utilizan la interpretación del problema en términos de vueltas de triangulaciones de polígonos convexos, e interpretan la triangulación inicial y final como las caras superior e inferior de un poliedro convexo con el polígono convexo en sí interpretado como un circuito hamiltoniano en este poliedro. Según esta interpretación, una secuencia de volteretas de una triangulación a la 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 la geometría hiperbólica tridimensional ) los poliedros tienen un gran volumen, pero todos los tetraedros en su interior tienen un volumen mucho menor, lo que implica que se necesitan muchos tetraedros en cualquier triangulación. Los árboles binarios obtenidos de traducir los conjuntos de caras superior e inferior de estos poliedros nuevamente en árboles tienen una distancia de rotación alta, al menos 2 n - 6 . [2]
Posteriormente, Pournin (2014) proporcionó una prueba de que para todo n ≥ 11 , la distancia máxima de rotación es exactamente 2 n - 6 . La prueba de Pournin es combinatoria y evita el uso de geometría hiperbólica. [3]
Complejidad computacional
¿Cuál es la complejidad de calcular la distancia de rotación entre dos árboles?
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 dos árboles cualesquiera implica que probar 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 que se pueda resolver en tiempo polinomial . Sin embargo, el algoritmo de Fordham calcula una distancia de rotación en tiempo lineal, pero solo permite 2 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 utiliza una tabla de búsqueda para encontrar el número de rotaciones necesarias para transformar un nodo de un tipo en otro.
La distancia de rotación entre dos árboles cualesquiera puede limitarse a un límite inferior, en la vista equivalente de triangulaciones poligonales, por el número de diagonales que deben eliminarse de una triangulación y reemplazarse por otras diagonales para producir la otra triangulación. También se puede acotar por el doble de este número, dividiendo el problema en subproblemas a lo largo de las diagonales compartidas entre ambas triangulaciones y luego aplicando el método de Čulík & 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 manejable de parámetros fijos para calcular exactamente la distancia de rotación. [5] [6]
La determinación de la complejidad de calcular la distancia de rotación exactamente sin parametrización sigue sin resolverse, y los mejores algoritmos conocidos actualmente para el problema se ejecutan en tiempo exponencial . [7] Sin embargo, la existencia del algoritmo de Fordham sugiere fuertemente que existe un algoritmo de tiempo lineal para calcular la distancia de rotación.
Referencias
- ^ a b c Čulík, Karel, II; Wood, Derick (1982), "Una nota sobre algunas medidas de similitud de árboles", Information Processing Letters , 15 (1): 39–42, doi : 10.1016 / 0020-0190 (82) 90083-7 , MR 0678031
- ^ a b c d e f Sleator, Daniel D .; Tarjan, Robert E .; Thurston, William P. (1988), "Distancia de rotación, triangulaciones y geometría hiperbólica", Journal of the American Mathematical Society , 1 (3): 647–681, doi : 10.1090 / S0894-0347-1988-0928904-4 , JSTOR 1990951 , MR 0928904
- ^ a b Pournin, Lionel (2014), "El diámetro de Associahedra", Advances in Mathematics , 259 : 13–42, doi : 10.1016 / j.aim.2014.02.035 , MR 3197650
- ^ Cleary, Sean; St. John, Katherine (2010), "Una aproximación de tiempo lineal para la distancia de rotación", Journal of Graph Algorithms and Applications , 14 (2): 385–390, doi : 10.7155 / jgaa.00212 , MR 2740180
- ^ Cleary, Sean; St. John, Katherine (2009), "La distancia de rotación es manejable con parámetros fijos", Information Processing Letters , 109 (16): 918–922, arXiv : 0903.0197 , doi : 10.1016 / j.ipl.2009.04.023 , MR 2541971
- ^ Lucas, Joan M. (2010), "Un tamaño de núcleo mejorado para la distancia de rotación en árboles binarios", Information Processing Letters , 110 (12-13): 481-484, doi : 10.1016 / j.ipl.2010.04.022 , MR 2667389
- ^ Kanj, Iyad; Sedgwick, Eric; Xia, Ge (2017), "Calcular la distancia de volteo entre triangulaciones", Geometría discreta y computacional , 58 (2): 313–344, arXiv : 1407.1525 , doi : 10.1007 / s00454-017-9867-x , MR 3679938