El árbol R prioritario es una alternativa asintóticamente óptima en el peor de los casos al árbol espacial R-tree . Fue propuesto por primera vez por Arge, De Berg, Haverkort y Yi, K. en un artículo de 2004. [1] El árbol R priorizado es esencialmente un híbrido entre un árbol k -dimensional y un árbol R en el sentido de que define el volumen delimitador N-dimensional de un objeto dado (llamado Rectángulos Delimitadores Mínimos - MBR) como un punto en N-dimensiones, representado por el par ordenado de los rectángulos. El término priorizado proviene de la introducción de cuatro hojas de prioridad que representan los valores más extremos de cada dimensión, incluidos en cada rama del árbol. Antes de responder a una consulta de ventana recorriendo las subramas, el árbol R priorizado primero verifica si hay superposición en sus nodos de prioridad. Las subramas se recorren (y construyen) verificando si el valor más bajo de la primera dimensión de la consulta está por encima del valor de las subramas. Esto da acceso a una indexación rápida por el valor de la primera dimensión del cuadro delimitador.
Arge et al. escribe que el árbol de prioridad siempre responde a las consultas de ventana con E/S, donde N es el número de rectángulos (hiper) de dimensión d almacenados en el árbol R, B es el tamaño del bloque del disco y T es el tamaño de salida.
En el caso del rectángulo se representa mediante y el MBR por tanto cuatro esquinas .
