间隔树算法，支持区间合并没有重叠 [英] Interval tree algorithm that supports merging of intervals with no overlap

问题描述

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

I'm looking for an interval tree algorithm similar to the red-black interval tree in CLR but that supports merging of intervals by default so that there are never any overlapping intervals.

在换句话说，如果你有一个包含两个区间[2,3]和[5,6]一棵树，你添加的区间[4,4]，其结果必然是包含只是一个区间树[2,6 ]。

In other words if you had a tree containing two intervals [2,3] and [5,6] and you added the interval [4,4], the result would be a tree containing just one interval [2,6].

感谢

更新：使用情况下，我在考虑是计算传递闭包。间隔套用于存储所述后继集，因为他们已经发现是相当紧凑的。但是，如果你重新present区间集只是作为一个链表我已经发现，在某些情况下，它们会变得相当大，因此也是如此查找插入点所需的时间。因此，我在间隔树的兴趣。也有可能是相当多的合并一棵树与另一个（即一组或操作） - 如果两个树大那么它可能是更好的创建使用序这两个目录树的阶层，而不是每个区间的重复插入一个新的树。

Update: the use case I'm considering is calculating transitive closure. Interval sets are used to store the successor sets because they have been found to be quite compact. But if you represent interval sets just as a linked list I have found that in some situations they can become quite large and hence so does the time required to find the insertion point. Hence my interest in interval trees. Also there may be quite a lot of merging one tree with another (i.e. a set OR operation) - if both trees are large then it may be better to create a new tree using inorder walks of both trees rather than repeated insertions of each interval.

推荐答案

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

The problem I see is that inserting a large interval can wipe out a large chunk of the tree, making it difficult to recover the red-black invariants.

我认为这将是更容易使用伸展树，如下所示。为简单起见，每棵树包含两个哨兵，间隔 A 所有其他区间的左侧，间隔以Z 来正确的。当插入一个间隔我，张开我的predecessor将要 ^ h 树的根。树看起来像

I think it would be easier to use a splay tree, as follows. For simplicity, each tree contains two sentinels, an interval A to the left of all other intervals and an interval Z to the right. When inserting an interval I, splay I's predecessor-to-be H to the root of the tree. The tree looks like

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

现在分离 X 和张开我的继任者将要Ĵ根。

Now detach X and splay I's successor-to-be J to the root.

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

在这一点上所有的重叠的间隔我在Ĵ的左子树。分离的子树，并把所有的空闲列表上的节点，延长我，如果必要的。让我 H的父和Ĵ

At this point all of the intervals that overlap I are in J's left subtree. Detach that subtree and put all of its nodes on the free list, extending I if necessary. Make I the parent of H and J

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

和继续我们的快乐的方式。这个操作是O（log n）的摊销，其中n是树节点的数量（这可以通过检查伸展树的潜在功能，并做了很多代数的证明）。

and continue on our merry way. This operation is O(log n) amortized, where n is the number of tree nodes (this can be proved by examining the splay tree potential function and doing a lot of algebra).

我要补充一点，有通过将一棵树的根，然后将左，右子树合并自然的递归树，以树合并。我不知道如何去分析它的副手。

I should add that there's a natural recursive tree-to-tree merge by inserting the root of one tree and then merging the left and right subtrees. I don't know how to analyze it off-hand.

这篇关于间隔树算法，支持区间合并没有重叠的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！