Árbol de intervalos

Estructura de datos de árbol para almacenar intervalos

En informática , un árbol de intervalos es una estructura de datos en forma de árbol que contiene intervalos . En concreto, permite encontrar de forma eficiente todos los intervalos que se superponen con cualquier intervalo o punto dado. Se suele utilizar para consultas en ventanas, ^[1] por ejemplo, para encontrar todas las carreteras en un mapa informático 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 intersecta el punto o intervalo dado, lo que requiere tiempo, donde 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 intervalo grande que interseca todos los intervalos en la colección, esto es asintóticamente óptimo ; sin embargo, podemos hacerlo mejor considerando 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 intervalo tienen un tiempo de consulta de y un tiempo de creación inicial de , mientras que limitan el consumo de memoria a . Después de la creación, los árboles de intervalo 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 de enteros pequeños ( 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 dado (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 binario de búsqueda simple y consultar en el tiempo. Sin embargo, con intervalos que se superponen arbitrariamente, no hay forma de comparar dos intervalos para la inserción 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 en el tiempo, pero los resultados deben fusionarse, lo que requiere tiempo. Esto nos da consultas en , lo 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. En este artículo se describen dos diseños alternativos para un árbol de intervalos, denominados árbol de intervalos centrado y árbol aumentado .

Árbol de intervalos 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 poder 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éndolo por la mitad en (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 superpuestos a los que 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 independiente vinculada al nodo del á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 donde 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 de inicio
• 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 consisten en 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 utilizaría para recorrer un árbol binario tradicional, pero con lógica adicional para facilitar la búsqueda de los 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 del nodo 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 en que comiencen antes de deben superponerse si es menor que . De manera similar, la misma técnica también se aplica para verificar un intervalo dado. Si un intervalo dado termina en y e y es menor que , todos los intervalos en que comiencen 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 en terminan después de , o no podrían superponerse también . Por lo tanto, solo necesitamos encontrar aquellos intervalos en que comienzan antes de . Podemos consultar las listas de que ya se han construido. Como solo nos preocupamos por los comienzos de los intervalos en este escenario, podemos consultar la lista ordenada por comienzos. Supongamos que encontramos el número más cercano no mayor que en esta lista. Todos los rangos desde el comienzo de la lista hasta ese punto encontrado se superponen porque comienzan antes y terminan después (como sabemos porque se superponen que es mayor que ). Por lo tanto, simplemente podemos comenzar a enumerar intervalos en la lista hasta que el valor del punto de inicio 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 en deben comenzar antes de , por lo que encontramos aquellos intervalos que terminan después usando la lista ordenada por finales de intervalo. ${\displaystyle x}$ ${\displaystyle x_{\textrm {center}}}$ ${\displaystyle S_{\textrm {center}}}$ ${\displaystyle x}$ ${\displaystyle x}$

Si coincide exactamente , se pueden agregar todos los intervalos 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 intersecte nuestro intervalo de consulta, se debe cumplir una de las siguientes condiciones: ${\displaystyle r}$ ${\displaystyle q}$

• o bien 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 de inicio y/o fin dentro de ellos usando un árbol construido por separado. En el caso unidimensional, podemos usar un árbol de búsqueda que contenga todos los puntos de inicio y fin en el conjunto de intervalos, cada uno con un puntero a su intervalo correspondiente. Una búsqueda binaria en el tiempo para el inicio y fin de revela los puntos mínimo y máximo 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 un indicador binario 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}$

Por último, debemos encontrar intervalos que encierren a . Para encontrarlos, elegimos cualquier punto dentro de él y usamos el algoritmo anterior para encontrar todos los intervalos que intersecan ese punto (nuevamente, teniendo cuidado de eliminar los 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)}$

En primer lugar, se construye un árbol de intervalos en dimensiones que permite la recuperación eficiente de todos los intervalos con puntos de inicio y fin dentro de la región de consulta . Una vez que se encuentran 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 interseca a cada uno. Por ejemplo, en dos dimensiones, la parte inferior del cuadrado (o cualquier otra línea horizontal que interseca a ) se consultaría contra el árbol de intervalos construido para el eje horizontal. Del mismo modo, la izquierda (o cualquier otra línea vertical que interseca a ) se consultaría contra el árbol de intervalos construido sobre el eje vertical. ${\displaystyle N}$ ${\displaystyle R}$ ${\displaystyle N}$ ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle R}$

Cada árbol de intervalos también necesita una adición para dimensiones superiores. En cada nodo que recorremos en el árbol, se compara con para encontrar superposiciones. En lugar de dos listas ordenadas de puntos como se utilizó en el caso unidimensional, se construye un árbol de rango. 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 ya no contiene más intervalos, se puede eliminar ese nodo del árbol. Esta operación es más compleja 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 lo superponen, y todos los intervalos están completamente a la izquierda de su punto central en el subárbol izquierdo, lo mismo ocurre con el subárbol derecho; por lo tanto, 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 que el nodo que se está eliminando tiene dos hijos) implican promover un nodo más alejado de la hoja a la posición del nodo que se está eliminando (generalmente 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 utilizando el predecesor en orden (nodo más a la derecha en el subárbol izquierdo, etiquetado 6 ).

Como resultado de esta promoción, algunos nodos que estaban por encima del nodo promocionado pasarán a ser sus descendientes; es necesario buscar en estos nodos intervalos que también se superpongan al nodo promocionado y mover esos intervalos hacia el 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 almacenan 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 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 como el valor bajo de la raíz (20) es menor que el valor alto buscado (60), debemos buscar el subárbol derecho. El alto máximo del subárbol izquierdo de 41 excede el valor bajo buscado (40), por lo que también debemos buscar en el subárbol izquierdo. Sin embargo, ambos descendientes del nodo [3, 41) tienen altos máximos menores 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}$

Un árbol aumentado se puede construir a partir de un árbol ordenado simple, por ejemplo, un árbol binario de búsqueda o un árbol binario de búsqueda 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 ancestros del nodo desde abajo hacia arriba cada vez que se agrega o elimina un nodo. Esto solo requiere O( h ) pasos por cada adición o eliminación de nodo, donde h es la altura del nodo agregado o eliminado en el árbol. Si hay alguna rotación del árbol durante la inserción y eliminación, es posible que también sea necesario actualizar los nodos afectados.

Ahora, se sabe que dos intervalos y se superponen solo cuando ambos y . Al buscar en los árboles nodos que se superponen 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 sobre membresía

Se puede mejorar el rendimiento si el árbol evita recorridos innecesarios, como cuando se agregan intervalos que ya existen o se eliminan 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 comprobación de pertenencia en el tiempo, en comparación con el tiempo necesario para encontrar duplicados si los intervalos se superponen al intervalo que se va a insertar o eliminar. Esta solución tiene la ventaja de no requerir ninguna estructura adicional. El cambio es estrictamente algorítmico. La desventaja es que las consultas de pertenencia toman tiempo. ${\displaystyle O(\log n)}$ ${\displaystyle O(k+\log n)}$ ${\displaystyle k}$ ${\displaystyle O(\log n)}$

Como alternativa, a la velocidad de la memoria, las consultas de pertenencia en tiempo constante esperado se pueden implementar con una tabla hash, actualizada al mismo tiempo que el árbol de intervalos. Esto no necesariamente duplica 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 mismo, 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: Búsqueda de 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 las ramas que no pueden superponerse a la consulta. El caso más simple es una consulta puntual:

// Busca todos los intervalos que contengan "p", comenzando con el // nodo "n" y agregando los intervalos coincidentes a la lista "result" public void search ( IntervalNode n , Point p , List < Interval > result ) { // No busque nodos que no existan if ( n == null ) return ;               // Si p está a la derecha del punto más a la derecha de cualquier intervalo // en este nodo y todos los hijos, no habrá ninguna coincidencia. if ( p . compareTo ( n . getValue ()) > 0 ) return ;       // Buscar hijos de la izquierda search ( n.getLeft ( ) , p , result );    // Verifique este nodo si ( n . getKey (). contiene ( p )) result . add ( n . getKey ());    // Si p está a la izquierda del inicio de este intervalo, // entonces no puede estar en ningún hijo a la derecha. if ( p . compareTo ( n . getKey (). getStart ()) < 0 ) return ;       // De lo contrario, busque los hijos correctos search ( n.getRight ( ) , p , result ); }   

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 verificación en el medio:

// Verifique este nodo if ( n . getKey (). overlapsWith ( i )) result . add ( n . getKey ());   

overlapsWith()se define como:

público booleano overlapsWith ( Intervalo otro ) { return inicio . compareTo ( otro . getEnd ()) <= 0 && fin . compareTo ( otro . getStart ()) >= 0 ; }            

Dimensiones superiores

Los árboles aumentados se pueden ampliar 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 eficazmente 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 utilizando los rangos de la coordenada y . Ahora, para cada nodo del árbol, agregue otro árbol de intervalos 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 puede extenderse a un número arbitrario de dimensiones utilizando la misma base de código.

En un 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 cada coordenada x , lo que da como resultado la misma cantidad de nodos para ambas soluciones. El único gasto adicional es el de las estructuras de árbol anidadas, una por intervalo vertical. Esta estructura suele tener un tamaño insignificante, ya que consta únicamente de un puntero al nodo raíz y, posiblemente, de la cantidad de nodos y la profundidad del árbol.

Árbol orientado medial o longitudinalmente

Un árbol orientado medial o longitudinalmente es similar a un árbol aumentado, pero simétrico, con el árbol binario de búsqueda 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 iniciales y finales 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 binaria utilizando el valor medio como clave. Ingresamos en el 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

Vamos a utilizar para el intervalo de consulta y para la clave de un nodo (en comparación con los 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 del nodo usando los valores mínimo y máximo del 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 (sabiendo ): ${\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 's 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 binaria, pero como 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 las operaciones de búsqueda. La adición de elementos es un poco más lenta en la práctica, aunque el orden de crecimiento es el mismo.

Referencias

1. https://personal.us.es/almar/cg/08windowing.pdf ^{[ URL básica PDF ]}
2. Jens M. Schmidt. Problemas de punción de intervalos en rangos de 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 . Computational Geometry , segunda edición revisada. Springer-Verlag 2000. Sección 10.1: Árboles de intervalos, págs. 212–217.
• 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 robusta 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, compatibilidad con superposición, búsqueda, interfaz de colección e intervalos asociados a identificación
• Tree::Interval::Fast (Perl/C) - Creación y manipulación eficiente de árboles de intervalos.