Árbol cartesiano
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.
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.
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.
Esta idea fue aplicada por Seidel y Aragon (1996), quienes sugirieron el uso de números aleatorios como prioridades.
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.
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.
El vecino derecho se puede encontrar aplicando el mismo algoritmo de pila a la secuencia inversa.
En su algoritmo, la cola con prioridad consiste solo de elementos cuyos padres en el árbol cartesiano han sido encontrados y eliminados.
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.
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.
