Algoritmo ad albero intervallo che supporta la fusione di intervalli senza sovrapposizione

Question

Sto cercando un algoritmo ad albero di intervallo simile all'albero di intervallo rosso-nero in CLR ma che supporta l'unione di intervalli per impostazione predefinita in modo che non ci siano mai intervalli di sovrapposizione.

In altre parole se si avesse un albero contenente due intervalli [2,3] e [5,6] e si aggiungesse l'intervallo [4,4], il risultato sarebbe un albero contenente un solo intervallo [2, 6].

Grazie

Aggiornamento: il caso d'uso che sto considerando è il calcolo chiusura transitiva. I set di intervalli vengono utilizzati per memorizzare i set successivi perché sono stati found to be quite compact. Ma se rappresenti gli intervalli solo come elenco collegato, ho scoperto che in alcune situazioni possono diventare piuttosto grandi e quindi anche il tempo necessario per trovare il punto di inserimento. Da qui il mio interesse per gli alberi intervallati. Inoltre ci può essere un bel po 'di fusione di un albero con un altro (vale a dire un'operazione OR impostata) - se entrambi gli alberi sono grandi allora potrebbe essere meglio creare un nuovo albero usando le passeggiate in entrata di entrambi gli alberi piuttosto che gli inserimenti ripetuti di ogni intervallo.

Answer 1

Il problema che vedo è che l'inserimento di un intervallo di grandi dimensioni può eliminare un grosso blocco dell'albero, rendendo difficile il recupero degli invarianti rosso-nero.

Penso che sarebbe più semplice utilizzare uno splay tree, come segue. Per semplicità, ogni albero contiene due sentinelle, un intervallo A alla sinistra di tutti gli altri intervalli e un intervallo Z a destra. Quando si inserisce un intervallo I, si visualizza il predecessore I precedente alla H nella radice dell'albero. L'albero si presenta come

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

Ora staccare X e strombatura I 's successore-to-be J alla radice.

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

A questo punto tutti gli intervalli che si sovrappongono I sono in sottoalbero sinistro J s'. Scollega quella sottostruttura e metti tutti i suoi nodi nella lista libera, estendendo I se necessario. Fare I il genitore di H e J

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

e continuare il nostro modo allegro. Questa operazione è O (log n) ammortizzata, dove n è il numero di nodi dell'albero (ciò può essere dimostrato esaminando la funzione potenziale dell'albero di splay e facendo molta algebra).

---

devo aggiungere che c'è una naturale ricorsiva unione albero a albero inserendo la radice di un albero e quindi unendo il sottoalberi sinistro e destro. Non so come analizzarlo a mano.