En informática , un árbol de rango es una estructura de datos de árbol ordenado para contener una lista de puntos. Permite informar de manera eficiente todos los puntos dentro de un rango determinado y generalmente se usa en dos o más dimensiones. Los árboles de pasto fueron introducidos por Jon Louis Bentley en 1979. [1] Lueker, [2] Lee y Wong, [3] y Willard descubrieron de forma independiente estructuras de datos similares . [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 (en notación Big O ) pero un 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 reportados por una consulta dada.
Bernard Chazelle mejoró esto para consultar la complejidad del tiempo y el espacio . [5] [6]
Un árbol de rango en un conjunto de puntos unidimensionales es un árbol de búsqueda binario equilibrado en 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 en un conjunto de puntos en dimensiones d es un árbol de búsqueda binaria multinivel definido recursivamente . Cada nivel de la estructura de datos es un árbol de búsqueda binario en una de las dimensiones d . El primer nivel es un árbol de búsqueda binario en la primera de las coordenadas d . Cada vértice v de este árbol contiene una estructura asociada que es un árbol de rango dimensional ( d −1) en las últimas coordenadas ( d −1) de los puntos almacenados en el subárbol de v .
Un árbol de rango unidimensional en 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 equilibrado en la primera coordenada de los puntos y luego, para cada vértice v en este árbol, construyendo un árbol de rango ( d −1)-dimensional en los puntos contenidos en el subárbol de v . Construir un árbol de pasto de esta manera requeriría tiempo.
Este tiempo de construcción se puede mejorar para árboles de rango bidimensionales . [7] Sea S un conjunto de n puntos bidimensionales. Si S contiene solo un punto, devuelve una hoja que contiene 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 coordenada x mediana 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 el hijo izquierdo v L y el 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 sus coordenadas x , podemos construir las estructuras asociadas de cada subárbol en tiempo lineal. Esto reduce el tiempo para construir un árbol de rango bidimensional y también reduce el tiempo para construir un árbol de rango d -dimensional .
Una consulta de rango en un árbol de rango informa el conjunto de puntos que se encuentran dentro de un intervalo determinado. 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 hacia 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, informar 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 informar la hoja de esta ruta si se encuentra dentro del intervalo de consulta.
Dado que el árbol de rango es un árbol binario equilibrado, las rutas de búsqueda hacia x 1 y x 2 tienen una longitud de . Se puede informar de todos los puntos almacenados en el subárbol de un vértice 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 el número 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 dimensional ( d −1) 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 d -dimensional consta de consultas de rango d -dimensional, se deduce que el tiempo necesario para realizar una consulta de rango d -dimensional 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 fraccionada . [2] [4] [7]
