Árbol de rango

En informática , un árbol de rangos es una estructura de datos de árbol ordenada para contener una lista de puntos. Permite que todos los puntos dentro de un rango determinado se notifiquen de manera eficiente y, por lo general, 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 rangos 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 )${\ Displaystyle O (\ log ^ {d} n + k)}$pero peor almacenamiento de , donde n es el número de puntos almacenados en el árbol, d es la dimensión de cada punto yk es el número de puntos reportados por una consulta dada.${\ Displaystyle O (n \ log ^ {d-1} n)}$

Bernard Chazelle mejoró esto para consultar la complejidad del tiempo y el espacio . ^{[5] [6]}${\ Displaystyle O (\ log ^ {d-1} n + k)}$${\displaystyle O\left(n\left({\frac {\log n}{\log \log n}}\right)^{d-1}\right)}$

Un árbol de rango en un conjunto de puntos unidimensionales es un árbol de búsqueda binario balanceado en esos puntos. Los puntos almacenados en el árbol se almacenan en las hojas del árbol; cada nodo interno almacena el mayor valor de su subárbol izquierdo. Un árbol de rango en un conjunto de puntos en d -dimensions es un árbol de búsqueda binaria multinivel definido de forma recursiva . 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 ( d −1) -dimensional en el último ( d−1) -coordenadas 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 más altas se construyen recursivamente construyendo un árbol de búsqueda binario balanceado 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 distribución de esta manera requeriría tiempo.${\displaystyle O(n\log n)}$${\displaystyle O(n\log ^{d}n)}$

Un ejemplo de un árbol de rango unidimensional. Cada nodo que no es una hoja almacena el valor más grande de su subárbol izquierdo.

Una consulta de rango unidimensional [ x ₁ , x ₂ ]. Se informarán los puntos almacenados en los subárboles sombreados en gris. find ( x ₁ ) y find ( x ₂ ) se informarán si están dentro del intervalo de consulta.