Apéndice B Búsquedas dentro de un rango

Un problema clásico en geometría computacional es la búsqueda dentro de un rango. El problema se puede definir de la siguiente manera:
Tenemos un conjunto de puntos en el espacio n-dimensional. Se trata de encontrar de forma eficiente el conjunto de puntos cuyas coordenadas se encuentran situadas dentro de un rango. En el caso de dos dimensiones el rango especificado podría ser [x₁:x₂]×[y₁:y₂], indicando que las coordenadas de los puntos que se devuelven tienen que estar comprendidas entre dichos intervalos.

Se pueden encontrar varias propuestas en la literatura de tipos de datos para realizar estas búsquedas. En [de Berg et al.1997] se presentan algunas de las estructuras de datos más eficientes para realizar estas consultas, de las cuales se ha seleccionado la que presenta una menor complejidad en el tiempo de consulta. La estructura seleccionada es el árbol de rango (Range Tree) que es una ampliación del clásico árbol binario en una dimensión. En la siguiente sección se comenta la estructura del árbol binario y la forma de interrogar a dicho árbol, analizándose la complejidad de dicha estructura. En la Sección B.2 se detalla cómo se puede crear la estructura de árbol de rango y cómo se realiza la consulta de rango a dicha estructura.

B.1 Búsqueda unidimensional

Una búsqueda en una única dimensión es trivial: ordenamos todos los valores en un vector y simplemente realizamos una búsqueda lineal viendo qué valores se encuentran entre el rango especificado. Sin embargo aquí vamos a introducir una estructura de datos llamada árbol binario y que sirve de base para ampliar a mayores dimensiones. Cada nodo de este árbol tendrá la siguiente información: Un valor V, un puntero a un subárbol izquierda L y otro a un subárbol derecha R. Dado un conjunto de valores ordenados de menor a mayor, la creación del árbol binario se puede definir de forma recursiva tal como se muestra en la Figura B.1.

Algoritmo de creación de un árbol binario Alg_CAB
Entrada: Lista de valores ordenados L.
Salida: Nodo raíz del árbol creado T.
Si Longitud(L)=1 entonces /*Un único elemento*/
Crear un nuevo nodo N con V=Obtener_Elemento(L) y los punteros de los subárboles apuntando a un árbol vacío.
sino
Obtener el nodo cuyo valor es el central de la lista de valores (la mediana): v_med
Particionar la lista L en dos sublistas L₁ y L₂ de tal forma que L₁ contiene todos los elementos menores o iguales a v_med y L₂ los estrictamente mayores.
Crear un nuevo nodo N con V=v_med. El puntero izquierdo L apuntará al árbol devuelto en la llamada a la función Alg_CAB(L₁) y el derecho R ídem Alg_CAB(L₂).
FinSi
Devolver N.

Figure B.1: Algoritmo de creación de un árbol binario.

Si tenemos los siguientes valores: 3, 5, 10, 15, 16, 20, 22, 23, 30, el resultado de la creación de este árbol se puede observar en la Figura B.2. Los valores almacenados en los nodos internos permiten guiar la búsqueda hacia los valores en las hojas. Todos los valores en el subárbol izquierdo de un determinado nodo contienen valores menores o iguales que el valor almacenado en dicho nodo, mientras que en el subárbol derecho estos valores son mayores.

Figure B.2: Árbol binario creado indicando el nodo de partición.

El método de consulta parte de un determinado rango a buscar [x₁:x₂] y devuelve los puntos del árbol que se encuentran dentro de ese rango. El método se divide en dos fases: primero encontrar el nodo de partición para, a continuación, ir explorando a partir de este nodo e ir devolviendo los valores dentro del rango. Este nodo de partición (v_part) es aquel nodo del árbol cuyo valor es mayor que x₁ y menor que x₂, es decir se encuentra dentro del rango a buscar, y que además tiene menor profundidad (más próximo a la raíz). En la Figura B.2 se muestra el nodo de partición para un rango de búsqueda de [4:15]. La Figura B.3 muestra el resultado de buscar un determinado rango en el árbol binario. Primero encontramos el nodo de partición. Después buscamos por el hijo izquierdo, quedándonos con los subárboles derechos que se encuentren dentro del rango, mientras que cuando buscamos por el hijo derecho nos quedamos con los subárboles izquierdos. En la Figura B.5 se detalla el método de consulta de rango.

Figure B.3: Obtención de los puntos dentro de un rango.

La función Devolver_Subárbol() devuelve una lista con todos los puntos que pertenecen al árbol pasado como parámetro a la función.

La creación de este árbol se puede realizar con una complejidad temporal de °(nlog n) y una espacial de °(n). En cuanto a la complejidad de la consulta, siendo k el número de puntos devueltos se tiene una complejidad temporal de °(k+log n).

B.2 Árboles de rango

Este tipo de árbol permite obtener, de manera eficiente, los puntos dentro de un espacio bidimensional cuyas coordenadas se encuentran dentro de un determinado rango. Si P es el conjunto de puntos totales, una consulta de rango ([x₁:x₂]×[y₁:y₂]) en dos dimensiones sobre P devolverá todos aquellos puntos que estén situados dentro del rectángulo definido por el rango de consulta. Un punto p=(p_x,p_y) está situado dentro de dicho rectángulo si se cumple que:

p_x Î [x₁:x₂] y p_y Î [y₁:y₂]

Una consulta de este tipo se puede dividir en dos subconsultas, una para las coordenadas x y otra para las y. El árbol de rango es un árbol binario en el cual se han utilizado las coordenadas x de los puntos para su construcción. La consulta principal se realiza sobre estas coordenadas. Asociado a cada nodo de este árbol principal tenemos un árbol binario como el descrito en la anterior sección pero construido a partir de las coordenadas y de los puntos hijos de este nodo. La construcción de esta estructura es idéntica a la del árbol binario, excepto que el primer paso del algoritmo debe ser construir un árbol binario, asociado al nodo en cuestión, con las coordenadas y de los puntos (ver Figura B.4).

Figure B.4: Árbol de rango con el árbol binario asociado.

En cuanto a la consulta, el algoritmo también es muy similar al descrito para consulta en árboles binarios. Se realiza una consulta sobre las coordenadas x del árbol, y cuando se llamaba a la función Devolver_Subárbol ahora se debe realizar una consulta al árbol asociado con el rango de las y.

Si tenemos un conjunto P de n puntos, la creación de un árbol de rango se puede realizar con una complejidad temporal de °(nlog n) y una espacial de °(nlog n). En cuanto a la complejidad de la consulta, siendo k el número de puntos devueltos se tiene una complejidad temporal de °(k+log² n).

Algoritmo de consulta en un árbol binario Alg_CoAB
Entrada: Un árbol T y un rango de búsqueda [x₁:x₂]
Salida: Lista de puntos del árbol que se encuentran dentro del rango.
Crear una lista vacía Lista
v_part=raíz( T)
x_part=valor(v_part)
mientras v_part no es hoja y (x₂ £ x_part o x₁ > x_part) hacer
Si x₂ £ x_part entonces
    v_part=Hijo_izquierdo(v_part)
sino
    v_part=Hijo_derecho(v_part)
FinSi
x_part=valor(v_part)
FinMientras

Si v_part es hoja entonces
Si (x_part ³ x₁ y x_part £ x₂) entonces Insertar x_part en Lista FinSi
sino
/* Primero se sigue el camino de la izquierda */
v=v_part
v=Hijo_izquierdo(v)
mientras v no es hoja hacer
    x_v=valor(v)
    Si x₁ £ x_v entonces
     Concatenar (Lista, Devolver_Subárbol(Hijo_derecho(v)))
     v=Hijo_izquierdo(v)
    sino
     v=Hijo_derecho(v)
    FinSi
FinMientras
/* El nodo hoja también debe de ser chequeado */
Si (x_v ³ x₁ y x_v £ x₂) entonces Insertar x_v en Lista FinSi
/* Ahora se continúa por la derecha */
v=v_part
v=Hijo_derecho(v)
mientras v no es hoja hacer
    x_v=valor(v)
    Si x₂ ³ x_v entonces
     Concatenar (Lista, Devolver_Subárbol(Hijo_izquierdo(v)))
     v=Hijo_derecho(v)
    sino
     v=Hijo_izquierdo(v)
   FinSi
FinMientras
/* El nodo hoja también debe de ser chequeado */
Si (x_v ³ x₁ y x_v £ x₂) entonces Insertar x_v en Lista FinSi
FinSi
Devolver Lista

Figure B.5: Algoritmo de consulta de un árbol binario.