En informática , un árbol de segmentos, también conocido como árbol de estadísticas, es una estructura de datos de árbol que se utiliza para almacenar información sobre intervalos o segmentos. Permite consultar cuál de los segmentos almacenados contiene un punto determinado. Es, en principio, una estructura estática; es decir, es una estructura que no se puede modificar una vez construida. Una estructura de datos similar es el árbol de intervalos .
Un árbol de segmentos para un conjunto I de n intervalos usa almacenamiento O ( n log n ) y se puede construir en 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 mayor dimensión .
Descripción de la estructura
Esta sección describe la estructura de un árbol de segmentos en un espacio unidimensional.
Sea S un conjunto de intervalos o segmentos. Sea p 1 , p 2 , ..., p m la lista de puntos finales de intervalo distintos, ordenados de izquierda a derecha. Considere la división de la línea real inducida por esos puntos. Las regiones de esta partición se denominan intervalos elementales . Así, 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 únicos 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:
- T es un árbol binario .
- Sus hojas corresponden a los intervalos elementales inducidos por los extremos en I , de forma ordenada: la hoja más a la izquierda corresponde al intervalo más a la izquierda, y así sucesivamente. El intervalo elemental correspondiente a una hoja v se denota Int ( v ).
- Los nodos internos de T corresponden a intervalos que son la unión de intervalos elementales: el Int intervalo ( N ) que corresponde al nodo N es la unión de los intervalos correspondientes a las hojas del árbol con raíz en N . Eso implica que Int ( N ) es la unión de los intervalos de sus dos hijos.
- Cada nodo u hoja v en T almacena el intervalo Int ( v ) y un conjunto de intervalos, en alguna estructura de datos. Este subconjunto canónico del nodo v contiene los intervalos [ x , x ′ ] de I tales que [ x , x ′ ] contiene Int ( v ) y no contiene Int (parent ( v )). Es decir, cada nodo en T almacena los segmentos que abarcan su intervalo, pero no el intervalo de su padre. [3]
Requisitos de almacenamiento
Esta sección analiza el costo de almacenamiento de un árbol de segmentos en un espacio unidimensional.
Un árbol de segmentos T en un conjunto I de n intervalos usa 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 v dado . Suponga 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 ). Tenga en cuenta 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 cuando se pasa de cualquier nivel al que está por encima mediante la combinación de pares. de segmentos adyacentes. Ahora bien, padre ( v 2 ) = padre ( v 1 ), o el primero está a la derecha del último (los bordes del á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, Int (padre ( v 2 )) 's punto más a la izquierda está a la derecha de Int (padre ( v 1 ))' s punto más a la derecha, y por lo tanto también a la derecha de Int ( v 1 ) 's más a la derecha punto. En ambos casos, Int (parent ( v 2 )) comienza en el punto más a la izquierda de Int ( v 1 ) o hacia la derecha . Un razonamiento similar muestra que Int (parent ( v 2 )) termina en el punto más a la derecha de Int ( v 3 ) o hacia la izquierda . Int (parent ( v 2 )) debe estar contenido en [ x , x ′ ]; por lo tanto, [ x , x ′ ] no se almacenará en v 2 .
- El conjunto I tiene como máximo 4 n + 1 intervalos elementales. Debido a que T es un árbol binario balanceado con un máximo de 4 n + 1 hojas, su altura es O (log n ). Dado que cualquier intervalo se almacena como máximo dos veces a una profundidad dada del árbol, la cantidad total de almacenamiento es O ( n log n ). [4]
Construcción
Esta sección describe la construcción de un árbol de segmentos en un espacio unidimensional.
Un árbol de segmentos del conjunto de segmentos I se puede construir de la siguiente manera. Primero, se ordenan los puntos finales de los intervalos en I. Los intervalos elementales se obtienen de eso. 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 de 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: [5]
- Si Int ( T ) está contenido en X , almacene X en T y termine.
- Demás:
- Si X interseca el intervalo del hijo izquierdo de T , inserte X en ese hijo, de forma recursiva.
- Si X interseca el intervalo del hijo derecho de T , inserte X en ese hijo, de forma recursiva.
La operación completa de la construcción toma O ( n log n ) tiempo, n es el número de segmentos en I .
- La clasificación de los puntos finales toma O ( n log n ). La construcción de un árbol binario equilibrado a partir de los puntos finales ordenados requiere un tiempo lineal en n .
- La inserción de un intervalo X = [ x , x ′ ] en el árbol, cuesta O (log n ).
Visitar cada nodo lleva un tiempo constante (asumiendo que los subconjuntos canónicos se almacenan en una estructura de datos simple como una lista vinculada ). Cuando visitamos nodo v , que cualquiera de las tiendas X en v , o int ( v ) contiene un punto final de la 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 niveles O (log n ), el costo total de la inserción es O (log n ). [1]
Consulta
Esta sección describe la operación de consulta de un árbol de segmentos en un espacio unidimensional.
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 .
Declarado formalmente; dado un nodo (subárbol) v y un punto de consulta q x , la consulta se puede realizar utilizando el siguiente algoritmo:
- Informe todos los intervalos en I ( v ).
- Si v no es una hoja:
- Si q x está en Int (hijo izquierdo de v ) entonces
- Realice una consulta en el hijo izquierdo de v .
- Si q x está en Int (hijo derecho de v ) entonces
- Realice una consulta en el hijo derecho de v .
- Si q x está en Int (hijo izquierdo de v ) entonces
En un árbol de segmentos que contiene n intervalos, los 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 O (log n ) nodos en total. Por otro lado, 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. [4]
Generalización para dimensiones superiores
El árbol de segmentos se puede generalizar a espacios de mayor dimensión, 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 almacenamiento O ( n log d n ) y responde consultas en O (log d n ).
El uso de cascada fraccional reduce el tiempo de consulta limitado por un factor logarítmico. El uso del árbol de intervalo en el nivel más profundo de estructuras asociadas reduce el almacenamiento limitado por un factor logarítmico. [6]
Notas
Una consulta que solicita todos los intervalos que contienen un punto determinado se suele denominar consulta de puñalada . [7]
El árbol de segmento es menos eficiente que el árbol de intervalo para consultas de rango en una dimensión, debido a su mayor requerimiento de almacenamiento: O ( n log n ) contra O ( n ) del árbol de intervalo. 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 )]), estructuras de datos óptimas [ ¿cuál? ] existen 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 determinado.
Otra ventaja del árbol de segmentos es que se puede adaptar fácilmente para contar consultas; es decir, informar el número de segmentos que contienen un punto determinado, en lugar de informar los segmentos en sí. En lugar de almacenar los intervalos en los subconjuntos canónicos, simplemente puede almacenar el número de ellos. Dicho árbol de segmentos utiliza almacenamiento lineal y requiere un tiempo de consulta O (log n ), por lo que es óptimo. [8]
No existen versiones de mayor dimensión 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 se pueden utilizar como estructura asociada de árboles de segmentos. [6]
Historia
El árbol de segmentos fue inventado por Jon Bentley en 1977; en "Soluciones a los problemas del rectángulo de Klee". [7]
Referencias
- ↑ a b ( de Berg et al. 2000 , p. 227)
- ↑ ( de Berg et al. 2000 , p. 224)
- ^ ( de Berg et al. 2000 , págs. 225-226)
- ↑ a b ( de Berg et al. 2000 , p. 226)
- ^ ( de Berg et al. 2000 , págs. 226-227)
- ↑ a b ( de Berg et al. 2000 , p. 230)
- ↑ a b c ( de Berg et al. 2000 , p. 229)
- ^ ( de Berg et al. 2000 , págs. 229-230)
Fuentes citadas
- de Berg, Mark; van Kreveld, Marc; Overmars, Mark; Schwarzkopf, Otfried (2000). "Más estructuras de datos geométricas". Geometría computacional: algoritmos y aplicaciones (2ª ed.). Springer-Verlag Berlin Heidelberg Nueva York. doi : 10.1007 / 978-3-540-77974-2 . ISBN 3-540-65620-0.
- http://www.cs.nthu.edu.tw/~wkhon/ds/ds10/tutorial/tutorial6.pdf
enlaces externos
- Árbol de segmentos: algoritmos CP