Árbol-R

Árbol-R
Ejemplo simple de un Árbol-R para rectángulos 2D.

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".

La estructura de datos divide el espacio de forma jerárquica en conjuntos, posiblemente superpuestos.

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 en el caso peor.

Algoritmo

Plantilla:Sec - incompleta

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

Enlaces externos


Wikimedia foundation. 2010.

Игры ⚽ Нужна курсовая?

Mira otros diccionarios:

  • árbol — (Del lat. arbor, ŏris). 1. m. Planta perenne, de tronco leñoso y elevado, que se ramifica a cierta altura del suelo. 2. Pieza de hierro en la parte superior del husillo de la prensa de imprimir. 3. En los órganos, eje que, movido a voluntad del… …   Diccionario de la lengua española

  • árbol — sustantivo masculino 1. Planta leñosa de tronco elevado que se ramifica a cierta altura del suelo: Han plantado muchos árboles. Este árbol da una sombra deliciosa. árbol del Paraíso Árbol de tronco gris, hojas blanquecinas, estrechas, y flores… …   Diccionario Salamanca de la Lengua Española

  • Arbol — is programming language, primarily developed to serve for Genetic Programming experiments. It is functional programming language inspired by the ideas of other small and esoteric languages. An Arbol program looks like: // Simple I/O ((Z a)b) =… …   Wikipedia

  • Arbol.bb — (Ассемини,Италия) Категория отеля: Адрес: Via Belli 6, 09032 Ассемини, Италия …   Каталог отелей

  • árbol — 1. (en anatomía) estructura anatómica con ramas que se extienden hacia fuera como las de un árbol, como el árbol bronquial. 2. patrón de búsqueda de información en una base de datos de un ordenador, siguiendo una serie de opciones ramificadas a… …   Diccionario médico

  • Árbol — (Del lat. arbor.) ► sustantivo masculino 1 BOTÁNICA Planta de tronco leñoso que se ramifica a mayor o menor altura del suelo, formando una copa. 2 NÁUTICA Madero redondo o cilíndrico fijo en una embarcación que sostiene las vergas a las que se… …   Enciclopedia Universal

  • Árbol-B — Ejemplo de árbol B. En las ciencias de la computación, los árboles B o B árboles son estructuras de datos de árbol que se encuentran comúnmente en las implementaciones de bases de datos y sistemas de archivos. Son árboles binarios de búsqueda en… …   Wikipedia Español

  • Árbol — Para otros usos de este término, véase Árbol (desambiguación). Un roble en Dinamarca …   Wikipedia Español

  • Árbol kd — Un árbol kd tridimensional. La primera división (rojo) corta la celda raíz (blanco) en dos subceldas, que son divididas a su vez (verde) en dos subceldas. Finalmente, cada una de esas cuatro es dividida (azul) en dos subceldas. Dado que no hay… …   Wikipedia Español

  • Árbol 2-3 — Este artículo o sección sobre informática necesita ser wikificado con un formato acorde a las convenciones de estilo. Por favor, edítalo para que las cumpla. Mientras tanto, no elimines este aviso puesto el 2 de febrero de 2009. También puedes… …   Wikipedia Español

  • Árbol AA — En informática un árbol AA es un tipo de árbol binario de búsqueda auto balanceable utilizado para almacenar y recuperar información ordenada de manera eficiente. Los árboles AA reciben el nombre de su inventor, Arne Andersson. Los árboles AA son …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”