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

Question

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

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

谢谢

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

Answer 1

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

我认为使用展开树会更容易，如下所示。为简单起见，每棵树包含两个哨兵，一个区间 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 是树节点的数量（这可以通过检查展开树势函数并进行大量代数来证明）。

---

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