Árbol-R

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

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

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.