支持間隔合併不重疊的區間樹算法

我正在尋找類似於CLR中的紅黑間隔樹的間隔樹算法，但默認情況下支持合併間隔，以便永遠不會有任何重疊間隔。支持間隔合併不重疊的區間樹算法

換句話說，如果你有一個包含兩個區間[2,3]和[5,6]的樹，並且你添加了區間[4,4]，結果將是一棵只包含一個區間[2， 6]。

謝謝

更新：我正在考慮的用例是計算傳遞閉包。間隔集用於存儲後繼集，因爲它們是found to be quite compact。但是，如果將間隔集表示爲鏈表，我發現在某些情況下，它們可能變得相當大，因此找到插入點所需的時間也是如此。因此我對間隔樹感興趣。也可能有相當多的合併一棵樹與另一棵樹（即一組OR操作） - 如果兩棵樹都很大，那麼使用兩棵樹的中間行來創建一棵新樹可能會更好，而不是每個區間的重複插入。

來源

2010-04-07 Dave Griffiths

我已經刪除了我的答案，因爲我愚蠢地忽略了一些情況。它仍然可以修復，但會變得更加複雜。無論如何，因爲你更新說，你將主要合併整個樹，答案似乎不再有用，因爲順序遍歷將更快。 – interjay 2010-04-09 12:08:32

噢，好的。有時我會合並兩棵大樹，當inorder可能會更快時，但更多的時候我會爲一棵大樹添加一棵小樹。 – 2010-04-09 13:15:55

我看到的問題是，插入一個很大的間隔可能會消滅大部分樹，使得難以恢復紅黑色不變量。

我認爲使用splay樹會更容易，如下所示。爲了簡單起見，每棵樹包含兩個哨兵，所有其他區間左側的區間爲A，右側區間爲Z。當插入間隔I時，展開I的前身H到樹的根部。樹看起來像

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

現在分離X和張開I的繼任者將要J到根。

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

此時所有的重疊區間I是J的左子樹。分離該子樹並將其所有節點放在空閒列表中，如有必要，則將其擴展爲I。讓I的H家長和J

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

，並繼續我們的快樂的方式。這個操作是O（log n）攤銷，其中n是樹節點的數量（這可以通過檢查splay樹勢函數和做許多代數來證明）。

我要補充一點，有一個天然的遞歸樹到樹合併通過插入一個樹的根，然後合併左，右子樹。我不知道如何分析它。

來源

2010-04-09 15:39:12 user287792

非常有趣，謝謝！ – 2010-04-19 15:36:39

支持間隔合併不重疊的區間樹算法

回答

相關問題