En informática , el árbol de segmentos es una estructura de datos que se utiliza para almacenar información sobre intervalos o segmentos. Permite consultar cuáles de los segmentos almacenados contienen un punto determinado. Una estructura de datos similar es el árbol de intervalos .
Un árbol de segmentos para un conjunto I de n intervalos utiliza un almacenamiento O ( n log n ) y puede construirse en un tiempo O ( n log n ). Los árboles de segmentos admiten la búsqueda de todos los intervalos que contienen un punto de consulta en el tiempo O (log n + k ), siendo k el número de intervalos o segmentos recuperados. [1]
Las aplicaciones del árbol de segmentos se encuentran en las áreas de geometría computacional , sistemas de información geográfica y aprendizaje automático .
El árbol de segmentos se puede generalizar a espacios de dimensiones superiores .
Sea I un conjunto de intervalos o segmentos. Sea p 1 , p 2 , ..., p m la lista de extremos de intervalos distintos, ordenados de izquierda a derecha. Considérese la partición de la recta real inducida por esos puntos. Las regiones de esta partición se denominan intervalos elementales . Por tanto, los intervalos elementales son, de izquierda a derecha:
Es decir, la lista de intervalos elementales consta de intervalos abiertos entre dos puntos finales consecutivos p i y p i +1 , alternados con intervalos cerrados que constan de un único punto final. Los puntos finales se tratan a sí mismos como intervalos porque la respuesta a una consulta no es necesariamente la misma en el interior de un intervalo elemental y sus puntos finales. [2]
Dado un conjunto I de intervalos o segmentos, un árbol de segmentos T para I se estructura de la siguiente manera:
Un árbol de segmentos a partir del conjunto de segmentos I se puede construir de la siguiente manera. Primero se ordenan los puntos finales de los intervalos en I. A partir de ahí se obtienen los intervalos elementales. Luego se construye un árbol binario balanceado sobre los intervalos elementales y para cada nodo v se determina el intervalo Int( v ) que representa. Queda por calcular los subconjuntos canónicos para los nodos. Para lograr esto, los intervalos en I se insertan uno por uno en el árbol de segmentos. Se puede insertar un intervalo X = [ x , x′ ] en un subárbol con raíz en T , utilizando el siguiente procedimiento: [4]
La operación de construcción completa toma un tiempo O ( n log n ), siendo n el número de segmentos en I .
Visitar cada nodo lleva un tiempo constante (suponiendo que los subconjuntos canónicos se almacenan en una estructura de datos simple como una lista enlazada ). Cuando visitamos el nodo v , almacenamos X en v o Int( v ) contiene un punto final de X. Como se demostró anteriormente, un intervalo se almacena como máximo dos veces en cada nivel del árbol. También hay como máximo un nodo en cada nivel cuyo intervalo correspondiente contiene x , y un nodo cuyo intervalo contiene x′ . Por lo tanto, se visitan como máximo cuatro nodos por nivel. Dado que hay O (log n ) niveles, el costo total de la inserción es O (log n ). [1]
Una consulta para un árbol de segmentos recibe un punto q x (debe ser una de las hojas del árbol) y recupera una lista de todos los segmentos almacenados que contienen el punto q x .
Formalmente establecido, dado un nodo (subárbol) v y un punto de consulta q x , la consulta se puede realizar utilizando el siguiente algoritmo:
En un árbol de segmentos que contiene n intervalos, aquellos que contienen un punto de consulta determinado se pueden informar en tiempo O (log n + k ), donde k es el número de intervalos informados.
El algoritmo de consulta visita un nodo por nivel del árbol, por lo que en total hay O (log n ). Por otra parte, en un nodo v , los segmentos en I se informan en O (1 + k v ) tiempo, donde k v es el número de intervalos en el nodo v , informados. La suma de todos los k v para todos los nodos v visitados, es k , el número de segmentos informados. [5]
Un árbol de segmentos T en un conjunto I de n intervalos utiliza almacenamiento O ( n log n ).
Lema — Cualquier intervalo [ x , x′ ] de I se almacena en el conjunto canónico para como máximo dos nodos a la misma profundidad.
Sean v 1 , v 2 , v 3 los tres nodos a la misma profundidad, numerados de izquierda a derecha; y sea p( v ) el nodo padre de cualquier nodo dado v . Supongamos que [ x , x′ ] se almacena en v 1 y v 3 . Esto significa que [ x , x′ ] abarca todo el intervalo desde el extremo izquierdo de Int( v 1 ) hasta el extremo derecho de Int( v 3 ). Nótese que todos los segmentos en un nivel particular no se superponen y están ordenados de izquierda a derecha: esto es cierto por construcción para el nivel que contiene las hojas, y la propiedad no se pierde al pasar de cualquier nivel al superior combinando pares de segmentos adyacentes. Ahora, o padre( v 2 ) = padre( v 1 ), o el primero está a la derecha del segundo (los bordes en el árbol no se cruzan). En el primer caso, el punto más a la izquierda de Int(parent( v 2 )) es el mismo que el punto más a la izquierda de Int( v 1 ); en el segundo caso, el punto más a la izquierda de Int(parent( v 2 )) está a la derecha del punto más a la derecha de Int(parent( v 1 )) y, por lo tanto, también a la derecha del punto más a la derecha de Int( v 1 ). En ambos casos, Int(parent( v 2 )) comienza en o a la derecha del punto más a la izquierda de Int( v 1 ). Un razonamiento similar muestra que Int(parent( v 2 )) termina en o a la izquierda del punto más a la derecha de Int( v 3 ). Por lo tanto, Int(parent( v 2 )) debe estar contenido en [ x , x′ ]; por lo tanto, [ x , x′ ] no se almacenará en v 2 .
El árbol de segmentos se puede generalizar a espacios de dimensiones superiores, en forma de árboles de segmentos de varios niveles. En versiones de dimensiones superiores, el árbol de segmentos almacena una colección de (hiper)rectángulos paralelos a los ejes y puede recuperar los rectángulos que contienen un punto de consulta determinado. La estructura utiliza un almacenamiento O ( n log d n ) y responde a las consultas en tiempo O (log d n ).
El uso de cascada fraccionaria reduce el tiempo de consulta limitado por un factor logarítmico. El uso del árbol de intervalos en el nivel más profundo de las estructuras asociadas reduce el límite de almacenamiento por un factor logarítmico. [6]
Una consulta que solicita todos los intervalos que contienen un punto determinado a menudo se denomina consulta de punción . [7]
El árbol de segmentos es menos eficiente que el árbol de intervalos para consultas de rangos en una dimensión, debido a su mayor requerimiento de almacenamiento: O ( n log n ) contra el O( n ) del árbol de intervalos. La importancia del árbol de segmentos es que los segmentos dentro del subconjunto canónico de cada nodo se pueden almacenar de cualquier manera arbitraria. [7]
Para n intervalos cuyos puntos finales están en un rango de números enteros pequeños (por ejemplo, en el rango [1,..., O ( n )]), existen estructuras de datos óptimas [ ¿cuáles? ] con un tiempo de preprocesamiento lineal y un tiempo de consulta O (1 + k ) para informar todos los k intervalos que contienen un punto de consulta dado.
Otra ventaja del árbol de segmentos es que se puede adaptar fácilmente a consultas de conteo; es decir, para informar el número de segmentos que contienen un punto dado, en lugar de informar los segmentos en sí. En lugar de almacenar los intervalos en los subconjuntos canónicos, puede simplemente almacenar el número de ellos. Un árbol de segmentos de este tipo utiliza almacenamiento lineal y requiere un tiempo de consulta de O (log n ), por lo que es óptimo. [8]
No existen versiones de dimensiones superiores del árbol de intervalos y del árbol de búsqueda de prioridades ; es decir, no hay una extensión clara de estas estructuras que resuelva el problema análogo en dimensiones superiores. Pero las estructuras pueden usarse como estructura asociada de árboles de segmentos. [6]
El árbol de segmentos fue inventado por Jon Bentley en 1977; en "Soluciones a los problemas del rectángulo de Klee". [7]
![{\displaystyle (-\infty ,p_{1}),[p_{1},p_{1}],(p_{1},p_{2}),[p_{2},p_{2}],\puntos ,(p_{m-1},p_{m}),[p_{m},p_{m}],(p_{m},+\infty )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d7d38ca3ad16c39bc9f67a6e0601c8e82ff59358)