Árbol de intervalo
Esta estructura de datos se compone de dos listas, una que contiene todos los intervalos según sus puntos iniciales, y otra que contiene todos los intervalos según sus puntos finales.
El resultado es un árbol ternario con cada nodo de almacenamiento: Teniendo en cuenta la estructura de datos construida, recibimos consultas consisten en rangos o puntos, y retornamos todos los rangos en el conjunto original superponiendo esta entrada.
La tarea es encontrar todos los intervalos en el árbol que se superponen a un punto dado x.
Por lo tanto, sólo necesitamos encontrar esos intervalos en S_center que comienzan antes de x.
Ya que sólo nos preocupamos por los inicios del intervalo en este escenario, se puede consultar la lista ordenada por comienzos.
Por lo tanto, podemos simplemente comenzar enumerando intervalos en la lista hasta que el valor del punto final supere a x.
Se debe tener cuidado para evitar duplicados, ya que un intervalo podría comenzar y terminar dentro de R. Esto se puede hacer usando una puntero binario en cada intervalo para marcar si es o no añadido al conjunto de resultados.
Esto es más complejo que una operación de eliminación en un árbol binario normal.
Operaciones de eliminación normales en un árbol binario (para el caso en que el nodo se borre tiene dos hijos) implican la promoción de un nodo más de la raíz a la posición del nodo que se está eliminado (por lo general el hijo más a la izquierda del subárbol derecho, o el hijo más a la derecha del subárbol izquierdo).
Las mismas cuestiones que afectan a la eliminación también afectan a las operaciones de rotación; la rotación debe preservar el invariante que los intervalos se almacenan tan cerca de la raíz como sea posible.
Otra manera de representar intervalos se describe en Cormen et al.
Al buscar en los árboles los nodos superpuestos con un intervalo dado, puede saltar de inmediato: Un total del pedido se puede definir en los intervalos ordenándolas por primera vez por su valor 'bajo' y, finalmente, por su 'alto' valor.
La llave de cada nodo es el intervalo en sí mismo, por eso cada nodo está ordenado primero por el menor valor y al final por el valo más alto, y el valor de cada nodo es el punto al final del intervalo: Para buscar un intervalo, caminas por el árbol, omitiendo las ramas que no contengan lo que estas buscando: where El código para buscar un intervalo es similar: overlapsWith() is defined as: Esto puede extenderse a dimensiones más altas por ciclos a través de las dimensiones en cada nivel del árbol.
Sin embargo, no es bastante obvio cómo la lógica de rotación que tendrá ampliarse para mantener el árbol balanceado.
Al principio, el costo de los árboles adicionales podría parecer prohibitivo, pero que por lo general no es el caso.
La única diferencia es que se necesita una estructura de árbol adicional por intervalo vertical.
