Árbol Cartesiano

En Ciencias de la Computación, el árbol Cartesiano es un árbol binario que se deriva de una secuencia 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.