Árbol cartesiano

En Ciencias de la Computación, un árbol cartesiano es un árbol binario que se deriva de una sucesión de números; se define únicamente a partir de que cumple con una ordenación a modo de montículo y de que un recorrido entre-orden del árbol retorna la secuencia original de números. Introducido por Vuillemin (1980) en el contexto de las estructuras de datos de búsqueda en rangos geométricos, los árboles cartesianos también han sido utilizados en la definición del treap y árboles aleatorios binarios de búsqueda para problemas de búsqueda binaria. El árbol cartesiano de una secuencia puede ser construido en tiempo lineal usando un algoritmo de pila para encontrar todos los menores valores más cercanos en una secuencia.

Una secuencia de números y el árbol cartesiano derivado de ellos.

Definición

Para una secuencia de números distintos, el árbol cartesiano se puede definir únicamente a partir de las siguientes propiedades:

1. Para una secuencia, el árbol cartesiano contiene un nodo para cada número de la secuencia. Cada nodo está asociado con un único número de la secuencia.
2. Un recorrido entre-orden del árbol resulta en la secuencia original. Esto significa que el subárbol izquierdo consiste de valores antecesores de la raíz en la secuencia, mientras que el subárbol derecho consiste de valores sucesores de la raíz en la secuencia. Estas restricciones se aplican para el resto de los nodos del árbol.
3. El árbol cumple con la propiedad del montículo: el padre de cualquier nodo, excepto la raíz, contiene un valor menor que el valor del nodo.^[1]​

Basado en la propiedad del montículo, la raíz del árbol tiene que ser el menor número de la secuencia. A partir de esto, el árbol también se puede definir de forma recursiva: la raíz es el menor valor de la secuencia, y los subárboles izquierdo y derecho son árboles cartesianos para las subsecuencias a la izquierda y a la derecha del valor de la raíz en la secuencia.

Si una secuencia contiene números repetidos, el árbol cartesiano se puede definir determinando una regla de desempate (por ejemplo, determinando que el primer número repetido sea tratado como menor que su homólogo en la secuencia) antes de aplicar las propiedades anteriores.

Búsqueda en rango y menores ancestros comunes

Los árboles cartesianos se pueden usar como parte de una estructura de datos eficiente para consultas de rango mínimo, un problema de búsqueda en rango relacionado con consultas que buscan el menor valor de una subsecuencia contigua de la secuencia original.^[2]​ En un árbol cartesiano, dicho menor valor se puede encontrar en el menor ancestro común 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) de la secuencia mostrada en la primera figura, el menor valor es (10) forma el menor ancestro común de los valores más a la izquierda y más a la derecha (12 y 15). Debido a que los menores ancestros comunes se pueden encontrar en un tiempo constante para cada consulta, usar una estructura de datos que utiliza un espacio lineal para almacenamiento y que se construye en tiempo lineal,^[3]​ implica obtener dichos tiempos para el problema de minimización en rangos.

Bender y Farach-Colton (2000) invirtieron esta relación entre las dos estructuras de datos demostrando que los menores ancestros comunes en un árbol de entrada se podían encontrar eficientemente aplicando una técnica de minimización en rangos que no se basa en árboles. Su estructura de datos usa una técnica del circuito euleriano para transformar el árbol de entrada en una secuencia. La secuencia resultante de esta transformación tiene una forma especial (números adyacentes, representantes de las alturas de nodos adyacentes en el árbol, difieren en ±1) de la cual ellos se aprovechan en su estructura de datos; para resolver problemas de minimización en rango en secuencias que tienen esta forma especial, ellos utilizan un árbol cartesiano para transformar el problema de minimización en rango en un problema de menor ancestro común y entonces aplican la técnica del circuito euleriano para transformar el problema nuevamente a un problema de minimización de rango con esta forma especial.

El mismo problema de minimización también se puede interpretar de forma alternativa, en términos de búsqueda bidimensional en rango. Una colección finita de puntos en el plano cartesiano se puede utilizar para formar un árbol cartesiano, ordenando los puntos por su coordenada x y utilizando la coordenada y (en ese orden) para construir la secuencia de la cual se construye el árbol. Si S es el subconjunto de los puntos de entrada contenidos en una región definida por las desigualdades L ≤ x ≤ R, p es el punto más a la izquierda en S (cuya coordenada x es la menor) y q el punto más a la derecha en S (cuya coordenada x es la mayor) entonces el menor ancestro común de p y q en el árbol cartesiano es el punto más inferior en la región. Una consulta de rango delimitada por tres lados, en la cual el objetivo es listar todos los puntos contenidos en una región delimitada por tres desigualdades L ≤ x ≤ R and y ≤ T, se puede responder encontrando el punto más inferior b, comparando su coordenada y con T, y (si el punto se encuentra dentro de la región delimitada por los tres lados) continuando recursivamente en las regiones que se encuentran entre p y b y entre b y q. De esta forma, después de que los puntos más a la izquierda y más a la derecha en la región han sido encontrados, todos los puntos en la región delimitada por los tres lados se pueden listar en un tiempo constante para cada punto^[4]​

Esta misma construcción, de menores ancestros comunes en un árbol cartesiano, hace posible construir una estructura de datos con espacio lineal que permite que las distancias entre pares de puntos en cualquier espacio ultra métrico sean consultadas en un tiempo constante para cada consulta. La distancia dentro de una ultra métrica es lo mismo que el peso de un camino minimax en el árbol abarcador de costo mínimo de la métrica.^[5]​ A partir del árbol abarcador de costo mínimo, se puede construir un árbol cartesiano, del cual el nodo raíz representa la arista más de mayor costo del árbol abarcador de costo mínimo. Quitar esta arista particiona el árbol abarcador de costo mínimo en dos subárboles y los árboles cartesianos construidos recursivamente para los dos subárboles forman los hijos del nodo raíz del árbol cartesiano. Las hojas del árbol cartesiano representan puntos en el espacio métrico, y el menor ancestro común de dos hojas es la arista más de mayor costo entre esos dos puntos en el árbol abarcador de costo mínimo, que tiene un costo igual a la distancia entre esos dos puntos. Una vez que el árbol abarcador de costo mínimo ha sido encontrado y los costos de sus aristas ordenados, el árbol cartesiano puede ser construido en tiempo lineal.^[6]​

Treaps

Debido a que un árbol cartesiano es un árbol binario, resulta natural utilizarlo como un árbol binario de búsqueda para una secuencia ordenada de valores. No obstante, definir un árbol cartesiano basado en los mismos valores que forman las llaves de un árbol binario de búsqueda puede no funcionar bien: el árbol cartesiano de una secuencia ordenada no es más que una rama, comenzando en el punto más a la izquierda y una búsqueda binaria en dicho árbol se degenera a una búsqueda secuencial en la rama. Sin embargo, es posible construir árboles de búsqueda más balanceados generando valores de prioridad para cada llave que son distintos de la llave, ordenando la entrada por el valor de las llaves y usando la secuencia correspondiente de prioridades para generar el árbol cartesiano. Esto construcción puede ser vista de forma equivalente en el esquema geométrico descrito anteriormente, tomando las coordenadas x de un conjunto de puntos son las llaves de búsqueda y las coordenadas y son las prioridades.

Esta idea fue aplicada por Seidel y Aragon (1996), quienes sugirieron el uso de números aleatorios como prioridades. La estructura de datos resultante de esta selección aleatorio es denominada treap , debido a la combinación de las características del árbol binario de búsqueda (en inglés binary search tree) y el montículo binario (en inglés binary heap). Una inserción en un treap se realiza insertando la nueva llave como una hoja de un árbol existente, eligiendo una prioridad para dicha hoja y realizando operaciones de rotación en el camino desde la hoja hasta la raíz para reparar cualquier violación de la propiedad del montículo causadas por la inserción del nuevo nodo; la eliminación se realiza de forma similar, con una número constante de cambios en el árbol seguidos por una secuencia de rotaciones sobre un único camino en el árbol.

Si las prioridades de cada llave se eligen de forma aleatoria e independiente cuando la llave se inserta en el árbol, entonces el árbol cartesiano resultante tendrá las mismas propiedades que un árbol aleatorio binario de búsqueda, que no es más que un árbol binario computado mediante la inserción de llaves en una permutación escogida aleatoriamente. Dicho árbol comienza con un árbol vacío, y con cada inserción se deja la estructura del árbol anterior intacta y se inserta el nuevo nodo como una hoja del árbol. Los árboles aleatorios binarios de búsqueda han sido estudiados por mucho tiempo, y se conoce que presentan un buen comportamiento como árboles de búsqueda (tiene profundidad logarítmica con una alta probabilidad); el mismo buen comportamiento se lleva a los treaps. También es posible, como sugieren Aragon y Seidel, re-priorizar nodos accedidos frecuentemente, causando que se muevan hacia la raíz y acelerando futuros accesos con las mismas llaves.

Construcción eficiente

Un árbol cartesiano puede ser construido en tiempo lineal a partir de la secuencia de entrada. Un método es procesar los valores de izquierda a derecha, manteniendo el árbol cartesiano de los nodos procesados hasta el momento en una estructura que permite los recorridos hacia abajo y hacia arriba del árbol. Para procesar cada valor nuevo x, se comienza en el nodo que representa el valor anterior a x en la secuencia y se continua en el camino desde este nodo hasta la raíz hasta encontrar un valor y que sea menor que x. Este nodo y es el padre de x, y el antiguo hijo derecho de y pasa a ser el nuevo hijo izquierdo de x. El tiempo total para este procedimiento es lineal, ya que el tiempo que se emplea buscando por el padre y de cada nodo x se puede sobrecargar contra el número de nodos que se eliminan del camino en la extrema derecha del árbol.^[4]​

Una construcción alternativa de tiempo lineal se basa en el problema de los todos los valores cercanos más pequeños. En la secuencia de entrada, se puede definir el vecino izquierdo de un valor x como el valor que ocurre anterior a x, que es menor que x y cuya posición es la más cercana a x que cualquier otro valor menor que x. El vecino derecho se define de forma simétrica. La secuencia de los vecinos izquierdos de x se puede encontrar mediante un algoritmo que mantiene una pila que contiene una subsecuencia de la entrada. Para cada valor nuevo x de la secuencia, la pila se va reduciendo mediante la operación de desapilar (pop en inglés) hasta que la pila esté vacía o el elemento en la cima de la pila sea menor que x, y luego se apila dicho elemento. El vecino izquierdo de x es el elemento que estaba en el la cima de la pila en el momento en que se insertó x. El vecino derecho se puede encontrar aplicando el mismo algoritmo de pila a la secuencia inversa. El padre de x en el árbol cartesiano es el vecino izquierdo o el vecino derecho de x. Los vecinos izquierdo y derecho de x también pueden ser encontrados eficientemente mediante algoritmos paralelos, por lo que esta formulación puede ser utilizada para desarrollar algoritmos paralelos eficientes para la construcción de árboles Cart^[7]​

Aplicación en la ordenación.

Levcopoulos y Petersson (1989) describen un algoritmo de ordenación basado en árboles cartesianos. Ellos describen el algoritmo como basado en un árbol cuyo máximo está en la raíz, pero puede ser modificado para soportar árboles cartesianos con la convención de que el menor valor está en la raíz. Por consistencia, el algoritmo descrito a continuación incluye dicha modificación.

El algoritmo Levcopoulos–Petersson puede ser visto como una versión del ordenamiento por selección o el ordenamiento por montículos que mantiene una cola con prioridad de los candidatos a mínimo, y que en cada paso encuentra y elimina el mínimo de dicha cola, llevándolo al final de la secuencia de salida. En su algoritmo, la cola con prioridad consiste solo de elementos cuyos padres en el árbol cartesiano han sido encontrados y eliminados. El algoritmo consiste de los siguientes pasos:

1. Construir el árbol cartesiano a partir de la secuencia de entrada.
2. Inicializar la cola con prioridad, que contiene inicialmente la raíz del árbol.
3. Mientras que la cola no esté vacía:
   • Encontrar y eliminar el mínimo valor x de la cola.
   • Agregar x a la secuencia de salida.
   • Agregar los hijos de x en el árbol cartesiano a la cola con prioridad.

Como Levcopoulos and Petersson demuestran, para secuencias de entradas que estén casi ordenadas, el tamaño de la cola con prioridad se mantendrá pequeño, permitiendo a este método aprovechar el hecho de que la secuencia de entrada está casi ordenada y ejecutarse de manera más rápida. En específico, el peor tiempo de ejecución para este algoritmo es O(n log k), donde k es el promedio, para todos los valores x de la secuencia, del número de pares consecutivos de valores de la secuencia que encierran a x. Ellos también demuestran una cota inferior enunciando que, para cualquier n y k = ω(1), cualquier algoritmo de ordenación basado en comparaciones debe utilizar Ω(n log k) comparaciones para algunas entradas.

Historia

Los árboles cartesianos fueron introducidos y nombrados por Vuillemin (1980). El nombre se deriva del sistema de coordenadas cartesianas para el plano: en la versión de Vuillemin (1980) de esta estructura, un árbol cartesiano para un conjunto de puntos contiene la ordenación de los puntos por sus coordenadas x en el recorrido en orden simétrico y contiene la propiedad del montículo de acuerdo a las coordenadas y de los puntos. Gabow, Bentley y Tarjan (1984) y los autores subsecuentes seguidos en la definición mostrada aquí, en la cual el árbol cartesiano se define a partir de una secuencia. Este cambio generaliza el enfoque geométrico de Vuillemin para permitir otras secuencias además de las coordenadas x ordenadas, y permite también al árbol cartesiano ser aplicado a problemas no geométricos.

Notes

1. En algunas referencias, la ordenación es inversa, por lo que el padre de cualquier nodo siempre tiene un valor mayor, y la raíz contiene el máximo.
2. Gabow, Bentley y Tarjan (1984); Bender y Farach-Colton (2000).
3. Harel y Tarjan (1984); Schieber y Vishkin (1988).
4. Gabow, Bentley y Tarjan (1984).
5. Hu (1961); Leclerc (1981)
6. Demaine, Landau y Weimann (2009).
7. Berkman, Schieber y Vishkin (1993).

Referencias

• Bender, Michael A.; Farach-Colton, Martin (2000), «The LCA problem revisited», Proceedings of the 4th Latin American Symposium on Theoretical Informatics, Springer-Verlag, Lecture Notes in Computer Science 1776, pp. 88-94 ..
• Berkman, Omer; Schieber, Baruch; Vishkin, Uzi (1993), «Optimal doubly logarithmic parallel algorithms based on finding all nearest smaller values», Journal of Algorithms 14 (3): 344-370, doi:10.1006/jagm.1993.101 ..
• Demaine, Erik D.; Landau, Gad M.; Weimann, Oren (2009), «On cartesian trees and range minimum queries», Automata, Languages and Programming, 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Lecture Notes in Computer Science 5555, pp. 341-353, ISBN 978-3-642-02926-4, doi:10.1007/978-3-642-02927-1_29 ..
• Fischer, Johannes; Heun, Volker (2006), «Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE», Proceedings of the 17th Annual Symposium on Combinatorial Pattern Matching, Lecture Notes in Computer Science 4009, Springer-Verlag, pp. 36-48, ISBN 978-3-540-35455-0, doi:10.1007/11780441_5 .
• Fischer, Johannes; Heun, Volker (2007), «A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array.», Proceedings of the International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, Lecture Notes in Computer Science 4614, Springer-Verlag, pp. 459-470, ISBN 978-3-540-74449-8, doi:10.1007/978-3-540-74450-4_41 .
• Gabow, Harold N.; Bentley, Jon Louis; Tarjan, Robert E. (1984), «Scaling and related techniques for geometry problems», STOC '84: Proc. 16th ACM Symp. Theory of Computing, New York, NY, USA: ACM, pp. 135-143, ISBN 0-89791-133-4, doi:10.1145/800057.808675 ..
• Harel, Dov; Tarjan, Robert E. (1984), «Fast algorithms for finding nearest common ancestors», SIAM Journal on Computing 13 (2): 338-355, doi:10.1137/0213024 ..
• Hu, T. C. (1961), «The maximum capacity route problem», Operations Research 9 (6): 898-900, JSTOR 167055, doi:10.1287/opre.9.6.898 ..
• Leclerc, Bruno (1981), «Description combinatoire des ultramétriques», Centre de Mathématique Sociale. École Pratique des Hautes Études. Mathématiques et Sciences Humaines (en francés) (73): 5-37, 127, MR 623034 ..
• Levcopoulos, Christos; Petersson, Ola (1989), «Heapsort - Adapted for Presorted Files», WADS '89: Proceedings of the Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science 382, London, UK: Springer-Verlag, pp. 499-509, doi:10.1007/3-540-51542-9_41 ..
• Seidel, Raimund; Aragon, Cecilia R. (1996), «Randomized Search Trees», Algorithmica 16 (4/5): 464-497, doi:10.1007/s004539900061 ..
• Schieber, Baruch; Vishkin, Uzi (1988), «On finding lowest common ancestors: simplification and parallelization», SIAM Journal on Computing 17 (6): 1253-1262, doi:10.1137/0217079 ..
• Vuillemin, Jean (1980), «A unifying look at data structures», Commun. ACM (New York, NY, USA: ACM) 23 (4): 229-239, doi:10.1145/358841.358852 ..

•   Datos: Q5047286