数据结构的处理间隔 [英] Data structure for handling intervals

问题描述

我有一系列时间间隔（t_start，t_end），这是不能重叠，即：t_end（ⅰ）> t_start第（i + 1）。我想要做如下操作：

1）添加新的（​​联盟）区间[{（1,4），（8,10）} U（3,7）= {（1,7），（8,10）}]
2）取出来的时间间隔[（1,7） - （3,5）= {（1,3），（5,7）}
3）检查是否有一个间隔在我的系列中的点或区间重叠（交叉点）
4）寻找第一个非间隔的最小长度的某一点后[{（1,4），（7,8）}：有4〜7非间隔长度为3] <。 / P>

我想知道，实施这个，低复杂性（日志N的所有操作将做到这一点）的好方法。

相关问题：<一href="http://stackoverflow.com/questions/1580185/data-structure-for-quick-time-interval-look-up">http://stackoverflow.com/questions/1580185/data-structure-for-quick-time-interval-look-up

解决方案

这听起来像你可以只使用一个平衡二叉树所有边界时代。

例如，重新present {（1,4），（8,10），（12,15）}作为含有树1，4，8，10，12，和15。

每个节点需要说是否这是一个间隔的开始或结束。所以：

  8（开始）
                         / \
                1（开始）12（启动）
                      \ / \
                     4（结束）10（完）15（完）
 

（这里所有的端节点结束了在偶然的底部。）

那么我想你可以有你所有的操作在O（log n）的时间。 要添加间隔

• 查找的开始时间。如果它已经在树作为开始的时候，你可以离开它。如果它已经存在于树作为结束时间，你想删除它。如果它不是在树中的和的它并没有一个现有的间隔期间下降，你会希望添加它。否则，你不希望添加它。

• 查找的停止时间，用同样的方法，看看是否需要添加，删除，或两者都不是。

• 现在你只需要添加或删除上述的启动和停止节点，并在同一时间，删除之间的所有现有节点。要做到这一点，你只需要重建树节点的在或正上方的树这两个地方。如果树的高度为O（log n）的，您可以通过使用平衡树保障，这需要O（log n）的时间。

（声明：如果你在C ++和做明确的内存管理，你可能最终为O释放更多（log n）的内存条，你做到这一点，但真的需要时间去释放一个节点应该是宣传为谁加了，我想。）

删除间隔在很大程度上是相同的。

检查点或间隔是简单的。

查找至少给定尺寸的第一间隙给定的时间可以在O完成后（log n）的太多，如果你还缓存两个部分，每节点信息：

• 在每个启动节点（比最左边的除外），紧接间隙向左大小

• 在每个节点中，最大的差距出现在该子树的大小。

要找到一个给定的时间后出现一个给定大小的第一个缺口，先找到当时在树上。然后走上去，直到你达到这个声称含有足够大的差距的一个节点。如果你从右边来了，你知道这种差距是向左，让你忽略它，继续走了。否则，你就从左边。如果该节点是一个起始节点，检查是否该间隙到其左边是足够大。如果是这样，你就大功告成了。否则，足够大的间隙必须某处到右侧。走下向右并延续下来，直到你找到的差距。同样，因为树的高度为O（log n）的，走了三遍（向下，向上，并有可能再次下行）为O（log n）的。

I have got a series of time intervals (t_start,t_end), that cannot overlap, i.e.: t_end(i) > t_start(i+1). I want to do the following operations:

1) Add new (Union of) intervals [ {(1,4),(8,10)} U (3,7) = {(1,7),(8,10)} ]
2) Take intervals out [ (1,7) - (3,5) = {(1,3),(5,7)}
3) Checking whether a point or a interval overlaps with an interval in my series (intersection)
4) Finding the first "non-interval" of a minimum length after some point [ {(1,4),(7,8)}: there is a "non-interval" of length 3 between 4 and 7 ].

I want to know good ways of implementing this, with low complexities (log n for all operations would do it).

Related question: http://stackoverflow.com/questions/1580185/data-structure-for-quick-time-interval-look-up

解决方案

It sounds like you could just use a balanced binary tree of all the boundary times.

For example, represent {(1,4), (8,10), (12,15)} as a tree containing 1, 4, 8, 10, 12, and 15.

Each node needs to say whether it's the start or end of an interval. So:

                          8 (start)
                         /        \
                1 (start)         12 (start)
                      \             /      \
                     4 (end)   10 (end)   15 (end)

(Here all the "end" nodes ended up at the bottom by coincidence.)

Then I think you can have all your operations in O(log n) time. To add an interval:

• Find the start time. If it's already in the tree as a start time, you can leave it there. If it's already in the tree as an end time, you'll want to remove it. If it's not in the tree and it doesn't fall during an existing interval, you'll want to add it. Otherwise you don't want to add it.

• Find the stop time, using the same method to find out if you need to add it, remove it, or neither.

• Now you just want to add or remove the abovementioned start and stop nodes and, at the same time, delete all the existing nodes in between. To do this you only need to rebuild the tree nodes at or directly above those two places in the tree. If the height of the tree is O(log n), which you can guarantee by using a balanced tree, this takes O(log n) time.

(Disclaimer: If you're in C++ and doing explicit memory management, you might end up freeing more than O(log n) pieces of memory as you do this, but really the time it takes to free a node should be billed to whoever added it, I think.)

Removing an interval is largely the same.

Checking a point or interval is straightforward.

Finding the first gap of at least a given size after a given time can be done in O(log n) too, if you also cache two more pieces of information per node:

• In each start node (other than the leftmost), the size of the gap immediately to the left.

• In every node, the size of the largest gap that appears in that subtree.

To find the first gap of a given size that appears after a given time, first find that time in the tree. Then walk up until you reach a node that claims to contain a large enough gap. If you came up from the right, you know this gap is to the left, so you ignore it and keep walking up. Otherwise you came from the left. If the node is a start node, check to see if the gap to its left is large enough. If so, you're done. Otherwise, the large-enough gap must be somewhere to the right. Walk down to the right and continue down until you find the gap. Again, because the height of the tree is O(log n), walking it three times (down, up, and possibly down again) is O(log n).

这篇关于数据结构的处理间隔的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！