用於處理時間間隔的數據結構

Question

我得到了一系列不能重疊的時間間隔（t_start，t_end），即：t_end（i）> t_start（i + 1）。我想要做以下操作：

1）增加新的聯合區間[{（1,4），（8,10）} U（3,7）= {（1,7），（ 8））]]
2）取出間隔[（1,7） - （3,5）= {（1,3），（5,7）}
3）檢查點或間隔與我的系列中的區間重疊（交叉點）
4）在某點之後找到最小長度的第一個「非區間」[{（1,4），（7,8）}：間隔「長度3在4和7之間]。

我想知道實現這一點的好方法，而且複雜度低（所有操作都需要logn）。

相關問題：Data structure for quick time interval look up

Answer 1

這聽起來像你可以只使用所有邊界時間的平衡二叉樹。

例如，表示{（1,4），（8,10），（12,15）}爲含有1，4，8，10，12，和15

每個節點樹需要說明是否是間隔的開始或結束。所以：

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

（這裏所有的「結束」節點結束了在偶然的底部。）

那麼我想你可以有你所有的操作在O（log n）的時間。 要添加間隔：

• 查找的開始時間。如果它已經在樹中作爲開始時間，則可以將其留在那裏。如果它已經在樹中作爲結束時間，您將要刪除它。如果它不在樹和中，它不會在現有時間間隔內下降，您需要添加它。否則，你不想添加它。

• 找到停止時間，使用相同的方法來確定是否需要添加它，刪除它或兩者都不。

• 現在，您只需添加或刪除上述的啓動和停止節點，同時刪除兩者之間的所有現有節點。要做到這一點，你只需要重建樹節點，或者直接在樹中的那兩個地方重建。如果樹的高度是O（log n），可以通過使用平衡樹來保證，這需要O（log n）時間。

（免責聲明：如果你在C++和做明確的內存管理，你可能最終爲你做到這一點爲O釋放更多（log n）的內存條，但真正花費的時間來釋放我認爲，應該向任何人添加節點。）

刪除間隔在很大程度上是相同的。

檢查點或間隔很簡單。

至少找到一個給定尺寸的第一間隙給定的時間後，可以在O（log n）的得做，如果你還緩存信息的兩個片段，每個節點：

• 在每個起始節點（最左邊除外）中，間隙的大小緊挨着左邊。

• 在每個節點中，出現在該子樹中的最大差距的大小。

要查找給定時間之後出現的給定大小的第一個間隙，請先在樹中查找該時間。然後走直到你到達一個聲稱包含足夠大間隙的節點。如果你從右邊出現，你知道這個差距在左邊，所以你忽略它並繼續走下去。否則，你從左邊來。如果節點是開始節點，請檢查左側的間隙是否足夠大。如果是這樣，你就完成了。否則，足夠大的差距必須在正確的位置。向下走向右邊，繼續向下，直到找到缺口。再次，因爲樹的高度是O（log n），所以走三次（向下，向上，可能再次向下）是O（log n）。

Answer 2

不知道細節了，我建議你閱讀Interval Trees。間隔樹是一種特殊的一維情況，具有更通用的kd-trees，並且具有O(n log n)構建時間和O(log n)典型操作時間。您需要找到自己需要的確切算法實現，但您可以從CGAL開始。

Answer 3

我知道你已經接受了答案，但既然你表示你可能會用C++實現，你還可以看看Boosts Interval Container Library（http://www.boost.org/doc/libs/1_46_1/libs/icl/doc/html/index.html）。

Answer 4

我的區間樹實現與AVL樹。

public class IntervalTreeAVL<T>{ 
    private static class TreeNode<T>{ 
     private T low; 
     private T high; 
     private TreeNode<T> left; 
     private TreeNode<T> right; 
     private T max; 
     private int height; 
     private TreeNode(T l, T h){ 
      this.low=l; 
      this.high=h; 
      this.max=high; 
      this.height=1; 
     } 
    } 
    private TreeNode<T> root; 
    public void insert(T l, T h){ 
     root=insert(root, l, h); 
    } 
    private TreeNode<T> insert(TreeNode<T> node, T l, T h){ 
     if(node==null){ 
      return new TreeNode<T>(l, h); 
     } 
     else{ 
      int k=((Comparable)node.low).compareTo(l); 
      if(k>0){ 
       node.left=insert(node.left, l, h); 
      } 
      else{ 
       node.right=insert(node.right, l, h); 
      } 
      node.height=Math.max(height(node.left), height(node.right))+1; 
      node.max=findMax(node); 
      int hd = heightDiff(node); 
      if(hd<-1){ 
       int kk=heightDiff(node.right); 
       if(kk>0){ 
        node.right=rightRotate(node.right); 
        return leftRotate(node); 
       } 
       else{ 
        return leftRotate(node); 
       } 
      } 
      else if(hd>1){ 
       if(heightDiff(node.left)<0){ 
        node.left = leftRotate(node.left); 
        return rightRotate(node); 
       } 
       else{ 
        return rightRotate(node); 
       } 
      } 
      else; 
     } 
     return node; 
    } 
    private TreeNode<T> leftRotate(TreeNode<T> n){ 
     TreeNode<T> r = n.right; 
     n.right = r.left; 
     r.left=n; 
     n.height=Math.max(height(n.left), height(n.right))+1; 
     r.height=Math.max(height(r.left), height(r.right))+1; 
     n.max=findMax(n); 
     r.max=findMax(r); 
     return r; 
    } 
    private TreeNode<T> rightRotate(TreeNode<T> n){ 
     TreeNode<T> r = n.left; 
     n.left = r.right; 
     r.right=n; 
     n.height=Math.max(height(n.left), height(n.right))+1; 
     r.height=Math.max(height(r.left), height(r.right))+1; 
     n.max=findMax(n); 
     r.max=findMax(r); 
     return r; 
    } 
    private int heightDiff(TreeNode<T> a){ 
     if(a==null){ 
      return 0; 
     } 
     return height(a.left)-height(a.right); 
    } 
    private int height(TreeNode<T> a){ 
     if(a==null){ 
      return 0; 
     } 
     return a.height; 
    } 
    private T findMax(TreeNode<T> n){ 
     if(n.left==null && n.right==null){ 
      return n.max; 
     } 
     if(n.left==null){ 
      if(((Comparable)n.right.max).compareTo(n.max)>0){ 
       return n.right.max; 
      } 
      else{ 
       return n.max; 
      } 
     } 
     if(n.right==null){ 
      if(((Comparable)n.left.max).compareTo(n.max)>0){ 
       return n.left.max; 
      } 
      else{ 
       return n.max; 
      } 
     } 
     Comparable c1 = (Comparable)n.left.max; 
     Comparable c2 = (Comparable)n.right.max; 
     Comparable c3 = (Comparable)n.max; 
     T max=null; 
     if(c1.compareTo(c2)<0){ 
      max=n.right.max; 
     } 
     else{ 
      max=n.left.max; 
     } 
     if(c3.compareTo((Comparable)max)>0){ 
      max=n.max; 
     } 
     return max; 
    } 


TreeNode intervalSearch(T t1){ 
     TreeNode<T> t = root; 
     while(t!=null && !isInside(t, t1)){ 
      if(t.left!=null){ 
        if(((Comparable)t.left.max).compareTo(t1)>0){ 
        t=t.left; 
       } 
       else{ 
        t=t.right; 
       } 
      } 
      else{ 
       t=t.right; 
      } 
     } 
     return t; 
    } 
    private boolean isInside(TreeNode<T> node, T t){ 
     Comparable cLow=(Comparable)node.low; 
     Comparable cHigh=(Comparable)node.high; 
     int i = cLow.compareTo(t); 
     int j = cHigh.compareTo(t); 
     if(i<=0 && j>=0){ 
      return true; 
     } 
     return false; 
    } 
} 

Answer 5

我只是發現Guava's Range和RangeSet它這樣做。

它實現所有操作引用：

1. 聯盟

   RangeSet<Integer> intervals = TreeRangeSet.create(); 
   intervals.add(Range.closedOpen(1,4)); // stores {[1,4)} 
   intervals.add(Range.closedOpen(8,10)); // stores {[1,4), [8,10)} 
   // Now unite 3,7 
   intervals.add(Range.closedOpen(3,7)); // stores {[1,7), [8,10)} 
   

2. Subraction

   intervals.remove(Range.closedOpen(3,5)); //stores {[1,3), [5, 7), [8, 10)} 
   

3. 路口

   intervals.contains(3); // returns false 
   intervals.contains(5); // returns true 
   intervals.encloses(Range.closedOpen(2,4)); //returns false 
   intervals.subRangeSet(Range.closedOpen(2,4)); // returns {[2,3)} (isEmpty returns false) 
   intervals.subRangeSet(Range.closedOpen(3,5)).isEmpty(); // returns true 
   

4. 尋找空的空間（這將是相同的複雜性，因爲在最壞情況下的一組迭代）：

   Range freeSpace(RangeSet<Integer> ranges, int size) { 
       RangeSet<Integer> frees = intervals.complement().subRangeSet(Range.atLeast(0)); 
       for (Range free : frees.asRanges()) { 
        if (!free.hasUpperBound()) { 
         return free; 
        } 
        if (free.upperEndpoint() - free.lowerEndpoint() >= size) { 
         return free; 
        } 
       }