árbol cartesiano

En informática , un árbol cartesiano es un árbol binario derivado de una secuencia de números distintos. Para construirlo, se establece como raíz el número mínimo de la secuencia y se construyen recursivamente sus subárboles izquierdo y derecho a partir de las subsecuencias anteriores y posteriores a 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 rango geométrico . También se han utilizado en la definición de las estructuras de datos de árbol de búsqueda binaria aleatorio y treap para problemas de búsqueda binaria , en algoritmos de ordenación por comparación que funcionan eficientemente en entradas casi ordenadas, y como base para algoritmos de coincidencia de patrones . Un árbol cartesiano para una secuencia se puede construir en tiempo lineal .

Definición

Los árboles cartesianos se definen mediante árboles binarios , que son una forma de árbol con raíz . Para construir el árbol cartesiano para una secuencia dada de números distintos, se establece su raíz como el número mínimo de la secuencia ^{[ 1 ]} y se construyen recursivamente sus subárboles izquierdo y derecho a partir de las subsecuencias anteriores y posteriores a este número, respectivamente. Como caso base, cuando una de estas subsecuencias está vacía, no hay hijos izquierdo ni derecho ^{[ 2 ] .}

También es posible caracterizar el árbol cartesiano directamente, en lugar de recursivamente, utilizando sus propiedades de ordenación. En cualquier árbol, el subárbol con raíz en cualquier nodo consta de todos los demás nodos que pueden alcanzarlo siguiendo repetidamente los punteros a los nodos padres. El árbol cartesiano para una secuencia de números distintos se define mediante las siguientes propiedades:

El árbol cartesiano de una secuencia es un árbol binario con un nodo por cada número de la secuencia.
Un recorrido simétrico (en orden) del árbol da como resultado la secuencia original. De forma equivalente, para cada nodo, los números en su subárbol izquierdo son anteriores a él en la secuencia, y los números en el subárbol derecho son posteriores.
El árbol tiene la propiedad min-heap : el padre de cualquier nodo que no sea la raíz tiene un valor menor que el propio nodo. ^{[ 1 ]}

Estas dos definiciones son equivalentes: el árbol definido recursivamente como se describió anteriormente es el único árbol que posee las propiedades enumeradas. 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 considerarse el menor de los dos. ^{[ 2 ]}

Historia

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 del caso promedio de las operaciones de concatenación y división en árboles de búsqueda binaria . El nombre 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 que se analiza más adelante, un árbol cartesiano para un conjunto de puntos tiene el orden ordenado de los puntos según su $x$ -coordenadas como su orden de recorrido simétrico, y tiene la propiedad de montón según el $y$ -coordenadas de los puntos. Vuillemin describió tanto esta versión geométrica de la estructura como la definición aquí presentada, en la que un árbol cartesiano se define a partir de una secuencia. El uso de secuencias en lugar de coordenadas de puntos proporciona un marco más general que permite aplicar el árbol cartesiano también a problemas no geométricos. ^{[ 2 ]}

Construcción eficiente

Un árbol cartesiano se puede construir en tiempo lineal a partir de su secuencia de entrada. Un método consiste en procesar los valores de la secuencia de izquierda a derecha, manteniendo el árbol cartesiano de los nodos procesados hasta el momento, en una estructura que permite el recorrido ascendente y descendente del árbol. Para procesar cada nuevo valor $a$ , comience en el nodo que representa el valor anterior a $a$ en la secuencia y siga el camino desde este nodo hasta la raíz del árbol hasta encontrar un valor $b$ más pequeño que $a$ . El nodo $a$ se convierte en el hijo legítimo de $b$ y el anterior hijo derecho de $b$ se convierte en el nuevo hijo izquierdo de $a$ El tiempo total para este procedimiento es lineal, porque el tiempo empleado en buscar el padre $b$ de cada nuevo nodo $a$ se puede cobrar en función del número de nodos que se eliminan del camino más a la derecha del árbol. ^{[ 3 ]}

Un algoritmo de construcción alternativo de tiempo lineal se basa en el problema de todos los valores más pequeños cercanos . En la secuencia de entrada, defina el vecino izquierdo de un valor. $a$ ser el valor que ocurre antes de $a$ es más pequeño que $a$ y está más cerca en posición de $a$ 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 $a$ , la pila se va vaciando hasta que esté vacía o su elemento superior sea menor que $a$ , y luego $a$ se empuja a la pila. El vecino izquierdo de $a$ es el elemento superior en ese momento $a$ se empuja. Los vecinos correctos se pueden encontrar aplicando el mismo algoritmo de pila al inverso de la secuencia. El padre de $a$ en el árbol cartesiano es o bien el vecino izquierdo de $a$ o el vecino derecho de $a$ , 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 la estrategia de divide y vencerás . Este 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 ramas izquierda y derecha de estos árboles: la rama izquierda es el camino obtenido al seguir las aristas hijas izquierdas desde la raíz hasta llegar a un nodo sin hija izquierda, y la rama derecha se define simétricamente. Al igual que con cualquier camino en un min-heap, ambas ramas tienen sus valores ordenados, desde el valor más pequeño en su raíz hasta el valor más grande al final del camino. Para fusionar los dos árboles, se aplica un algoritmo de fusión a la rama derecha del árbol izquierdo y a la rama izquierda del árbol derecho, reemplazando estos dos caminos en los dos árboles por un único camino que contiene 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, en la misma posición que se utilizó previamente 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 puede calcularse en paralelo, y la operación de fusión también puede paralelizarse de manera eficiente . ^{[ 5 ]}

Otro algoritmo de tiempo lineal, que utiliza una representación de lista enlazada de la secuencia de entrada, se basa en el enlace de máximo local : el algoritmo identifica repetidamente un elemento de máximo local , es decir, uno que es mayor que sus dos vecinos (o que su único vecino, en caso de que sea el primer o último elemento de la lista). Este elemento se elimina de la lista y se adjunta como hijo derecho de su vecino izquierdo, o hijo izquierdo de su vecino derecho, dependiendo de cuál de los dos vecinos tenga un valor mayor, resolviendo los empates arbitrariamente. Este proceso se puede implementar en una sola pasada de izquierda a derecha de la entrada, y es fácil ver que cada elemento puede obtener como máximo un hijo izquierdo y como máximo un hijo derecho, y que el árbol binario resultante es un árbol cartesiano de la secuencia de entrada. ^{[ 6 ]}^{[ 7 ]}

Es posible mantener el árbol cartesiano de una entrada dinámica, sujeta a inserciones y eliminación diferida de elementos, en un tiempo amortizado logarítmico por operación. Aquí, la eliminación diferida significa que una operación de eliminación se realiza marcando un elemento en el árbol como eliminado, pero sin eliminarlo realmente del árbol. Cuando el número de elementos marcados alcanza una fracción constante del tamaño total del árbol, este se reconstruye, conservando solo los elementos no marcados. ^{[ 8 ]}

Aplicaciones

Búsqueda de rangos y antepasados comunes más bajos

Los árboles cartesianos forman parte de una estructura de datos eficiente para consultas de mínimo de rango . La 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. ^{[ 9 ]} 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). Dado 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 almacenarse y se puede construir en tiempo lineal, los mismos límites se mantienen para el problema de minimización de rango. ^{[ 10 ]}

Bender y Farach-Colton (2000) invirtieron esta relación entre los dos problemas de estructuras de datos al demostrar que las estructuras de datos para la minimización de rangos también podían utilizarse para encontrar los ancestros comunes más bajos. Su estructura de datos asocia a cada nodo del árbol su distancia a la raíz y construye una secuencia de estas distancias en el orden de un recorrido de Euler del árbol (con aristas duplicadas). A continuación, 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 del á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 utilizarse para las secuencias resultantes de esta transformación, las cuales 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. ^{[ 11 ]}

El mismo problema de minimización de rango también puede interpretarse de forma alternativa en términos de búsqueda de rango bidimensional. Una colección de un número finito de puntos en el plano cartesiano puede utilizarse para formar un árbol cartesiano, ordenando los puntos según su $x$ -coordenadas y utilizando el $y$ -coordenadas 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\leq x\leq R$ , $p$ es el punto más a la izquierda en $S$ (el que tiene mínimo $x$ -coordenada), y $q$ es el punto más a la derecha en $S$ (el que tiene máximo $x$ -coordenada) entonces el ancestro común más bajo de $p$ y $q$ 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. $L\leq x\leq R$ y $y\leq T$ , se puede responder encontrando este punto más bajo $b$ , comparando su $y$ -coordinar con $T$ y (si el punto se encuentra dentro de la región de tres lados) continuando recursivamente en las dos losas delimitadas entre $p$ y $b$ y entre $b$ y $q$ De esta forma, una vez identificados los puntos más a la izquierda y más a la derecha de la losa, se pueden listar todos los puntos dentro de la región de tres lados 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 igual al peso de la ruta minimax en el árbol de expansión mínima de la métrica. ^{[ 12 ]} 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, el árbol de expansión mínima se divide 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 encontrado el árbol de expansión mínima y ordenados los pesos de sus aristas, el árbol cartesiano puede construirse en tiempo lineal. ^{[ 13 ]}

Como un árbol de búsqueda binaria

El árbol cartesiano de una secuencia ordenada es simplemente un grafo de caminos , enraizado en su extremo izquierdo. La búsqueda binaria en este árbol degenera en una búsqueda secuencial en el camino. 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 puede verse de forma equivalente en el marco geométrico descrito anteriormente, en el que $x$ -las coordenadas de un conjunto de puntos son los valores en una secuencia ordenada y el $y$ -las coordenadas son sus prioridades. ^{[ 14 ]}

Esta idea fue aplicada por Seidel y Aragon (1996) , quienes sugirieron el uso de números aleatorios como prioridades. El árbol de búsqueda binaria autoequilibrado resultante de esta elección aleatoria se denomina treap , debido a su combinación de características de árbol de búsqueda binaria 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 del árbol a lo largo de una ruta desde el nodo hasta la raíz del árbol para corregir cualquier violación de la propiedad heap causada por esta inserción; una eliminación se puede realizar de manera similar mediante una cantidad constante de cambio en el árbol seguida de una secuencia de rotaciones a lo largo de una única ruta en el árbol. ^{[ 14 ]} Una variación de esta estructura de datos llamada zip tree 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. ^{[ 15 ]}

Si las prioridades de cada clave se eligen aleatoriamente e independientemente una vez que la clave se inserta en el árbol, el árbol cartesiano resultante tendrá las mismas propiedades que un árbol de búsqueda binaria aleatorio , un árbol calculado insertando las claves en una permutación elegida aleatoriamente a partir de un árbol vacío, donde 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 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 a cualquier valor dado es como máximo $2\ln n$ 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 $C$ de tal manera que la profundidad sea $\leq C\ln n$ con una probabilidad que tiende a uno a medida que el número de nodos tiende a infinito. Este mismo buen comportamiento se extiende a los treaps. También es posible, como sugieren Aragon y Seidel, repriorizar los nodos de acceso frecuente, lo que provoca que se muevan hacia la raíz del treap y acelera los accesos futuros a las mismas claves. ^{[ 14 ]}

Al clasificar

Levcopoulos y Petersson (1989) describen un algoritmo de ordenación basado en árboles cartesianos. Describen el algoritmo como basado en un árbol con el máximo en la raíz ^{[ 16 ]} , pero puede modificarse fácilmente para admitir un árbol cartesiano con la convención de que el valor mínimo se encuentra en la raíz. Para mayor coherencia, es esta versión modificada del algoritmo la que se describe a continuación.

El algoritmo de Levcopoulos-Petersson puede considerarse una versión del algoritmo de ordenación por selección o de ordenación 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 dicho 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 ha sido encontrado y eliminado. Por lo tanto, el algoritmo consta de los siguientes pasos: ^{[ 16 ]}

Construye un árbol cartesiano para la secuencia de entrada.
Inicializa una cola de prioridad, que inicialmente contiene solo la raíz del árbol.
Mientras la cola de prioridad no esté vacía:
- Encuentra y elimina el valor mínimo en la cola de prioridad.
- Agregue este valor a la secuencia de salida.
- Agregue los hijos del árbol cartesiano del valor eliminado a la cola de prioridad.

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 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 $O(n\log k)$ , dónde $n$ es la longitud de la secuencia y $k$ es el promedio, sobre todos los valores de la secuencia, del número de pares consecutivos de valores de la secuencia que delimitan el valor dado (lo que significa que el valor dado está entre los dos valores de la secuencia). También demuestran una cota inferior que establece que, para cualquier $n$ y (no constante) $k$ cualquier algoritmo de ordenación basado en comparaciones debe utilizar $\Omega (n\log k)$ comparaciones para algunas entradas. ^{[ 16 ]}

En la coincidencia de patrones

El problema de la búsqueda de coincidencias en árboles cartesianos se ha definido como una forma generalizada de búsqueda 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 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. ^{[ 17 ]}

Notas

1 2 En algunas referencias, el orden de los números está invertido, por lo que el nodo raíz contiene el valor máximo y el árbol tiene la propiedad de montículo máximo en lugar de la propiedad de montículo mínimo.
1 2 3 Vuillemin (1980) .
^ Gabow , Bentley y Tarjan (1984) .
↑ Berkman, Schieber y Vishkin (1993) .
↑ Shun y Blelloch (2014) .
↑ Kozma y Saranurak (2020) .
↑ Hartmann et al. (2021) .
↑ Bialynicka-Birula y Grossi (2006) .
^ Gabow, Bentley y Tarjan (1984) ; Bender y Farach-Colton (2000) .
^ Harel y Tarjan (1984) ; Schieber y Vishkin (1988) .
↑ Bender y Farach-Colton (2000) .
↑ Hu (1961) ; Leclerc (1981)
↑ Demaine, Landau y Weimann (2009) .
1 2 3 Seidel y Aragon (1996) .
↑ Tarjan, Levy y Timmel (2021) .
^ Levcopoulos y Petersson ( 1989 ) .
^ Parque y col. (2019) ; Parque y col. (2020) ; Canción y col. (2021) ; Kim y Cho (2021) ; Nishimoto et al. (2021) ; Oizumi et al. (2022)

Referencias

Bender, Michael A.; Farach-Colton, Martin (2000), "El problema del LCA revisitado", Actas del 4.º Simposio Latinoamericano de Informática Teórica , Springer-Verlag, Lecture Notes in Computer Science 1776, pp . 88–94
Berkman, Omer; Schieber, Baruch ; Vishkin, Uzi (1993), "Algoritmos paralelos doblemente logarítmicos óptimos basados en la búsqueda de todos los valores más pequeños cercanos", Journal of Algorithms , 14 (3): 344–370 , doi : 10.1006/jagm.1993.1018
Bialynicka-Birula, Iwona; Grossi, Roberto (2006), "Rigidez amortizada en árboles cartesianos dinámicos", en Durand, Bruno; Thomas, Wolfgang (eds.), STACS 2006, 23.º Simposio Anual sobre Aspectos Teóricos de la Informática, Marsella, Francia, 23-25 de febrero de 2006, Actas , Lecture Notes in Computer Science, vol. 3884, Springer, pp. 80–91 , doi : 10.1007/11672142_5 , ISBN 978-3-540-32301-3
Demaine, Erik D .; Landau, Gad M.; Weimann, Oren (2009), "Sobre árboles cartesianos y consultas de mínimo de rango", Autómatas, lenguajes y programación, 36.º Coloquio Internacional, ICALP 2009, Rodas, Grecia, 5-12 de julio de 2009 , Lecture Notes in Computer Science, vol. 5555, pp. 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 Coincidencia de Patrones Combinatorios , Lecture Notes in Computer Science, vol. 4009, Springer-Verlag, pp. 36–48 , doi : 10.1007/11780441_5 , ISBN 978-3-540-35455-0
Fischer, Johannes; Heun, Volker (2007), "Una nueva representación sucinta de la información RMQ y mejoras en el array de sufijos mejorado.", Actas del Simposio Internacional sobre Combinatoria, Algoritmos, Metodologías Probabilísticas y Experimentales , Lecture Notes in Computer Science, vol. 4614, Springer-Verlag, pp. 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: Actas del 16.º Simposio ACM sobre Teoría de la Computación , Nueva York, NY, EE. UU.: ACM, págs. 135-143 , doi : 10.1145/800057.808675 , ISBN 0-89791-133-4, S2CID 17752833
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
Hartmann, Maria; Kozma, László; Sinnamon, Corwin; Tarjan, Robert E. (2021), "Análisis de montículos suaves y montículos delgados", ICALP , Actas Internacionales Leibniz en Informática (LIPIcs), vol. 198, pp. 79:1–79:20, doi : 10.4230/LIPIcs.ICALP.2021.79 , ISBN 978-3-95977-195-5
Hu, TC (1961), "El problema de la ruta de máxima capacidad", Operations Research , 9 (6): 898–900 , doi : 10.1287/opre.9.6.898 , JSTOR 167055
Kim, Sung-Hwan; Cho, Hwan-Gue (2021), "Un índice compacto para la coincidencia de árboles cartesianos", en Gawrychowski, Pawel; Starikovskaya, Tatiana (eds.), 32.º Simposio Anual sobre Coincidencia de Patrones Combinatorios, CPM 2021, 5-7 de julio de 2021, Wrocław, Polonia , LIPIcs, vol. 191, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 18:1–18:19, doi : 10.4230/LIPIcs.CPM.2021.18 , ISBN 9783959771863
Kozma, László; Saranurak, Thatchaphol (2020), "Montículos suaves y una visión dual de las estructuras de datos autoajustables", SIAM J. Comput. , 49 (5), SIAM, arXiv : 1802.05471 , doi : 10.1137/18M1195188
Leclerc, Bruno (1981), "Descripción combinatoria de 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 - Adaptado para archivos preordenados", WADS '89: Actas del Taller sobre Algoritmos y Estructuras de Datos , Lecture Notes in Computer Science, vol. 382, Londres, Reino Unido: Springer-Verlag, pp. 499–509 , doi : 10.1007/3-540-51542-9_41 , ISBN 978-3-540-51542-5
Nishimoto, Akio; Fujisato, Noriki; Nakashima, Yuto; Inenaga, Shunsuke (2021), "Position heaps for Cartesian-tree matching on strings and tries", en Lecroq, Thierry; Touzet, Hélène (eds.), String Processing and Information Retrieval - 28th International Symposium, SPIRE 2021, Lille, Francia, 4-6 de octubre de 2021, Proceedings , Lecture Notes in Computer Science, vol. 12944, Springer, pp. 241–254 , arXiv : 2106.01595 , doi : 10.1007/978-3-030-86692-1_20 , ISBN 978-3-030-86691-4, S2CID 235313506
Oizumi, Tsubasa; Kai, Takeshi; Mieno, Takuya; Inenaga, Shunsuke; Arimura, Hiroki (2022), "Cartesian Tree Subsequence Matching", en Bannai, Hideo; Holub, Jan (eds.), 33rd Annual Symposium on Combinatorial Pattern Matching, CPM 2022, 27-29 de junio de 2022, Praga, República Checa , LIPIcs, vol. 223, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 14:1–14:18, doi : 10.4230/LIPIcs.CPM.2022.14 , ISBN 9783959772341, S2CID 246679910
Parque, Sung Gwan; Amir, Amihood; Landau, Gad M.; Park, Kunsoo (2019), "Indización y coincidencia de árboles cartesianos", en Pisanti, Nadia; Pissis, Solon P. (eds.), 30.º Simposio anual sobre coincidencia de patrones combinatorios, CPM 2019, 18-20 de junio de 2019, Pisa, Italia , LIPIcs, vol. 128, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, págs. 16:1–16:14, arXiv : 1905.08974 , doi : 10.4230/LIPIcs.CPM.2019.16 , ISBN 9783959771030, S2CID 162168587
Park, Sung Gwan; Bataa, Magsarjav; Amir, Amihood; Landau, Gad M.; Park, Kunsoo (2020), "Finding patterns and periods in Cartesian tree matching", Theoretical Computer Science , 845 : 181–197 , doi : 10.1016/j.tcs.2020.09.014 , S2CID 225227284
Seidel, Raimund ; Aragon, Cecilia R. (1996), "Árboles de búsqueda aleatorios" , Algorithmica , 16 (4/5): 464–497 , doi : 10.1007/s004539900061 (inactivo el 1 de julio de 2025){{citation}}: CS1 maint: DOI inactivo desde julio de 2025 ( enlace )
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 simple de árbol cartesiano paralelo y su aplicación a la construcción de árboles de sufijos paralelos", ACM Transactions on Parallel Computing , 1 : 1–20 , doi : 10.1145/2661653 , S2CID 1912378
Song, Siwoo; Gu, Geonmo; Ryu, Cheol; Faro, Simone; Lecroq, Thierry; Park, Kunsoo (2021), "Algoritmos rápidos para la coincidencia de árboles cartesianos de patrones únicos y múltiples", Theoretical Computer Science , 849 : 47–63 , doi : 10.1016/j.tcs.2020.10.009 , S2CID 225142815
Tarjan, Robert E .; Levy, Caleb C.; Timmel, Stephen (2021), "Árboles Zip", ACM Transactions on Algorithms , 17 (4): 34:1–34:12, arXiv : 1806.06726 , doi : 10.1145/3476830 , S2CID 49298052
Vuillemin, Jean (1980), "Una mirada unificadora a las estructuras de datos", Communications of the ACM , 23 (4), Nueva York, NY, EE. UU.: ACM: 229–239 , doi : 10.1145/358841.358852 , S2CID 10462194

[minmax-1] 1 2 En algunas referencias, el orden de los números está invertido, por lo que el nodo raíz contiene el valor máximo y el árbol tiene la propiedad de montículo máximo en lugar de la propiedad de montículo mínimo.

[FOOTNOTEVuillemin1980-2] 1 2 3 Vuillemin (1980) .

[FOOTNOTEGabowBentleyTarjan1984-3] Gabow , Bentley y Tarjan (1984) .

[4] Berkman, Schieber y Vishkin (1993) .

[FOOTNOTEShunBlelloch2014-5] Shun y Blelloch (2014) .

[FOOTNOTEKozmaSaranurak2020-6] Kozma y Saranurak (2020) .

[FOOTNOTEHartmannKozmaSinnamonTarjan2021-7] Hartmann et al. (2021) .

[FOOTNOTEBialynicka-BirulaGrossi2006-8] Bialynicka-Birula y Grossi (2006) .

[9] Gabow, Bentley y Tarjan (1984) ; Bender y Farach-Colton (2000) .

[10] Harel y Tarjan (1984) ; Schieber y Vishkin (1988) .

[FOOTNOTEBenderFarach-Colton2000-11] Bender y Farach-Colton (2000) .

[12] Hu (1961) ; Leclerc (1981)

[FOOTNOTEDemaineLandauWeimann2009-13] Demaine, Landau y Weimann (2009) .

[FOOTNOTESeidelAragon1996-14] 1 2 3 Seidel y Aragon (1996) .

[FOOTNOTETarjanLevyTimmel2021-15] Tarjan, Levy y Timmel (2021) .

[FOOTNOTELevcopoulosPetersson1989-16] Levcopoulos y Petersson ( 1989 ) .

[17] Parque y col. (2019) ; Parque y col. (2020) ; Canción y col. (2021) ; Kim y Cho (2021) ; Nishimoto et al. (2021) ; Oizumi et al. (2022)

[ 1 ]

[ 2 ] .

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]