代码之家 › 专栏 › 技术社区 › Luís Guilherme

处理时间间隔的数据结构

intervals tree data-structures algorithm

Luís Guilherme · 技术社区 · 16 年前

我有一系列不能重叠的时间间隔(t_开始,t_结束),即:t_结束(I)>t_开始(i+1)。我要执行以下操作:

1) 添加新的(并集)区间[{(1,4)、(8,10)}U(3,7)={(1,7)、(8,10)}]
2) 将间隔取出[(1,7)-(3,5)={(1,3),(5,7)}

4) 在某个点[{(1,4)、(7,8)}之后找到最小长度的第一个“非间隔”:在4和7之间有一个长度为3的“非间隔”。

5 回复 | 直到 9 年前

Jason Orendorff Oliver 16 年前

听起来你只需要一个 平衡二叉树

例如,将{(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(logn),这可以通过使用平衡树来保证,这需要O(logn)时间。

(免责声明:如果你在C++中做了明确的内存管理,你可能最终释放出比O(log n)多的内存块,但实际上,释放一个节点需要花费多少钱给那些添加它的人,我想。)

删除间隔 基本上是一样的。

检查点或间隔 这是直截了当的。

在给定时间后找到至少一个给定大小的第一个间隙

在每个开始节点(除最左侧节点外)中,间隙的大小直接向左。
在每个节点中,显示在该子树中的最大间隙的大小。

要查找给定时间后出现的给定大小的第一个间隙,请首先在树中查找该时间。然后向上走,直到到达声称包含足够大间隙的节点。如果你从右边上来,你知道这个缺口在左边,所以你忽略它,继续往上走。否则你是从左边来的。如果节点是起始节点,请检查其左侧的间隙是否足够大。如果是这样,你就完了。否则,足够大的间隙必须位于右侧的某个位置。向右走,然后继续往下走,直到找到缺口。同样,因为树的高度是O(logn),所以走三次(向下,向上,可能再向下)就是O(logn)。

Kornel Kisielewicz 16 年前

Interval Trees . 区间树是一种特殊的一维更一般的情况 kd-trees ,并有一个 O(n log n) 施工时间,以及 O(log n) CGAL .

jsherer 15 年前

我知道你已经接受了一个答案,但是既然你指出你可能会在C++中实现,你也可以看看升空间隔容器库。 http://www.boost.org/doc/libs/1_46_1/libs/icl/doc/html/index.html

Trying 12 年前

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;
    }
}

Luís Guilherme 12 年前

Guava's Range 和 RangeSet

它执行所有引用的操作:

联合

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)}

副作用

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

交叉

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

查找空空间(在最坏的情况下,这与集合迭代的复杂性相同):

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;
        }
    }