Árbol R de prioridad

El árbol R priorizado es una alternativa asintóticamente óptima en el peor de los casos al árbol R espacial . 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, ya que define el volumen delimitador N-dimensional de un objeto dado (llamado Rectángulos Delimitadores Mínimos – RDM) 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 la superposición en sus nodos de prioridad. Las subramas se recorren (y construyen) verificando si el valor mínimo de la primera dimensión de la consulta es mayor que el valor de las subramas. Esto permite acceder a una indexación rápida mediante el valor de la primera dimensión del cuadro delimitador.

Arge et al. escriben que el árbol de prioridad siempre responde a las consultas de ventana con ${\displaystyle O\left(\left({\frac {N}{B}}\right)^{1-{\frac {1}{d}}}+{\frac {T}{B}}\right)}$E/S, donde N es el número de (hiper)rectángulos d-dimensionales almacenados en el árbol R, B es el tamaño del bloque de disco y T es el tamaño de salida.

En el caso de${\displaystyle d=2}$El rectángulo está representado por${\displaystyle \,((x_{min},y_{min}),(x_{max},y_{max}))}$y el MBR por lo tanto cuatro esquinas${\displaystyle \,(x_{min},y_{min},x_{max},y_{max})}$.

• Jerarquía de volúmenes delimitadores
• Árbol B
• Árbol R