árbol de intervalos

Estructura de datos de árbol para mantener intervalos.

En informática , un árbol de intervalos es una estructura de datos de árbol para mantener intervalos . Específicamente, permite encontrar de manera eficiente todos los intervalos que se superponen con cualquier intervalo o punto determinado. A menudo se utiliza para consultas de ventanas, ^[1] por ejemplo, para encontrar todas las carreteras en un mapa computarizado dentro de una ventana gráfica rectangular, o para encontrar todos los elementos visibles dentro de una escena tridimensional. Una estructura de datos similar es el árbol de segmentos .

La solución trivial es visitar cada intervalo y probar si se cruza con el punto o intervalo dado, lo que requiere tiempo, donde está 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 intervalo grande que cruza todos los intervalos de la colección, esto es asintóticamente óptimo ; sin embargo, podemos hacerlo mejor si consideramos algoritmos sensibles a la salida , donde el tiempo de ejecución se expresa en términos de , el número de intervalos producidos por la consulta. Los árboles de intervalos tienen un tiempo de consulta y un tiempo de creación inicial de , al tiempo que limitan el consumo de memoria a . Después de la creación, los árboles de intervalos pueden ser dinámicos, lo que permite la inserción y eliminación eficiente de un intervalo en el tiempo. Si los puntos finales de los intervalos están dentro de un rango entero pequeño ( por ejemplo , en el rango ), existen estructuras de datos más rápidas y, de hecho, óptimas ^{[2] [3]} con tiempo de preprocesamiento y tiempo de consulta para informar intervalos que contienen un punto de consulta determinado (consulte ^{[ 2]} para uno muy simple). ${\displaystyle O(n)}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle O(\log n+m)}$ ${\displaystyle O(n\log n)}$ ${\displaystyle O(n)}$ ${\displaystyle O(\log n)}$ ${\displaystyle [1,\ldots ,O(n)]}$ ${\displaystyle O(n)}$ ${\displaystyle O(1+m)}$ ${\displaystyle m}$

Enfoque ingenuo

En un caso simple, los intervalos no se superponen y se pueden insertar en un árbol de búsqueda binario simple y consultar a tiempo. Sin embargo, con intervalos que se superponen arbitrariamente, no hay forma de comparar dos intervalos para insertarlos en el árbol, ya que los ordenamientos ordenados por los puntos iniciales o finales pueden ser diferentes. Un enfoque ingenuo podría ser construir dos árboles paralelos, uno ordenado por el punto inicial y otro ordenado por el punto final de cada intervalo. Esto permite descartar la mitad de cada árbol a tiempo, pero los resultados deben fusionarse, lo que requiere tiempo. Esto nos da consultas en , que no es mejor que la fuerza bruta. ${\displaystyle O(\log n)}$ ${\displaystyle O(\log n)}$ ${\displaystyle O(n)}$ ${\displaystyle O(n+\log n)=O(n)}$

Los árboles de intervalos resuelven este problema. Este artículo describe dos diseños alternativos para un árbol de intervalo, denominado árbol de intervalo centrado y árbol aumentado .

Árbol de intervalo centrado

Las consultas requieren tiempo, siendo el número total de intervalos y el número de resultados informados. La construcción requiere tiempo y el almacenamiento requiere espacio. ${\displaystyle O(\log n+m)}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle O(n\log n)}$ ${\displaystyle O(n)}$

Construcción

Dado un conjunto de intervalos en la recta numérica, queremos construir una estructura de datos para que podamos recuperar de manera eficiente todos los intervalos que se superponen a otro intervalo o punto. ${\displaystyle n}$

Comenzamos tomando el rango completo de todos los intervalos y dividiéndolos por la mitad (en la práctica, se debe elegir para mantener el árbol relativamente equilibrado). Esto da tres conjuntos de intervalos, aquellos completamente a la izquierda de los cuales llamaremos , aquellos completamente a la derecha de los cuales llamaremos , y aquellos que se superponen a los cuales llamaremos . ${\displaystyle x_{\textrm {center}}}$ ${\displaystyle x_{\textrm {center}}}$ ${\displaystyle x_{\textrm {center}}}$ ${\displaystyle S_{\textrm {left}}}$ ${\displaystyle x_{\textrm {center}}}$ ${\displaystyle S_{\textrm {right}}}$ ${\displaystyle x_{\textrm {center}}}$ ${\displaystyle S_{\textrm {center}}}$

Los intervalos en y se dividen recursivamente de la misma manera hasta que no queden intervalos. ${\displaystyle S_{\textrm {left}}}$ ${\displaystyle S_{\textrm {right}}}$

Los intervalos que se superponen al punto central se almacenan en una estructura de datos separada vinculada al nodo en el árbol de intervalos. Esta estructura de datos consta de dos listas, una que contiene todos los intervalos ordenados por sus puntos iniciales y otra que contiene todos los intervalos ordenados por sus puntos finales. ${\displaystyle S_{\textrm {center}}}$

El resultado es un árbol binario en el que cada nodo almacena:

• Un punto central
• Un puntero a otro nodo que contiene todos los intervalos completamente a la izquierda del punto central.
• Un puntero a otro nodo que contiene todos los intervalos completamente a la derecha del punto central.
• Todos los intervalos que se superponen al punto central ordenados por su punto inicial
• Todos los intervalos que se superponen al punto central ordenados por su punto final

intersección

Dada la estructura de datos construida anteriormente, recibimos consultas que constan de rangos o puntos y devolvemos todos los rangos en el conjunto original que se superponen a esta entrada.

con un punto

La tarea consiste en encontrar todos los intervalos del árbol que se superponen a un punto determinado . El árbol se recorre con un algoritmo recursivo similar al que se usaría para atravesar un árbol binario tradicional, pero con lógica adicional para respaldar la búsqueda de intervalos que se superponen al punto "central" en cada nodo. ${\displaystyle x}$

Para cada nodo del árbol, se compara con el punto medio utilizado en la construcción de nodos anterior. Si es menor que , se considera el conjunto de intervalos más a la izquierda, . Si es mayor que , se considera el conjunto de intervalos más a la derecha, . ${\displaystyle x}$ ${\displaystyle x_{\textrm {center}}}$ ${\displaystyle x}$ ${\displaystyle x_{\textrm {center}}}$ ${\displaystyle S_{\textrm {left}}}$ ${\displaystyle x}$ ${\displaystyle x_{\textrm {center}}}$ ${\displaystyle S_{\textrm {right}}}$

Todos los intervalos que comienzan antes deben superponerse si es menor que . De manera similar, la misma técnica también se aplica al verificar un intervalo determinado. Si un intervalo dado termina en y e y es menor que , todos los intervalos que comienzan antes de y también deben superponerse al intervalo dado. ${\displaystyle S_{\textrm {center}}}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x_{\textrm {center}}}$
${\displaystyle x_{\textrm {center}}}$ ${\displaystyle S_{\textrm {center}}}$

A medida que se procesa cada nodo a medida que recorremos el árbol desde la raíz hasta una hoja, se procesan los rangos en él. Si es menor que , sabemos que todos los intervalos terminan después , o no podrían superponerse . Por lo tanto, sólo necesitamos encontrar aquellos intervalos que comienzan antes . Podemos consultar las listas de los que ya se han construido. Como en este escenario sólo nos importan los inicios de intervalo, podemos consultar la lista ordenada por inicios. Supongamos que encontramos el número más cercano no mayor que en esta lista. Todos los rangos desde el principio de la lista hasta el punto encontrado se superponen porque comienzan antes y terminan después (como sabemos porque se superponen, que es mayor que ). Por lo tanto, podemos simplemente comenzar a enumerar intervalos en la lista hasta que el valor del punto inicial exceda . ${\displaystyle S_{\textrm {center}}}$ ${\displaystyle x}$ ${\displaystyle x_{\textrm {center}}}$ ${\displaystyle S_{\textrm {center}}}$ ${\displaystyle x}$ ${\displaystyle x_{\textrm {center}}}$ ${\displaystyle S_{\textrm {center}}}$ ${\displaystyle x}$ ${\displaystyle S_{\textrm {center}}}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x_{\textrm {center}}}$ ${\displaystyle x}$ ${\displaystyle x}$

Del mismo modo, si es mayor que , sabemos que todos los intervalos deben comenzar antes de , por lo que encontramos aquellos intervalos que terminan después de usar la lista ordenada por terminaciones de intervalo. ${\displaystyle x}$ ${\displaystyle x_{\textrm {center}}}$ ${\displaystyle S_{\textrm {center}}}$ ${\displaystyle x}$ ${\displaystyle x}$

Si coincide exactamente , todos los intervalos se pueden agregar a los resultados sin procesamiento adicional y se puede detener el recorrido del árbol. ${\displaystyle x}$ ${\displaystyle x_{\textrm {center}}}$ ${\displaystyle S_{\textrm {center}}}$

con un intervalo

Para que un intervalo de resultados se cruce con nuestro intervalo de consulta, se debe cumplir una de las siguientes condiciones: ${\displaystyle r}$ ${\displaystyle q}$

• ya sea el punto inicial o final de está en ; o ${\displaystyle r}$ ${\displaystyle q}$
• ${\displaystyle r}$encierra completamente . ${\displaystyle q}$

Primero encontramos todos los intervalos con puntos iniciales y/o finales dentro usando un árbol construido por separado. En el caso unidimensional, podemos utilizar un árbol de búsqueda que contenga todos los puntos inicial y final del conjunto de intervalos, cada uno con un puntero a su intervalo correspondiente. Una búsqueda binaria en el tiempo para el inicio y el final de revela los puntos mínimos y máximos a considerar. Cada punto dentro de este rango hace referencia a un intervalo que se superpone y se agrega a la lista de resultados. Se debe tener cuidado para evitar duplicados, ya que un intervalo puede comenzar y terminar dentro de . Esto se puede hacer usando una bandera binaria en cada intervalo para marcar si se ha agregado o no al conjunto de resultados. ${\displaystyle q}$ ${\displaystyle O(\log n)}$ ${\displaystyle q}$ ${\displaystyle q}$ ${\displaystyle q}$

Finalmente, debemos encontrar intervalos que encierren . Para encontrarlos, elegimos cualquier punto dentro y usamos el algoritmo anterior para encontrar todos los intervalos que cruzan ese punto (nuevamente, teniendo cuidado de eliminar duplicados). ${\displaystyle q}$ ${\displaystyle q}$

Dimensiones superiores

La estructura de datos del árbol de intervalos se puede generalizar a una dimensión superior con tiempo y espacio de consulta y construcción idénticos . ${\displaystyle N}$ ${\displaystyle O(n\log n)}$

Primero, se construye un árbol de rango en dimensiones que permite la recuperación eficiente de todos los intervalos con puntos iniciales y finales dentro de la región de consulta . Una vez encontrados los rangos correspondientes, lo único que queda son aquellos rangos que encierran la región en alguna dimensión. Para encontrar estas superposiciones, se crean árboles de intervalos y se consulta un eje que se cruza para cada uno. Por ejemplo, en dos dimensiones, la parte inferior del cuadrado (o cualquier otra línea horizontal que se cruce ) se compararía con el árbol de intervalos construido para el eje horizontal. Del mismo modo, la izquierda (o cualquier otra línea vertical que se cruce ) se comparará con el árbol de intervalos construido en el eje vertical. ${\displaystyle N}$ ${\displaystyle R}$ ${\displaystyle N}$ ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle R}$

Cada árbol de intervalo también necesita una adición para dimensiones superiores. En cada nodo que atravesamos en el árbol, se compara para encontrar superposiciones. En lugar de dos listas ordenadas de puntos como se usó en el caso unidimensional, se construye un árbol de rangos. Esto permite la recuperación eficiente de todos los puntos en esa región de superposición . ${\displaystyle x}$ ${\displaystyle S_{\textrm {center}}}$ ${\displaystyle S_{\textrm {center}}}$ ${\displaystyle R}$

Supresión

Si después de eliminar un intervalo del árbol, el nodo que contiene ese intervalo no contiene más intervalos, ese nodo puede eliminarse del árbol. Esto es más complejo que una operación normal de eliminación de un árbol binario.

Un intervalo puede superponerse al punto central de varios nodos del árbol. Dado que cada nodo almacena los intervalos que se superponen, con todos los intervalos completamente a la izquierda de su punto central en el subárbol izquierdo, de manera similar para el subárbol derecho, se deduce que cada intervalo se almacena en el nodo más cercano a la raíz del conjunto de nodos cuyo punto central se superpone.

Las operaciones de eliminación normales en un árbol binario (para el caso en el que el nodo que se elimina tiene dos hijos) implican promover un nodo más lejos de la hoja a la posición del nodo que se elimina (normalmente el hijo más a la izquierda del subárbol derecho, o el hijo más a la derecha del subárbol izquierdo).

Eliminar un nodo con dos hijos de un árbol de búsqueda binario usando el predecesor en orden (nodo más a la derecha en el subárbol izquierdo, etiquetado como 6 ).

Como resultado de esta promoción, algunos nodos que estaban por encima del nodo promocionado se convertirán en sus descendientes; es necesario buscar en estos nodos intervalos que también se superpongan al nodo promocionado y mover esos intervalos al nodo promocionado. Como consecuencia, esto puede dar como resultado nuevos nodos vacíos, que deben eliminarse, siguiendo nuevamente el mismo algoritmo.

Equilibrio

Los mismos problemas que afectan la eliminación también afectan las operaciones de rotación; la rotación debe preservar la invariante de que los nodos se almacenen lo más cerca posible de la raíz.

árbol aumentado

Un árbol aumentado con un valor bajo como clave y un valor máximo alto como anotación adicional.

Por ejemplo, al probar si el intervalo dado [40, 60) se superpone a los intervalos en el árbol que se muestra arriba, vemos que no se superpone al intervalo [20, 36) en la raíz, pero desde el valor bajo de la raíz (20) es menor que el valor alto buscado (60), debemos buscar el subárbol correcto. El máximo máximo del subárbol izquierdo de 41 excede el valor bajo buscado (40), por lo que debemos buscar también en el subárbol izquierdo. Sin embargo, ambos descendientes del nodo [3, 41) tienen máximos máximos inferiores a 40, por lo que la búsqueda del subárbol izquierdo termina allí y no es necesario buscarlos.

Otra forma de representar intervalos se describe en Cormen et al. (2009, Sección 14.3: Árboles de intervalos, págs. 348–354).

Tanto la inserción como la eliminación requieren tiempo, siendo el número total de intervalos en el árbol antes de la operación de inserción o eliminación. ${\displaystyle O(\log n)}$ ${\displaystyle n}$

Se puede construir un árbol aumentado a partir de un árbol ordenado simple, por ejemplo un árbol de búsqueda binario o un árbol de búsqueda binario autoequilibrado , ordenado por los valores "bajos" de los intervalos. Luego se agrega una anotación adicional a cada nodo, registrando el valor superior máximo entre todos los intervalos desde este nodo hacia abajo. Mantener este atributo implica actualizar todos los antecesores del nodo de abajo hacia arriba cada vez que se agrega o elimina un nodo. Esto requiere solo O( h ) pasos por adición o eliminación de nodos, donde h es la altura del nodo agregado o eliminado en el árbol. Si hay rotaciones de árbol durante la inserción y eliminación, es posible que los nodos afectados también necesiten actualizarse.

Ahora bien, se sabe que dos intervalos y se superponen sólo cuando ambos y . Al buscar en los árboles nodos que se superpongan con un intervalo determinado, puede omitir inmediatamente: ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A_{\textrm {low}}\leq B_{\textrm {high}}}$ ${\displaystyle A_{\textrm {high}}\geq B_{\textrm {low}}}$

• todos los nodos a la derecha de los nodos cuyo valor bajo está más allá del final del intervalo dado.
• todos los nodos que tienen su valor máximo alto por debajo del inicio del intervalo dado.

Consultas de membresía

Se puede ganar algo de rendimiento si el árbol evita recorridos innecesarios. Estos pueden ocurrir al agregar intervalos que ya existen o al eliminar intervalos que no existen.

Se puede definir un orden total en los intervalos ordenándolos primero por sus límites inferiores y luego por sus límites superiores. Luego, se puede realizar una verificación de membresía a tiempo, en comparación con el tiempo necesario para encontrar duplicados si los intervalos se superponen con el intervalo que se va a insertar o eliminar. Esta solución tiene la ventaja de no requerir estructuras adicionales. El cambio es estrictamente algorítmico. La desventaja es que las consultas sobre membresía toman tiempo. ${\displaystyle O(\log n)}$ ${\displaystyle O(k+\log n)}$ ${\displaystyle k}$ ${\displaystyle O(\log n)}$

Alternativamente, a la velocidad de la memoria, las consultas de membresía en un tiempo constante esperado se pueden implementar con una tabla hash, actualizada al mismo tiempo que el árbol de intervalos. Es posible que esto no necesariamente duplique el requisito total de memoria, si los intervalos se almacenan por referencia en lugar de por valor. ${\displaystyle O(n)}$

Ejemplo de Java: agregar un nuevo intervalo al árbol

La clave de cada nodo es el intervalo en sí, por lo tanto, los nodos se ordenan primero por valor bajo y finalmente por valor alto, y el valor de cada nodo es el punto final del intervalo:

public void add ( Intervalo i ) { put ( i , i . getEnd ()); }      

Ejemplo de Java: buscar un punto o un intervalo en el árbol

Para buscar un intervalo, se recorre el árbol, utilizando la clave ( n.getKey()) y el valor alto ( n.getValue()) para omitir cualquier rama que no pueda superponerse a la consulta. El caso más simple es una consulta puntual:

// Busca todos los intervalos que contienen "p", comenzando con el // nodo "n" y agregando intervalos coincidentes a la lista "resultado" public void search ( IntervalNode n , Point p , List < Interval > result ) { // Don No buscar nodos que no existen si ( n == null ) return ;               // Si p está a la derecha del punto más a la derecha de cualquier intervalo // en este nodo y en todos los hijos, no habrá coincidencias. si ( p . compareTo ( n . getValue ()) > 0 ) retorno ;       // Buscar niños izquierdos buscar ( n . getLeft (), p , resultado );    // Verifique este nodo si ( n . getKey (). contiene ( p )) resultado . agregar ( n . getKey ());    // Si p está a la izquierda del inicio de este intervalo, // entonces no puede estar en ningún elemento secundario a la derecha. if ( p . compareTo ( n . getKey (). getStart ()) < 0 ) return ;       // De lo contrario, busque la búsqueda de niños correctos ( n . getRight (), p , resultado ); }   

dónde

a.compareTo(b)devuelve un valor negativo si a < b

a.compareTo(b)devuelve cero si a = b

a.compareTo(b)devuelve un valor positivo si a > b

El código para buscar un intervalo es similar, excepto por la marca en el medio:

// Verifique este nodo si ( n . getKey (). se superpone con ( i )) resultado . agregar ( n . getKey ());   

overlapsWith()Se define como:

superposiciones booleanas públicas con ( intervalo otro ) { retorno inicio . compareTo ( otro . getEnd ()) <= 0 && fin . compareTo ( otro . getStart ()) >= 0 ; }            

Dimensiones superiores

Los árboles aumentados se pueden extender a dimensiones superiores recorriendo las dimensiones en cada nivel del árbol. Por ejemplo, para dos dimensiones, los niveles impares del árbol pueden contener rangos para la coordenada x , mientras que los niveles pares contienen rangos para la coordenada y . Este enfoque convierte efectivamente la estructura de datos de un árbol binario aumentado a un árbol kd aumentado , lo que complica significativamente los algoritmos de equilibrio para inserciones y eliminaciones.

Una solución más sencilla es utilizar árboles de intervalos anidados. Primero, cree un árbol usando los rangos de la coordenada y . Ahora, para cada nodo en el árbol, agregue otro árbol de intervalo en los rangos x , para todos los elementos cuyo rango y sea el mismo que el rango y de ese nodo .

La ventaja de esta solución es que se puede ampliar a un número arbitrario de dimensiones utilizando la misma base de código.

Al principio, el coste adicional de los árboles anidados puede parecer prohibitivo, pero normalmente no es así. Al igual que con la solución no anidada anterior, se necesita un nodo por coordenada x , lo que produce la misma cantidad de nodos para ambas soluciones. La única sobrecarga adicional es la de las estructuras de árbol anidadas, una por intervalo vertical. Esta estructura suele ser de tamaño insignificante y consta únicamente de un puntero al nodo raíz y posiblemente del número de nodos y la profundidad del árbol.

Árbol orientado medial o longitudinal

Un árbol orientado a la media o a la longitud es similar a un árbol aumentado, pero simétrico, con el árbol de búsqueda binario ordenado por los puntos mediales de los intervalos. Hay un montón binario orientado al máximo en cada nodo, ordenado por la longitud del intervalo (o la mitad de la longitud). También almacenamos el valor mínimo y máximo posible del subárbol en cada nodo (de ahí la simetría).

prueba de superposición

Utilizando únicamente los valores inicial y final de dos intervalos , para , la prueba de superposición se puede realizar de la siguiente manera: ${\displaystyle \left(a_{i},b_{i}\right)}$ ${\displaystyle i=0,1}$

${\displaystyle a_{0}<b_{1}}$y ${\displaystyle a_{1}<b_{0}}$

Esto se puede simplificar usando la suma y la diferencia:

${\displaystyle s_{i}=a_{i}+b_{i}}$

${\displaystyle d_{i}=b_{i}-a_{i}}$

Lo que reduce la prueba de superposición a:

${\displaystyle \left|s_{1}-s_{0}\right|<d_{0}+d_{1}}$

Añadiendo intervalo

Agregar nuevos intervalos al árbol es lo mismo que para un árbol de búsqueda binario usando el valor medio como clave. Ingresamos al montón binario asociado con el nodo y actualizamos los valores mínimos y máximos posibles asociados con todos los nodos superiores. ${\displaystyle d_{i}}$

Buscando todos los intervalos superpuestos

Usemos para el intervalo de consulta y para la clave de un nodo (en comparación con intervalos) ${\displaystyle a_{q},b_{q},m_{q},d_{q}}$ ${\displaystyle M_{n}}$ ${\displaystyle m_{i}}$

Comenzando con el nodo raíz, en cada nodo, primero verificamos si es posible que nuestro intervalo de consulta se superponga con el subárbol de nodos usando los valores mínimo y máximo de nodo (si no es así, no continuamos para este nodo).

Luego calculamos los intervalos dentro de este nodo (no sus hijos) para que se superpongan con el intervalo de consulta (conociendo ): ${\displaystyle \min \left\{d_{i}\right\}}$ ${\displaystyle m_{i}=M_{n}}$

${\displaystyle \min \left\{d_{i}\right\}=\left|m_{q}-M_{n}\right|-d_{q}}$

y realizar una consulta en su montón binario para el mayor que ${\displaystyle d_{i}}$ ${\displaystyle \min \left\{d_{i}\right\}}$

Luego pasamos por los hijos izquierdo y derecho del nodo, haciendo lo mismo.

En el peor de los casos, tenemos que escanear todos los nodos del árbol de búsqueda binario, pero dado que la consulta del montón binario es óptima, esto es aceptable (un problema bidimensional no puede ser óptimo en ambas dimensiones).

Se espera que este algoritmo sea más rápido que un árbol de intervalos tradicional (árbol aumentado) para operaciones de búsqueda. Agregar elementos es un poco más lento en la práctica, aunque el orden de crecimiento es el mismo.

Referencias

1. https://personal.us.es/almar/cg/08windowing.pdf ^{[ URL desnuda PDF ]}
2. Jens M. Schmidt. "Problemas de apuñalamiento de intervalos en rangos enteros pequeños" . DOI. ISAAC'09, 2009
3. Consultas de rango # Operadores de semigrupo

• Mark de Berg , Marc van Kreveld , Mark Overmars y Otfried Schwarzkopf . Geometría computacional , segunda edición revisada. Springer-Verlag 2000. Sección 10.1: Árboles de intervalos, págs.
• Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2009), Introducción a los algoritmos (3.ª ed.), MIT Press y McGraw-Hill, ISBN 978-0-262-03384-8
• Franco P. Preparata y Michael Ian Shamos . Geometría computacional: una introducción . Springer-Verlag, 1985

enlaces externos

• CGAL: la biblioteca de algoritmos de geometría computacional en C++ contiene una implementación sólida de árboles de rango
• Boost.Icl ofrece implementaciones en C++ de conjuntos de intervalos y mapas.
• IntervalTree (Python): un árbol de intervalos centrado con equilibrio AVL, compatible con intervalos etiquetados
• Árbol de intervalos (C#): un árbol de intervalos aumentado, con equilibrio AVL
• Árbol de intervalos (Ruby): un árbol de intervalos centrado, inmutable, compatible con intervalos etiquetados
• IntervalTree (Java): un árbol de intervalos aumentado, con equilibrio AVL, compatible con superposición, búsqueda, interfaz de colección e intervalos asociados a ID.
• Tree::Interval::Fast (Perl/C): creación y manipulación eficiente de árboles de intervalos.