Árbol de la cordillera

Un árbol de rango unidimensional sobre un conjunto de n puntos es un árbol de búsqueda binaria, que se puede construir en${\displaystyle O(n\log n)}$tiempo. Los árboles de rango en dimensiones superiores se construyen recursivamente construyendo un árbol de búsqueda binaria balanceado en la primera coordenada de los puntos y luego, para cada vértice v en este árbol, construyendo un árbol de rango de ( d -1) dimensiones en los puntos contenidos en el subárbol de v . Construir un árbol de rango de esta manera requeriría${\displaystyle O(n\log ^{d}n)}$tiempo.

Este tiempo de construcción se puede mejorar para árboles de rango bidimensionales.${\displaystyle O(n\log n)}$[ ^{7 ]} Sea S un conjunto de n puntos bidimensionales. Si S contiene solo un punto, devuelva una hoja que contenga ese punto. De lo contrario, construya la estructura asociada de S , un árbol ^de rango unidimensional en las coordenadas y de los puntos en S. Sea x _m la mediana de la coordenada x de los puntos. Sea S _L el conjunto de puntos con coordenada x menor o igual a x _m y sea S _R el conjunto de puntos con coordenada x mayor que x _m . Construya recursivamente v _L , un árbol de rango bidimensional en S _L , y v _R , un árbol de rango bidimensional en S _R. Cree un vértice v con hijo izquierdo v _L e hijo derecho v _R. Si ordenamos los puntos por sus coordenadas y al inicio del algoritmo, y mantenemos este orden al dividir los puntos por su coordenada x , podemos construir las estructuras asociadas de cada subárbol en tiempo lineal. Esto reduce el tiempo necesario para construir un árbol de rango bidimensional.${\displaystyle O(n\log n)}$y también reduce el tiempo para construir un árbol de rango d -dimensional a${\displaystyle O(n\log ^{d-1}n)}$.

Una consulta de rango en un árbol de rango informa el conjunto de puntos que se encuentran dentro de un intervalo dado. Para informar los puntos que se encuentran en el intervalo [ x ₁ , x ₂ ], comenzamos buscando x ₁ y x ₂ . En algún vértice del árbol, las rutas de búsqueda hacia x ₁ y x ₂ divergirán. Sea v _split el último vértice que estas dos rutas de búsqueda tienen en común. Para cada vértice v en la ruta de búsqueda desde v _split hasta x ₁ , si el valor almacenado en v es mayor que x ₁ , informa cada punto en el subárbol derecho de v . Si v es una hoja, informa el valor almacenado en v si está dentro del intervalo de consulta. De manera similar, informa todos los puntos almacenados en los subárboles izquierdos de los vértices con valores menores que x ₂ a lo largo de la ruta de búsqueda desde v _split hasta x ₂ , e informa la hoja de esta ruta si se encuentra dentro del intervalo de consulta.

Dado que el árbol de rangos es un árbol binario equilibrado, las rutas de búsqueda a x ₁ y x ₂ tienen longitud${\displaystyle O(\log n)}$. Informar todos los puntos almacenados en el subárbol de un vértice se puede hacer en tiempo lineal utilizando cualquier algoritmo de recorrido de árboles . Por lo tanto, el tiempo para realizar una consulta de rango es${\displaystyle O(\log n+k)}$donde k es el número de puntos en el intervalo de consulta.

Las consultas de rango en d dimensiones son similares. En lugar de informar todos los puntos almacenados en los subárboles de las rutas de búsqueda, se realiza una consulta de rango ( d -1)-dimensional en la estructura asociada de cada subárbol. Eventualmente, se realizará una consulta de rango 1-dimensional y se informarán los puntos correctos. Dado que una consulta d -dimensional consta de${\displaystyle O(\log n)}$Consultas de rango de ( d -1) dimensiones, se deduce que el tiempo requerido para realizar una consulta de rango de d dimensiones es${\displaystyle O(\log ^{d}n+k)}$donde k es el número de puntos en el intervalo de consulta. Esto se puede reducir a${\displaystyle O(\log ^{d-1}n+k)}$utilizando una variante de cascada fraccionaria . ^{[ 2 ] [ 4 ] [ 7 ]}