Árbol de intervalo

En ciencia de la computación, un árbol de intervalo es una árbol ordenado para mantener intervalos. En concreto, permite encontrar de manera eficiente todos los intervalos que se solapan con cualquier otro intervalo o punto dado. A menudo se utiliza para las consultas de ventanas, por ejemplo, para encontrar todos los caminos en un mapa computarizado dentro de una ventana rectangular, o para encontrar todos los elementos visibles dentro de una escena tridimensional. Una estructura de datos similar es el árbol de segmento.La solución trivial es visitar cada intervalo y probar si se cruza el punto o intervalo dado, que requiere Θ(n) tiempo, donde n es el número de intervalos en la colección. Dado que una consulta puede devolver todos los intervalos, por ejemplo, si la consulta es un gran intervalo de intersección de todos los intervalos de la colección, esto es asintóticamente óptimo; Sin embargo, podemos mejorarlo al considerar algoritmos producto-sensible, donde el tiempo de ejecución se expresa en términos de m, el número de intervalos producidos por la consulta. Los Árboles de intervalo son dinámicos, es decir, que permiten la inserción y la supresión de intervalos. Obtienen un tiempo de consulta de O(log n), mientras que el tiempo de preprocesamiento para construir la estructura de datos es O(n log n) (pero el consumo de espacio es O(n)). Si los puntos extremos de los intervalos están dentro de un rango entero pequeño (por ejemplo, en el intervalo [1, ..., O (n)]), las estructuras de datos más rápidas existen con el tiempo de preprocesamiento O (n) y el tiempo de consulta O(1+m) para informar m intervalos que contienen un punto de consulta dada.