支持间隔合并不重叠的区间树算法

我正在寻找类似于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

支持间隔合并不重叠的区间树算法

回答

相关问题