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

Question

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

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

谢谢

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

- Dave Griffiths

---

我已经删除了我的回答，因为我愚蠢地忽略了一些情况。虽然仍然有可能修复，但会变得更加复杂。无论如何，既然你更新了说你将主要合并整个树，那么这个答案似乎不再有用，因为中序遍历会更快。 - interjay

好的。有时候当我合并两个大树时inorder可能会更快，但更多的情况下我会将小树添加到大树中。 - Dave Griffiths

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是树节点数（可以通过检查伸展树潜力函数并进行大量代数运算来证明）。

---

我应该补充说，有一种自然的递归树到树合并方法，即先插入一个树的根节点，然后合并左右子树。我不知道如何立即分析它。

- user287792