Los árboles-R o R-árboles son estructuras de datos de tipo árbol similares a los árboles-B, con la diferencia de que se utilizan para métodos de acceso espacial, es decir, para indexar información multidimensional; por ejemplo, las coordenadas (x, y) de un lugar geográfico. Un problema con aplicación práctica en el mundo real podría ser: "Encontrar todos los museos en un radio de dos kilómetros alrededor de la posición actual".
Cada nodo de un árbol-R tiene un número variable de entradas (hasta un máximo predefinido). Cada entrada de un nodo interno almacena dos datos: una forma de identificar a un nodo hijo y el conjunto límite de todas las entradas de ese nodo hijo.
Los algoritmos de inserción y borrado utilizan los conjuntos límite de los nodos para asegurar que elementos cercanos están localizados en la misma hoja (en particular, un nuevo elemento será insertado en la hoja que requiera el menor aumento del conjunto límite). Cada entrada de una hoja contiene dos datos: una forma de identificar el elemento actual (que, alternativamente, podría estar directamente en el nodo) y el conjunto límite de ese elemento.
De forma similar, los algoritmos de búsqueda utilizan los conjuntos límite para decidir en qué nodo buscar. De este modo, la mayoría de los nodos del árbol nunca son examinados durante una búsqueda. Esto hace que este tipo de árboles (como los árboles-B) sean idóneos para el trabajo con bases de datos.
Se pueden utilizar distintos algoritmos para dividir nodos cuando estos crecen demasiado, resultando subtipos de árbol-R cuadráticos y lineales.
Los árboles-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 publicó un nuevo algoritmo que define el árbol R-de prioridad, que parece ser tan eficiente como los métodos actuales más eficientes y, al mismo tiempo, óptimo para el peor caso.
Referencias
Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching, Proc. ACM SIGMOD International Conference on Management of Data, ISBN 0-89791-128-8
Lars Arge, Mark de Berg, Herman J.Haverkort, Ke Yi: The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree, Proc. ACM SIGMOD international conference on Management of data, ISBN 1-58113-859-8
Datos:Q1198051
Multimedia:R-tree
Diciembre 23, 2021
Árbol, árboles, árboles, estructuras, datos, tipo, árbol, similares, árboles, diferencia, utilizan, para, métodos, acceso, espacial, decir, para, indexar, información, multidimensional, ejemplo, coordenadas, lugar, geográfico, problema, aplicación, práctica, m. 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 Ejemplo simple de un Arbol R para rectangulos 2D 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 EditarAntonin Guttman R Trees A Dynamic Index Structure for Spatial Searching Proc ACM SIGMOD International Conference on Management of Data ISBN 0 89791 128 8 Lars Arge Mark de Berg Herman J Haverkort Ke Yi The Priority R Tree A Practically Efficient and Worst Case Optimal R Tree Proc ACM SIGMOD international conference on Management of data ISBN 1 58113 859 8 Datos Q1198051 Multimedia R tree Obtenido de https es wikipedia org w index php title Arbol R amp oldid 130713620, wikipedia, wiki, leyendo, leer, libro, biblioteca,
