En informática , un árbol de rango es una estructura de datos de árbol ordenado para contener una lista de puntos. Permite que todos los puntos dentro de un rango dado se informen de manera eficiente y, por lo general, se utiliza en dos o más dimensiones. Los árboles de rango fueron introducidos por Jon Louis Bentley en 1979. [1] Lueker, [2] Lee y Wong, [3] y Willard descubrieron estructuras de datos similares de forma independiente . [4] El árbol de rango es una alternativa al árbol k -d . En comparación con los árboles k -d, los árboles de rango ofrecen tiempos de consulta más rápidos de (en notación Big O ) pero peor almacenamiento de , donde n es el número de puntos almacenados en el árbol, d es la dimensión de cada punto y k es el número de puntos informados por una consulta dada.
En 1990, Bernard Chazelle mejoró esto para consultar la complejidad del tiempo y el espacio . [5] [6]
Un árbol de rango sobre un conjunto de puntos unidimensionales es un árbol binario de búsqueda equilibrado sobre esos puntos. Los puntos almacenados en el árbol se almacenan en las hojas del árbol; cada nodo interno almacena el valor más grande de su subárbol izquierdo. Un árbol de rango sobre un conjunto de puntos en d -dimensiones es un árbol binario de búsqueda de múltiples niveles definido recursivamente . Cada nivel de la estructura de datos es un árbol binario de búsqueda sobre una de las d -dimensiones. El primer nivel es un árbol binario de búsqueda sobre la primera de las d -coordenadas. Cada vértice v de este árbol contiene una estructura asociada que es un árbol de rango ( d −1)-dimensional sobre las últimas ( d −1)-coordenadas de los puntos almacenados en el subárbol de v .
Un árbol de rango unidimensional sobre un conjunto de n puntos es un árbol de búsqueda binario, que se puede construir en el tiempo. Los árboles de rango en dimensiones superiores se construyen recursivamente construyendo un árbol de búsqueda binario balanceado sobre la primera coordenada de los puntos y luego, para cada vértice v en este árbol, construyendo un árbol de rango ( d −1)-dimensional sobre los puntos contenidos en el subárbol de v . Construir un árbol de rango de esta manera requeriría tiempo.
Este tiempo de construcción se puede mejorar para árboles de rango bidimensionales a . [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 la coordenada x menor o igual que x m y sea S R el conjunto de puntos con la 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 y hijo derecho v R . Si ordenamos los puntos por sus coordenadas y al comienzo 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 para construir un árbol de rango bidimensional a , y también reduce el tiempo para construir un árbol de rango ddimensional a .
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 1 , x 2 ], comenzamos buscando x 1 y x 2 . En algún vértice del árbol, las rutas de búsqueda a x 1 y x 2 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 1 , si el valor almacenado en v es mayor que x 1 , informe cada punto en el subárbol derecho de v . Si v es una hoja, informe el valor almacenado en v si está dentro del intervalo de consulta. De manera similar, informe todos los puntos almacenados en los subárboles izquierdos de los vértices con valores menores que x 2 a lo largo de la ruta de búsqueda desde v split hasta x 2 , e informe la hoja de esta ruta si se encuentra dentro del intervalo de consulta.
Dado que el árbol de rango es un árbol binario balanceado, las rutas de búsqueda a x 1 y x 2 tienen una longitud de . La generación de informes de todos los puntos almacenados en el subárbol de un vértice se puede realizar en tiempo lineal utilizando cualquier algoritmo de recorrido de árbol . De ello se deduce que el tiempo para realizar una consulta de rango es , donde k es la cantidad de puntos en el intervalo de consulta.
Las consultas de rango en dimensiones d son similares. En lugar de informar todos los puntos almacenados en los subárboles de las rutas de búsqueda, realice una consulta de rango de ( d −1) dimensiones en la estructura asociada de cada subárbol. Finalmente, se realizará una consulta de rango unidimensional y se informarán los puntos correctos. Dado que una consulta de dimensión d consta de consultas de rango de ( d −1) dimensiones, se deduce que el tiempo necesario para realizar una consulta de rango de dimensión d es , donde k es el número de puntos en el intervalo de consulta. Esto se puede reducir al uso de una variante de cascada fraccionaria . [2] [4] [7]
