间隔树算法,支持合并没有重叠的间隔

Question

我正在寻找一种类似于CLR中的红黑区间树的区间树算法,但它默认支持合并区间,因此从不存在任何重叠区间.

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

谢谢

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

Answer 1

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

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

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

现在分离X并展开根I的未来继承者。J

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

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

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

并继续我们的快乐之路。此操作是 O(log n) 摊销的，其中 n 是树节点的数量（这可以通过检查展开树势函数并进行大量代数来证明）。

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