En informática , un árbol cartesiano es un árbol binario derivado de una secuencia de números distintos. Para construir el árbol cartesiano, establezca su raíz como el número mínimo de la secuencia y construya recursivamente sus subárboles izquierdo y derecho a partir de las subsecuencias antes y después de este número. Se define de forma única como un min-heap cuyo recorrido simétrico (en orden) devuelve la secuencia original.
Los árboles cartesianos fueron introducidos por Vuillemin (1980) en el contexto de las estructuras de datos de búsqueda de rangos geométricos . También se han utilizado en la definición de las estructuras de datos treap y de árboles de búsqueda binaria aleatorizados para problemas de búsqueda binaria , en algoritmos de ordenamiento por comparación que funcionan de manera eficiente con entradas casi ordenadas y como base para algoritmos de coincidencia de patrones . Un árbol cartesiano para una secuencia se puede construir en tiempo lineal .
Los árboles cartesianos se definen utilizando árboles binarios , que son una forma de árbol con raíz . Para construir el árbol cartesiano para una secuencia dada de números distintos, establezca su raíz como el número mínimo en la secuencia, [1] y construya recursivamente sus subárboles izquierdo y derecho a partir de las subsecuencias antes y después de este número, respectivamente. Como caso base, cuando una de estas subsecuencias está vacía, no hay ningún hijo izquierdo o derecho. [2]
También es posible caracterizar el árbol cartesiano directamente en lugar de hacerlo de forma recursiva, utilizando sus propiedades de ordenación. En cualquier árbol, el subárbol que tiene su raíz en cualquier nodo está formado por todos los demás nodos que pueden alcanzarlo siguiendo repetidamente los punteros principales. El árbol cartesiano para una secuencia de números distintos se define mediante las siguientes propiedades:
Estas dos definiciones son equivalentes: el árbol definido recursivamente como se describió anteriormente es el único árbol que tiene las propiedades enumeradas anteriormente. Si una secuencia de números contiene repeticiones, se puede determinar un árbol cartesiano para ella siguiendo una regla de desempate consistente antes de aplicar la construcción anterior. Por ejemplo, el primero de dos elementos iguales puede tratarse como el menor de los dos. [2]
Los árboles cartesianos fueron introducidos y nombrados por Vuillemin (1980), quien los utilizó como un ejemplo de la interacción entre la combinatoria geométrica y el diseño y análisis de estructuras de datos . En particular, Vuillemin utilizó estas estructuras para analizar la complejidad del caso promedio de las operaciones de concatenación y división en árboles de búsqueda binarios . El nombre se deriva del sistema de coordenadas cartesianas para el plano: en una versión de esta estructura, como en la aplicación de búsqueda de rango bidimensional analizada a continuación, un árbol cartesiano para un conjunto de puntos tiene el orden ordenado de los puntos por sus coordenadas como su orden de recorrido simétrico, y tiene la propiedad heap de acuerdo con las coordenadas de los puntos. Vuillemin describió tanto esta versión geométrica de la estructura como la definición aquí en la que un árbol cartesiano se define a partir de una secuencia. El uso de secuencias en lugar de coordenadas de puntos proporciona una configuración más general que permite que el árbol cartesiano también se aplique a problemas no geométricos. [2]
Un árbol cartesiano se puede construir en tiempo lineal a partir de su secuencia de entrada. Un método es procesar los valores de la secuencia en orden de izquierda a derecha, manteniendo el árbol cartesiano de los nodos procesados hasta ahora, en una estructura que permita el recorrido tanto hacia arriba como hacia abajo del árbol. Para procesar cada nuevo valor , comience en el nodo que representa el valor anterior a en la secuencia y siga la ruta desde este nodo hasta la raíz del árbol hasta encontrar un valor menor que . El nodo se convierte en el hijo derecho de , y el hijo derecho anterior de se convierte en el nuevo hijo izquierdo de . El tiempo total para este procedimiento es lineal, porque el tiempo empleado en buscar el padre de cada nuevo nodo se puede cargar contra la cantidad de nodos que se eliminan de la ruta más a la derecha en el árbol. [3]
Un algoritmo de construcción lineal alternativo se basa en el problema de todos los valores más pequeños más cercanos . En la secuencia de entrada, defina el vecino izquierdo de un valor como el valor que ocurre antes de , es más pequeño que , y está más cerca en posición que cualquier otro valor más pequeño. El vecino derecho se define simétricamente. La secuencia de vecinos izquierdos se puede encontrar mediante un algoritmo que mantiene una pila que contiene una subsecuencia de la entrada. Para cada nuevo valor de secuencia , la pila se vacía hasta que está vacía o su elemento superior es más pequeño que , y luego se empuja hacia la pila. El vecino izquierdo de es el elemento superior en el momento en que se empuja. Los vecinos derechos se pueden encontrar aplicando el mismo algoritmo de pila al reverso de la secuencia. El padre de en el árbol cartesiano es el vecino izquierdo de o el vecino derecho de , el que exista y tenga un valor mayor. Los vecinos izquierdo y derecho también se pueden construir de manera eficiente mediante algoritmos paralelos , lo que hace que esta formulación sea útil en algoritmos paralelos eficientes para la construcción de árboles cartesianos. [4]
Otro algoritmo de tiempo lineal para la construcción de árboles cartesianos se basa en divide-y-vencerás . El algoritmo construye recursivamente el árbol en cada mitad de la entrada y luego fusiona los dos árboles. El proceso de fusión involucra solo los nodos en las espinas izquierda y derecha de estos árboles: la espina izquierda es la ruta obtenida al seguir las aristas de los hijos izquierdos desde la raíz hasta llegar a un nodo sin hijos izquierdos, y la espina derecha se define simétricamente. Como con cualquier ruta en un min-heap, ambas espinas tienen sus valores en orden ordenado, desde el valor más pequeño en su raíz hasta su valor más grande al final de la ruta. Para fusionar los dos árboles, aplique un algoritmo de fusión a la espina derecha del árbol izquierdo y a la espina izquierda del árbol derecho, reemplazando estas dos rutas en dos árboles por una única ruta que contenga los mismos nodos. En la ruta fusionada, el sucesor en el orden ordenado de cada nodo del árbol izquierdo se coloca en su hijo derecho, y el sucesor de cada nodo del árbol derecho se coloca en su hijo izquierdo, la misma posición que se utilizó anteriormente para su sucesor en la columna vertebral. Los hijos izquierdos de los nodos del árbol izquierdo y los hijos derechos de los nodos del árbol derecho permanecen sin cambios. El algoritmo es paralelizable ya que en cada nivel de recursión, cada uno de los dos subproblemas se puede calcular en paralelo, y la operación de fusión también se puede paralelizar de manera eficiente . [5]
Es posible mantener el árbol cartesiano de una entrada dinámica, sujeto a inserciones de elementos y borrado diferido de elementos, en tiempo amortizado logarítmico por operación. Aquí, borrado diferido significa que se realiza una operación de borrado marcando un elemento en el árbol como elemento eliminado, pero sin eliminarlo realmente del árbol. Cuando el número de elementos marcados alcanza una fracción constante del tamaño de todo el árbol, se reconstruye, manteniendo solo sus elementos no marcados. [6]
Los árboles cartesianos forman parte de una estructura de datos eficiente para consultas de rango mínimo . Una entrada a este tipo de consulta especifica una subsecuencia contigua de la secuencia original; la salida de la consulta debe ser el valor mínimo en esta subsecuencia. [7] En un árbol cartesiano, este valor mínimo se puede encontrar en el ancestro común más bajo de los valores más a la izquierda y más a la derecha en la subsecuencia. Por ejemplo, en la subsecuencia (12,10,20,15,18) de la secuencia de ejemplo, el valor mínimo de la subsecuencia (10) forma el ancestro común más bajo de los valores más a la izquierda y más a la derecha (12 y 18). Debido a que los ancestros comunes más bajos se pueden encontrar en tiempo constante por consulta, utilizando una estructura de datos que ocupa un espacio lineal para almacenarse y se puede construir en tiempo lineal, los mismos límites se mantienen para el problema de minimización de rango. [8]
Bender y Farach-Colton (2000) invirtieron esta relación entre los dos problemas de estructura de datos al demostrar que las estructuras de datos para la minimización de rangos también se pueden utilizar para encontrar el ancestro común más bajo. Su estructura de datos asocia con cada nodo del árbol su distancia desde la raíz y construye una secuencia de estas distancias en el orden de un recorrido de Euler del árbol (con aristas duplicadas). Luego construye una estructura de datos de minimización de rangos para la secuencia resultante. El ancestro común más bajo de dos vértices cualesquiera en el árbol dado se puede encontrar como la distancia mínima que aparece en el intervalo entre las posiciones iniciales de estos dos vértices en la secuencia. Bender y Farach-Colton también proporcionan un método para la minimización de rangos que se puede utilizar para las secuencias resultantes de esta transformación, que tienen la propiedad especial de que los valores de secuencia adyacentes difieren en uno. Como describen, para la minimización de rango en secuencias que no tienen esta forma, es posible utilizar árboles cartesianos para reducir el problema de minimización de rango a los ancestros comunes más bajos, y luego utilizar recorridos de Euler para reducir los ancestros comunes más bajos a un problema de minimización de rango con esta forma especial. [9]
El mismo problema de minimización de rango también puede recibir una interpretación alternativa en términos de búsqueda de rango bidimensional. Una colección de un número finito de puntos en el plano cartesiano se puede utilizar para formar un árbol cartesiano, ordenando los puntos por sus coordenadas y utilizando las coordenadas en este orden como la secuencia de valores a partir de la cual se forma este árbol. Si es el subconjunto de los puntos de entrada dentro de alguna losa vertical definida por las desigualdades , es el punto más a la izquierda en (el que tiene la coordenada mínima), y es el punto más a la derecha en (el que tiene la coordenada máxima), entonces el ancestro común más bajo de y en el árbol cartesiano es el punto más bajo en la losa. Una consulta de rango de tres lados, en la que la tarea es enumerar todos los puntos dentro de una región delimitada por las tres desigualdades y , se puede responder encontrando este punto más bajo , comparando su coordenada con , y (si el punto se encuentra dentro de la región de tres lados) continuando recursivamente en las dos losas delimitadas entre y y entre y . De esta manera, después de que se identifican los puntos más a la izquierda y más a la derecha en la losa, todos los puntos dentro de la región de tres lados se pueden enumerar en tiempo constante por punto. [3]
La misma construcción, de ancestros comunes más bajos en un árbol cartesiano, permite construir una estructura de datos con espacio lineal que permite consultar las distancias entre pares de puntos en cualquier espacio ultramétrico en tiempo constante por consulta. La distancia dentro de un ultramétrico es la misma que el peso de la ruta minimax en el árbol de expansión mínima de la métrica. [10] A partir del árbol de expansión mínima, se puede construir un árbol cartesiano, cuyo nodo raíz representa la arista más pesada del árbol de expansión mínima. Al eliminar esta arista, se divide el árbol de expansión mínima en dos subárboles, y los árboles cartesianos construidos recursivamente para estos dos subárboles forman los hijos del nodo raíz del árbol cartesiano. Las hojas del árbol cartesiano representan puntos del espacio métrico, y el ancestro común más bajo de dos hojas en el árbol cartesiano es la arista más pesada entre esos dos puntos en el árbol de expansión mínima, que tiene un peso igual a la distancia entre los dos puntos. Una vez que se ha encontrado el árbol de expansión mínimo y se han ordenado los pesos de sus bordes, se puede construir el árbol cartesiano en tiempo lineal. [11]
El árbol cartesiano de una secuencia ordenada es simplemente un gráfico de ruta , con raíz en su extremo más a la izquierda. La búsqueda binaria en este árbol degenera en una búsqueda secuencial en la ruta. Sin embargo, una construcción diferente utiliza árboles cartesianos para generar árboles de búsqueda binaria de profundidad logarítmica a partir de secuencias ordenadas de valores. Esto se puede hacer generando números de prioridad para cada valor y utilizando la secuencia de prioridades para generar un árbol cartesiano. Esta construcción se puede ver de manera equivalente en el marco geométrico descrito anteriormente, en el que las coordenadas de un conjunto de puntos son los valores en una secuencia ordenada y las coordenadas son sus prioridades. [12]
Esta idea fue aplicada por Seidel y Aragon (1996), quienes sugirieron el uso de números aleatorios como prioridades. El árbol binario de búsqueda autoequilibrado resultante de esta elección aleatoria se llama treap , debido a su combinación de características de árbol binario de búsqueda y min-heap. Una inserción en un treap se puede realizar insertando la nueva clave como una hoja de un árbol existente, eligiendo una prioridad para ella y luego realizando operaciones de rotación de árbol a lo largo de una ruta desde el nodo hasta la raíz del árbol para reparar cualquier violación de la propiedad del heap causada por esta inserción; una eliminación se puede realizar de manera similar mediante una cantidad constante de cambio en el árbol seguido de una secuencia de rotaciones a lo largo de una única ruta en el árbol. [12] Una variación de esta estructura de datos llamada árbol zip utiliza la misma idea de prioridades aleatorias, pero simplifica la generación aleatoria de las prioridades y realiza inserciones y eliminaciones de una manera diferente, dividiendo la secuencia y su árbol cartesiano asociado en dos subsecuencias y dos árboles y luego recombinándolos. [13]
Si las prioridades de cada clave se eligen aleatoriamente e independientemente una vez cada vez que se inserta la clave en el árbol, el árbol cartesiano resultante tendrá las mismas propiedades que un árbol binario de búsqueda aleatorio , un árbol calculado insertando las claves en una permutación elegida aleatoriamente a partir de un árbol vacío, en el que cada inserción deja sin cambios la estructura del árbol anterior e inserta el nuevo nodo como una hoja del árbol. Los árboles binarios de búsqueda aleatorios se han estudiado durante mucho más tiempo que los treaps, y se sabe que se comportan bien como árboles de búsqueda. La longitud esperada de la ruta de búsqueda para cualquier valor dado es como máximo , y todo el árbol tiene una profundidad logarítmica (su distancia máxima de raíz a hoja) con alta probabilidad . Más formalmente, existe una constante tal que la profundidad es con una probabilidad que tiende a uno a medida que el número de nodos tiende a infinito. El mismo buen comportamiento se traslada a los treaps. También es posible, como lo sugieren Aragon y Seidel, repriorizar los nodos a los que se accede con frecuencia, haciendo que se muevan hacia la raíz del tronco y acelerando los accesos futuros para las mismas claves. [12]
Levcopoulos y Petersson (1989) describen un algoritmo de ordenamiento basado en árboles cartesianos. Describen el algoritmo como basado en un árbol con el máximo en la raíz [14], pero se puede modificar directamente para admitir un árbol cartesiano con la convención de que el valor mínimo se encuentra en la raíz. Para mantener la coherencia, es esta versión modificada del algoritmo la que se describe a continuación.
El algoritmo de Levcopoulos-Petersson puede considerarse como una versión del ordenamiento por selección o del ordenamiento por montículo que mantiene una cola de prioridad de mínimos candidatos y que en cada paso encuentra y elimina el valor mínimo de esta cola, moviendo este valor al final de una secuencia de salida. En su algoritmo, la cola de prioridad consta únicamente de elementos cuyo padre en el árbol cartesiano ya se ha encontrado y eliminado. Por lo tanto, el algoritmo consta de los siguientes pasos: [14]
Como muestran Levcopoulos y Petersson, para las secuencias de entrada que ya están casi ordenadas, el tamaño de la cola de prioridad seguirá siendo pequeño, lo que permite que este método aproveche la entrada casi ordenada y se ejecute más rápidamente. Específicamente, el tiempo de ejecución en el peor de los casos de este algoritmo es , donde es la longitud de la secuencia y es el promedio, sobre todos los valores de la secuencia, del número de pares consecutivos de valores de secuencia que encierran el valor dado (lo que significa que el valor dado está entre los dos valores de la secuencia). También prueban un límite inferior que establece que, para cualquier y (no constante) , cualquier algoritmo de ordenamiento basado en comparación debe usar comparaciones para algunas entradas. [14]
El problema de la comparación de árboles cartesianos se ha definido como una forma generalizada de comparación de cadenas en la que se busca una subcadena (o en algunos casos, una subsecuencia ) de una cadena dada que tenga un árbol cartesiano de la misma forma que un patrón dado. Se han desarrollado algoritmos rápidos para variaciones del problema con un patrón único o múltiples patrones, así como estructuras de datos análogas al árbol de sufijos y otras estructuras de indexación de texto. [15]
{{citation}}: CS1 maint: DOI inactivo a partir de noviembre de 2024 ( enlace )