Dark Mode

Ir al contenido

Arbol-R

De Wikipedia, la enciclopedia libre
Ejemplo simple de un Arbol-R para rectangulos 2D.

Los arboles-R o R-arboles son estructuras de datos de tipo arbol similares a los arboles-B, con la diferencia de que se utilizan para metodos de acceso espacial, es decir, para indexar informacion multidimensional; por ejemplo, las coordenadas (x, y) de un lugar geografico. Un problema con aplicacion practica en el mundo real podria ser: "Encontrar todos los museos en un radio de dos kilometros alrededor de la posicion actual".

La estructura de datos divide el espacio de forma jerarquica en conjuntos, posiblemente superpuestos.

Cada nodo de un arbol-R tiene un numero variable de entradas (hasta un maximo predefinido). Cada entrada de un nodo interno almacena dos datos: una forma de identificar a un nodo hijo y el conjunto limite de todas las entradas de ese nodo hijo.

Los algoritmos de insercion y borrado utilizan los conjuntos limite de los nodos para asegurar que elementos cercanos estan localizados en la misma hoja (en particular, un nuevo elemento sera insertado en la hoja que requiera el menor aumento del conjunto limite). Cada entrada de una hoja contiene dos datos: una forma de identificar el elemento actual (que, alternativamente, podria estar directamente en el nodo) y el conjunto limite de ese elemento.

De forma similar, los algoritmos de busqueda utilizan los conjuntos limite para decidir en que nodo buscar. De este modo, la mayoria de los nodos del arbol nunca son examinados durante una busqueda. Esto hace que este tipo de arboles (como los arboles-B) sean idoneos para el trabajo con bases de datos.

Se pueden utilizar distintos algoritmos para dividir nodos cuando estos crecen demasiado, resultando subtipos de arbol-R cuadraticos y lineales.

Los arboles-R no garantizan un buen rendimiento en el peor caso, pero en general se comportan bien con datos del mundo real. Sin embargo, recientemente, en 2004, se publico un nuevo algoritmo que define el arbol R-de prioridad, que parece ser tan eficiente como los metodos actuales mas eficientes y, al mismo tiempo, optimo para el peor caso.


Referencias

[editar]
Control de autoridades