16

我正在寻找一种类似于 CLR 中的红黑区间树的区间树算法，但默认情况下它支持合并区间，因此不会有任何重叠区间。

换句话说，如果您有一棵包含两个区间 [2,3] 和 [5,6] 的树，并且您添加了区间 [4,4]，那么结果将是一棵仅包含一个区间 [2,6] 的树。

谢谢

更新：我正在考虑的用例是计算传递闭包。区间集用于存储后继集，因为已发现它们非常紧凑。但是，如果您将区间集表示为链表，我发现在某些情况下它们可能会变得非常大，因此找到插入点所需的时间也是如此。因此我对区间树感兴趣。此外，可能会有很多将一棵树与另一棵树合并（即一组 OR 操作） - 如果两棵树都很大，那么使用两棵树的中序游走而不是重复插入每个间隔来创建一棵新树可能会更好。

4

1 回答 1

4

我看到的问题是插入一个大的间隔可以消除树的一大块，使得很难恢复红黑不变量。

我认为使用伸展树会更容易，如下所示。为简单起见，每棵树都包含两个哨兵，一个区间A位于所有其他区间的左侧，一个区间Z位于右侧。插入区间时I，将 splayI的前身插入H到树的根部。树看起来像

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

现在分离X和 splayI的后继者到J根。

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

此时所有重叠的区间I都在J的左子树中。分离该子树并将其所有节点放在空闲列表中，I必要时进行扩展。使和I的父级HJ

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

继续我们的快乐之路。这个操作是 O(log n) 摊销的，其中 n 是树节点的数量（这可以通过检查 splay 树势函数和做很多代数来证明）。

我应该补充一点，通过插入一棵树的根然后合并左右子树，可以实现自然递归的树到树合并。我不知道如何分析它。

于 2010-04-09T15:39:12.633 回答