Algoritmo de árbol de intervalo que admite la fusión de intervalos sin superposición

Question

Estoy buscando un algoritmo de árbol de intervalos similar al árbol de intervalos rojo-negro en CLR, pero que admite la fusión de intervalos de forma predeterminada para que nunca haya intervalos superpuestos.

En otras palabras, si tiene un árbol que contiene dos intervalos [2,3] y [5,6] y ha agregado el intervalo [4,4], el resultado sería un árbol que contiene solo un intervalo [2, 6].

Gracias

Actualización: el caso de uso que estoy considerando es el cálculo de cierre transitivo. Los conjuntos de intervalos se utilizan para almacenar los conjuntos sucesores porque han sido found to be quite compact. Pero si representas conjuntos de intervalos como una lista vinculada, he descubierto que en algunas situaciones pueden llegar a ser bastante grandes y, por lo tanto, también lo hace el tiempo requerido para encontrar el punto de inserción. De ahí mi interés en los árboles de intervalo. También puede haber una gran cantidad de fusión de un árbol con otro (es decir, una operación O establecida): si ambos árboles son grandes, entonces puede ser mejor crear un nuevo árbol utilizando caminatas inorder de ambos árboles en lugar de inserciones repetidas de cada intervalo.

Answer 1

El problema que veo es que la inserción de un intervalo grande puede borrar una gran parte del árbol, lo que dificulta la recuperación de las invariantes rojo-negro.

Creo que sería más fácil usar un árbol de distribución, de la siguiente manera. Para simplificar, cada árbol contiene dos centinelas, un intervalo A a la izquierda de todos los demás intervalos y un intervalo Z a la derecha. Al insertar un intervalo I, seleccione I predecesor-to-be H en la raíz del árbol. El árbol se parece a

H 
/\ 
... X 
    /\ 
    ... ... 

Ahora desprender X y Splay I 's sucesor-a-ser J a la raíz.

H  J 
/ /\ 
...  ... ... 

En este punto, todos los intervalos que se solapan I están en subárbol izquierdo J 's. Separe ese subárbol y coloque todos sus nodos en la lista libre, extendiendo I si es necesario. Hacer I el padre de H y J

 I 
    /\ 
    H J 
/ \ 
...  ... 

y continuar en nuestro camino alegre. Esta operación se amortiza O (log n), donde n es el número de nodos de árbol (esto se puede comprobar examinando la función de potencial del árbol de dispersión y realizando una gran cantidad de álgebra).

---

debo añadir que hay una fusión recursiva naturales de árbol a árbol mediante la inserción de la raíz de un árbol y luego la fusión de los subárboles izquierdo y derecho. No sé cómo analizarlo.