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 en 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 únicamente como un montón mínimo cuyo recorrido simétrico (en orden) devuelve la secuencia original.
Los árboles cartesianos fueron introducidos por Vuillemin (1980) en el contexto de estructuras de datos de búsqueda de rango geométrico . También se han utilizado en la definición de treap y estructuras de datos de árbol de búsqueda binaria aleatoria para problemas de búsqueda binaria , en algoritmos de clasificación de comparación que funcionan de manera eficiente en entradas casi ordenadas y como base para algoritmos de coincidencia de patrones . Se puede construir un árbol cartesiano para una secuencia en tiempo lineal .
Los árboles cartesianos se definen mediante árboles binarios , que son una forma de árbol enraizado . 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 recursivamente, utilizando sus propiedades de ordenamiento. En cualquier árbol, el subárbol enraizado en cualquier nodo consta de 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 por las siguientes propiedades:
Estas dos definiciones son equivalentes: el árbol definido recursivamente como se describe anteriormente es el árbol único que tiene las propiedades enumeradas anteriormente. Si una secuencia de números contiene repeticiones, se puede determinar un árbol cartesiano 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 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 promedio de las operaciones de concatenación y división en árboles de búsqueda binarios . El nombre se deriva del sistema de coordenadas cartesiano para el plano: en una versión de esta estructura, como en la aplicación de búsqueda de rango bidimensional que se analiza a continuación, un árbol cartesiano para un conjunto de puntos tiene el orden de los puntos según sus coordenadas. como su orden transversal simétrico, y tiene la propiedad de montón según 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 aplicar el árbol cartesiano también a problemas no geométricos. [2]
Se puede construir un árbol cartesiano en tiempo lineal a partir de su secuencia de entrada. Un método consiste en procesar los valores de la secuencia en orden de izquierda a derecha, manteniendo el árbol cartesiano de los nodos procesados hasta el momento, en una estructura que permita el recorrido del árbol tanto hacia arriba como hacia abajo. 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 de este procedimiento es lineal, porque el tiempo dedicado a buscar el padre de cada nodo nuevo se puede imputar al número de nodos que se eliminan de la ruta más a la derecha del árbol. [3]
Un algoritmo alternativo de construcción en tiempo lineal 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 de su 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 abre hasta que está vacía o su elemento superior es más pequeño que y luego se empuja a la pila. El vecino izquierdo de es el elemento superior en el momento en que se empuja. Los vecinos correctos 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 o 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 el camino obtenido siguiendo los bordes secundarios izquierdos desde la raíz hasta llegar a un nodo sin hijo izquierdo, y la espina derecha se define simétricamente. Al igual que con cualquier ruta en un montón mínimo, ambas espinas tienen sus valores en orden, 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 columna derecha del árbol izquierdo y a la columna 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 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 usó anteriormente para su sucesor en la columna. 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 recursividad, 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 eliminación diferida de elementos, en tiempo amortizado logarítmico por operación. Aquí, la eliminación diferida significa que se realiza una operación de eliminación 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 sólo los elementos no marcados. [6]
Los árboles cartesianos forman parte de una estructura de datos eficiente para consultas de rango mínimo . Una entrada para este tipo de consulta especifica una subsecuencia contigua de la secuencia original; el resultado 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 de 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 espacio lineal para almacenar y se puede construir en tiempo lineal, los mismos límites se aplican al 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 mostrar que las estructuras de datos para la minimización del rango también podrían usarse para encontrar ancestros comunes más bajos. 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 rango 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 puede usarse para las secuencias resultantes de esta transformación, que tienen la propiedad especial de que los valores de secuencias adyacentes difieren en uno. Como describen, para la minimización de rango en secuencias que no tienen esta forma, es posible usar árboles cartesianos para reducir el problema de minimización de rango a los ancestros comunes más bajos, y luego usar recorridos de Euler para reducir los ancestros comunes más bajos a un problema de minimización de rango. con esta forma especial. [9]
Al mismo problema de minimización de rango también se le puede dar una interpretación alternativa en términos de búsqueda de rango bidimensional. Se puede utilizar una colección de un número finito de puntos en el plano cartesiano para formar un árbol cartesiano, clasificando los puntos por sus coordenadas y usando 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 (el que tiene la coordenada mínima) y es el punto más a la derecha (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 de 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 los tres región de lados) que continúa recursivamente en las dos losas delimitadas entre y y entre y . De esta manera, después de identificar los puntos más a la izquierda y más a la derecha de 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 una ultramétrica es la misma que el peso de ruta minimax en el árbol de expansión mínimo 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 el borde más pesado del árbol de expansión mínima. La eliminación de este borde 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 el borde más pesado 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, el árbol cartesiano se puede construir en tiempo lineal. [11]
El árbol cartesiano de una secuencia ordenada es simplemente un gráfico de ruta , con raíz en su punto final más a la izquierda. La búsqueda binaria en este árbol degenera en búsqueda secuencial en la ruta. Sin embargo, una construcción diferente utiliza árboles cartesianos para generar árboles de búsqueda binarios de profundidad logarítmica a partir de secuencias ordenadas de valores. Esto se puede hacer generando números de prioridad para cada valor y usando la secuencia de prioridades para generar un árbol cartesiano. Esta construcción puede verse 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 Aragón (1996), quienes sugirieron el uso de números aleatorios como prioridades. El árbol de búsqueda binario autoequilibrado resultante de esta elección aleatoria se llama treap , debido a su combinación de árbol de búsqueda binario y características de montón mínimo. Se puede realizar una inserción en un treap insertando la nueva clave como una hoja de un árbol existente, eligiendo una prioridad para ella y luego realizando operaciones de rotación del á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 montón causada por esta inserción; De manera similar, una eliminación se puede realizar mediante una cantidad constante de cambios 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 recombinarlos. [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 de búsqueda binaria aleatoria , un árbol que se calcula insertando las claves en una permutación elegida aleatoriamente comenzando de un árbol vacío, y cada inserción deja la estructura del árbol anterior sin cambios e inserta el nuevo nodo como una hoja del árbol. Los árboles de búsqueda binaria aleatoria 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 tiene una probabilidad que tiende a uno cuando el número de nodos tiende a infinito. El mismo buen comportamiento se aplica a las trampas. También es posible, como sugieren Aragon y Seidel, volver a priorizar los nodos a los que se accede con frecuencia, haciendo que se muevan hacia la raíz del problema y acelerando los accesos futuros para las mismas claves. [12]
Levcopoulos y Petersson (1989) describen un algoritmo de clasificación 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 está 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 verse como una versión de clasificación por selección o clasificación de montón que mantiene una cola de prioridad de mínimos candidatos y que en cada paso encuentra y elimina el valor mínimo en esta cola, moviendo este valor al final de una salida. secuencia. En su algoritmo, la cola de prioridad consta únicamente de elementos cuyo padre en el árbol cartesiano ya ha sido encontrado y eliminado. Así, el algoritmo consta de los siguientes pasos: [14]
Como muestran Levcopoulos y Petersson, para secuencias de entrada que ya están casi ordenadas, el tamaño de la cola de prioridad seguirá siendo pequeño, lo que permitirá 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 abarcan el valor dado (lo que significa que el valor dado está entre los dos valores de secuencia). También demuestran un límite inferior que indica que, para any y (no constante) , cualquier algoritmo de clasificación basado en comparaciones debe utilizar comparaciones para algunas entradas. [14]
El problema de la coincidencia de árboles cartesianos se ha definido como una forma generalizada de coincidencia de cadenas en la que se busca una subcadena (o en algunos casos, una subsecuencia ) de una cadena determinada que tenga un árbol cartesiano de la misma forma que un patrón determinado. Se han desarrollado algoritmos rápidos para variaciones del problema con un solo patrón o múltiples patrones, así como estructuras de datos análogas al árbol de sufijos y otras estructuras de indexación de texto. [15]
