Algorytm przedziałów czasowych, który obsługuje łączenie przedziałów bez nakładania się

Question

Szukam algorytmu drzewa interwałowego podobnego do drzewa interwałów czerwono-czarne w CLR, ale obsługuje domyślnie łączenie przedziałów, tak aby nigdy nie zachodziły na siebie nakładające się interwały.

Innymi słowy, jeśli drzewo zawierało dwa przedziały [2,3] i [5,6], a użytkownik dodał przedział [4,4], wynikiem byłoby drzewo zawierające tylko jeden przedział [2, 6].

Dzięki

Aktualizacja: przypadek użycia Zastanawiam jest obliczenie przechodni zamknięcia. Zbiory przedziałów czasowych są używane do przechowywania zestawów następców, ponieważ zostały one found to be quite compact. Ale jeśli reprezentujesz zbiory interwałowe jako listę połączoną, odkryłem, że w niektórych sytuacjach mogą one stać się dość duże, a więc także czas wymagany do znalezienia punktu wstawienia. Stąd moje zainteresowanie drzewami interwałowymi. Również może być całkiem dużo scalania jednego drzewa z innym (tj. Operacja zestaw OR) - jeśli oba drzewa są duże, może być lepiej utworzyć nowe drzewo przy użyciu spacerów wewnątrz drzew, zamiast wielokrotnych wstawień każdego interwału.

Answer 1

Problemem, który widzę, jest to, że wstawienie dużego interwału może wymazać dużą część drzewa, co utrudnia odzyskanie czerwono-czarnych niezmienników.

Myślę, że łatwiej byłoby użyć drzewa gry w następujący sposób. Dla uproszczenia każde drzewo zawiera dwa wskaźniki, przedział A po lewej stronie wszystkich pozostałych przedziałów i przedział Z po prawej stronie. Podczas wstawiania przedziału I, splay I 's poprzednik-do-być H do katalogu głównego drzewa. Drzewo wygląda

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

Teraz odłączyć X i pochylenie I jest następcą-to-be J do korzenia.

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

W tym momencie wszystkich przedziałów czasowych, które pokrywają I są w lewej poddrzewem J „S. Odłącz to poddrzewo i umieść wszystkie jego węzły na wolnej liście, rozszerzając w razie potrzeby I. Dokonaj I rodzicem H i J

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

i kontynuować na naszej wesołej drodze. Ta operacja jest amortyzowana przez O (log n), gdzie n jest liczbą węzłów drzewa (można to sprawdzić poprzez zbadanie potencjalnej funkcji drzewa gry i wykonanie wielu algebry).

---

Powinienem dodać, że istnieje naturalna rekurencyjne drzewa do drzewa seryjnej przez wstawienie korzeń jednego drzewa, a następnie połączenia lewego i prawego poddrzewa. Nie wiem, jak analizować to z ręki.