En informática , un árbol cartesiano es un árbol binario derivado de una secuencia de números; se puede definir de forma única a partir de las propiedades de que está ordenado en montón y que un recorrido simétrico (en orden) del árbol devuelve la secuencia original. Introducido por Vuillemin (1980) en el contexto de las estructuras de datos de búsqueda de rango geométrico , los árboles cartesianos también se han utilizado en la definición de las estructuras de datos de árbol de búsqueda binaria treap y aleatoria para problemas de búsqueda binaria . El árbol cartesiano de una secuencia se puede construir en tiempo linealusando un algoritmo basado en pila para encontrar todos los valores más pequeños más cercanos en una secuencia.
Definición
El árbol cartesiano para una secuencia de números distintos se puede definir de forma única mediante las siguientes propiedades:
- El árbol cartesiano de una secuencia tiene un nodo para cada número de la secuencia. Cada nodo está asociado con un único valor de secuencia.
- Un recorrido simétrico (en orden) del árbol da como resultado la secuencia original. Es decir, el subárbol izquierdo consta de los valores anteriores a la raíz en el orden de secuencia, mientras que el subárbol derecho consta de los valores posteriores a la raíz, y una restricción de orden similar se mantiene en cada nodo inferior del árbol.
- El árbol tiene la propiedad del montón : el padre de cualquier nodo no raíz tiene un valor menor que el nodo en sí. [1]
Según la propiedad del montón, la raíz del árbol debe ser el número más pequeño de la secuencia. A partir de esto, el árbol en sí también se puede definir de forma recursiva: la raíz es el valor mínimo de la secuencia, y los subárboles izquierdo y derecho son los árboles cartesianos para las subsecuencias a la izquierda y derecha del valor de la raíz. Por lo tanto, las tres propiedades anteriores definen de forma única el árbol cartesiano.
Si una secuencia de números contiene repeticiones, el árbol cartesiano se puede definir determinando una regla de desempate consistente (por ejemplo, determinando que el primero de dos elementos iguales se trata como el más pequeño de los dos) antes de aplicar las reglas anteriores.
En la figura anterior se muestra un ejemplo de árbol cartesiano.
Búsqueda de rango y antepasados comunes más bajos
Los árboles cartesianos pueden usarse como parte de una estructura de datos eficiente para consultas de rango mínimo , un problema de búsqueda de rango que involucra consultas que solicitan el valor mínimo en una subsecuencia contigua de la secuencia original. [2] 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) de la secuencia mostrada en la primera ilustración, 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 15). Debido a que los antepasados comunes más bajos se pueden encontrar en tiempo constante por consulta, utilizando una estructura de datos que requiere espacio lineal para almacenar y que puede construirse en tiempo lineal, [3] se mantienen los mismos límites para el problema de minimización de rango.
Bender y Farach-Colton (2000) invirtieron esta relación entre los dos problemas de estructura de datos al mostrar que los antepasados comunes más bajos en un árbol de entrada podrían resolverse de manera eficiente aplicando una técnica no basada en árboles para minimizar el rango. Su estructura de datos utiliza una técnica de recorrido de Euler para transformar el árbol de entrada en una secuencia y luego encuentra mínimos de rango en la secuencia resultante. La secuencia resultante de esta transformación tiene una forma especial (los números adyacentes, que representan las alturas de los nodos adyacentes en el árbol, difieren en ± 1) que aprovechan en su estructura de datos; Para resolver el problema de minimización de rango para secuencias que no tienen esta forma especial, usan árboles cartesianos para transformar el problema de minimización de rango en un problema de ancestro común más bajo, y luego aplican la técnica de recorrido de Euler para transformar el problema nuevamente en uno de minimización de rango. para secuencias con esta forma especial.
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. Se puede usar 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 x y usando las coordenadas y en este orden como la secuencia de valores a partir de la cual se forma este árbol. Si S es el subconjunto de los puntos de entrada dentro de alguna losa vertical definida por las desigualdades L ≤ x ≤ R , p es el punto más a la izquierda en S (el que tiene una coordenada x mínima), y q es el punto más a la derecha en S (el uno con la máxima x coordenada), entonces el ancestro común más bajo de p y q 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 L ≤ x ≤ R y y ≤ T , puede responderse encontrando este punto inferior b , comparando su coordenada y con T , y (si el punto se encuentra dentro de la región de tres lados) continúa recursivamente en las dos losas delimitadas entre p y b y entre b y q . 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. [4]
La misma construcción, de antepasados 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ínimo de la métrica. [5] A partir del árbol de expansión mínimo, se puede construir un árbol cartesiano, cuyo nodo raíz representa el borde más pesado del árbol de expansión mínimo. La eliminación de este borde divide el árbol de expansión mínimo 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 antepasado 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ínimo, 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 los bordes, el árbol cartesiano se puede construir en tiempo lineal. [6]
Treaps
Debido a que un árbol cartesiano es un árbol binario, es natural usarlo como un árbol de búsqueda binario para una secuencia ordenada de valores. Sin embargo, definir un árbol cartesiano basado en los mismos valores que forman las claves de búsqueda de un árbol de búsqueda binario no funciona bien: el árbol cartesiano de una secuencia ordenada es solo una ruta , arraigada en su punto final más a la izquierda, y búsqueda binaria en este árbol degenera en búsqueda secuencial en el camino. Sin embargo, es posible generar árboles de búsqueda más equilibrados generando valores de prioridad para cada clave de búsqueda que sean diferentes a la clave en sí, clasificando las entradas por sus valores clave y utilizando la secuencia de prioridades correspondiente 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 x de un conjunto de puntos son las claves de búsqueda y las coordenadas y son las prioridades.
Esta idea fue aplicada por Seidel & Aragon (1996) , quienes sugirieron el uso de números aleatorios como prioridades. La estructura de datos resultante de esta elección aleatoria se llama treap , debido a su combinación de árbol de búsqueda binaria y características de montón binario. 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 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 montón causada por esta inserción; una eliminación puede realizarse 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.
Si las prioridades de cada clave se eligen de forma aleatoria e independiente 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 calculado insertando las claves en una permutación elegida al azar comenzando de un árbol vacío, con cada inserción dejando la estructura del árbol anterior sin cambios e insertando el nuevo nodo como una hoja del árbol. Los árboles de búsqueda binaria aleatoria se han estudiado durante mucho más tiempo y se sabe que se comportan bien como árboles de búsqueda (tienen una profundidad logarítmica con alta probabilidad); el mismo buen comportamiento se traslada a los dulces. 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 treap y acelerando los accesos futuros para las mismas claves.
Construcción eficiente
Un árbol cartesiano se puede construir en tiempo lineal a partir de su secuencia de entrada. Un método consiste simplemente en 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 del árbol tanto hacia arriba como hacia abajo. Para procesar cada nuevo valor x , comience en el nodo que representa el valor anterior ax en la secuencia y siga la ruta desde este nodo hasta la raíz del árbol hasta encontrar un valor y menor que x . El nodo x se convierte en el hijo derecho de y , y el hijo derecho anterior de y se convierte en el nuevo hijo izquierdo de x . El tiempo total para este procedimiento es lineal, porque el tiempo dedicado a buscar el padre y de cada nuevo nodo x puede cargarse contra el número de nodos que se eliminan de la ruta más a la derecha del árbol. [4]
Un algoritmo alternativo de construcción de tiempo lineal se basa en el problema de valores más pequeños más cercano . En la secuencia de entrada, se puede definir el vecino izquierdo de un valor x como el valor que ocurre antes de x , es menor que x , y está más cerca en posición ax que cualquier otro valor menor. 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 x , la pila se abre hasta que está vacía o su elemento superior es más pequeño que x , y luego x se empuja a la pila. El vecino izquierdo de x es el elemento superior en el momento en que se empuja x . Los vecinos correctos se pueden encontrar aplicando el mismo algoritmo de pila al reverso de la secuencia. El padre de x en el árbol cartesiano es el vecino izquierdo de x o el vecino derecho de x , el que exista y tenga un valor mayor. Los vecinos izquierdo y derecho también se pueden construir de manera eficiente mediante algoritmos paralelos , por lo que esta formulación se puede utilizar para desarrollar algoritmos paralelos eficientes para la construcción de árboles cartesianos. [7]
Otro algoritmo de tiempo lineal para la construcción de árboles cartesianos se basa en divide y vencerás. En particular, el algoritmo construye recursivamente el árbol en cada mitad de la entrada y luego fusiona los dos árboles tomando la columna derecha del árbol izquierdo y la columna izquierda del árbol derecho (ambos son caminos cuya raíz a hoja order ordena sus valores de menor a mayor) y realiza una operación de fusión estándar , reemplazando estas dos rutas en dos árboles por una única ruta que contiene los mismos nodos. En la ruta combinada, el sucesor en el orden ordenado de cada nodo del árbol de la izquierda 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 vertebral. Los hijos de la izquierda de los nodos del árbol de la izquierda y los hijos de la derecha de los nodos del árbol de la derecha no se modifican. El algoritmo también se puede paralelizar 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 eficientemente . [8]
Aplicación en clasificación
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, pero puede modificarse directamente para admitir un árbol cartesiano con la convención de que el valor mínimo está en la raíz. En aras de la coherencia, es esta versión modificada del algoritmo la que se describe a continuación.
El algoritmo de Levcopoulos-Petersson se puede ver como una versión de clasificación de selección o clasificación de pila 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 solo de elementos cuyo padre en el árbol cartesiano ya se ha encontrado y eliminado. Por tanto, el algoritmo consta de los siguientes pasos:
- Construya un árbol cartesiano para la secuencia de entrada
- Inicializar una cola de prioridad, que inicialmente contiene solo la raíz del árbol
- Si bien la cola de prioridad no está vacía:
- Busque y elimine el valor mínimo x en la cola de prioridad
- Suma x a la secuencia de salida
- Agregue los elementos secundarios del árbol cartesiano de x a la cola de prioridad
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 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 O ( n log k ), donde k es el promedio, sobre todos los valores x en la secuencia, del número de pares consecutivos de valores de secuencia que incluyen x . También prueban un límite inferior que indica que, para cualquier n y k = ω (1), cualquier algoritmo de clasificación basado en comparación debe usar comparaciones Ω ( n log k ) para algunas entradas.
Historia
Los árboles cartesianos fueron introducidos y nombrados por Vuillemin (1980) . El nombre se deriva del sistema de coordenadas cartesiano para el plano: en la versión de Vuillemin de esta estructura, como en la aplicación de búsqueda de rango bidimensional discutida anteriormente, un árbol cartesiano para un conjunto de puntos tiene el orden de los puntos por su x - coordenadas como su orden transversal simétrico, y tiene la propiedad heap de acuerdo con las coordenadas y de los puntos. Gabow, Bentley y Tarjan (1984) y los autores posteriores siguieron la definición aquí en la que un árbol cartesiano se define a partir de una secuencia; este cambio generaliza la configuración geométrica de Vuillemin para permitir secuencias distintas del orden ordenado de las coordenadas x , y permite que el árbol cartesiano se aplique también a problemas no geométricos.
Notas
- ^ En algunas referencias, el orden se invierte, por lo que el padre de cualquier nodo siempre tiene un valor mayor y el nodo raíz tiene el valor máximo.
- ^ Gabow, Bentley y Tarjan (1984) ; Bender y Farach-Colton (2000) .
- ^ Harel y Tarjan (1984) ; Schieber y Vishkin (1988) .
- ↑ a b Gabow, Bentley y Tarjan (1984) .
- ^ Hu (1961) ; Leclerc (1981)
- ^ Demaine, Landau y Weimann (2009) .
- ^ Berkman, Schieber y Vishkin (1993) .
- ^ Shun y Blelloch (2014) .
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, págs. 88–94.
- Berkman, Omer; Schieber, Baruch; Vishkin, Uzi (1993), "Algoritmos paralelos doblemente logarítmicos óptimos basados en encontrar todos los valores más pequeños más cercanos", Journal of Algorithms , 14 (3): 344–370, doi : 10.1006 / jagm.1993.1018.
- Demaine, Erik D .; Landau, Gad M .; Weimann, Oren (2009), "Sobre árboles cartesianos y consultas de rango mínimo", Automata, Languages and Programming, 36th International Colloquium, ICALP 2009, Rodas, Grecia, 5 al 12 de julio de 2009 , Lecture Notes in Computer Science, 5555 , págs. . 341–353, doi : 10.1007 / 978-3-642-02927-1_29 , hdl : 1721.1 / 61963 , ISBN 978-3-642-02926-4.
- Fischer, Johannes; Heun, Volker (2006), "Mejoras teóricas y prácticas en el problema RMQ, con aplicaciones a LCA y LCE", Actas del 17º Simposio Anual sobre Emparejamiento Combinatorio de Patrones , Lecture Notes in Computer Science, 4009 , Springer-Verlag, págs. . 36–48, doi : 10.1007 / 11780441_5 , ISBN 978-3-540-35455-0
- Fischer, Johannes; Heun, Volker (2007), "Una nueva representación sucinta de información RMQ y mejoras en la matriz de sufijos mejorada", Actas del Simposio internacional sobre combinatoria, algoritmos, metodologías probabilísticas y experimentales , notas de la conferencia en informática, 4614 , Springer -Verlag, págs. 459–470, doi : 10.1007 / 978-3-540-74450-4_41 , ISBN 978-3-540-74449-8
- Gabow, Harold N .; Bentley, Jon Louis ; Tarjan, Robert E. (1984), "Escalado y técnicas relacionadas para problemas de geometría", STOC '84: Proc. 16 ° ACM Symp. Theory of Computing , Nueva York, NY, EE. UU.: ACM, págs. 135–143, doi : 10.1145 / 800057.808675 , ISBN 0-89791-133-4.
- Harel, Dov; Tarjan, Robert E. (1984), "Algoritmos rápidos para encontrar ancestros comunes más cercanos", SIAM Journal on Computing , 13 (2): 338–355, doi : 10.1137 / 0213024.
- Hu, TC (1961), "El problema de la ruta de capacidad máxima", Investigación de operaciones , 9 (6): 898–900, doi : 10.1287 / opre.9.6.898 , JSTOR 167055.
- Leclerc, Bruno (1981), "Descripción 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 0623034.
- 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 , Londres, Reino Unido: Springer-Verlag, págs. 499– 509, doi : 10.1007 / 3-540-51542-9_41.
- Seidel, Raimund ; Aragon, Cecilia R. (1996), "Árboles de búsqueda aleatorios" , Algorithmica , 16 (4/5): 464–497, doi : 10.1007 / s004539900061.
- Schieber, Baruch; Vishkin, Uzi (1988), "Sobre la búsqueda de ancestros comunes más bajos: simplificación y paralelización", SIAM Journal on Computing , 17 (6): 1253-1262, doi : 10.1137 / 0217079.
- Shun, Julian; Blelloch, Guy E. (2014), "Un algoritmo de árbol cartesiano paralelo simple y su aplicación a la construcción de árboles de sufijos paralelos", Transacciones de ACM en computación paralela , 1 : 1–20, doi : 10.1145 / 2661653.
- Vuillemin, Jean (1980), "Una mirada unificadora a las estructuras de datos", Communications of the ACM , Nueva York, NY, EE. UU .: ACM, 23 (4): 229-239, doi : 10.1145 / 358841.358852.