如何构建数据结构以支持某些范围查询

给定一组可能重叠的间隔的范围内[说，0-999]，构建的数据结构以支持在最佳时间复杂

以下范围的查询。

重叠（开始，结束） =集与[开始，结束]

在（开始，结束） =组位于内的所有时间间隔重叠的所有间隔的[开始，结束]

其中，

Intervals I1[start1, end1], I2[start2, end2] are said to overlap with each other iff start1<end2 && start2<end1 
Interval I1[start1, end1] is said to be within interval I2[start2,end2] iff start1>start2 && end1<end2

来源

2015-05-25 Identity1

@Laurentiu L.你能否解释一下这个问题产生的数据结构应该是什么样的目标？ – Identity1

@LaurentiuL。我知道范围查询将返回上面提到的一组时间间隔。但是数据结构（假设Array）的外观如何？我可以编写范围查询逻辑，但我不确定数据结构的外观如何。你能展示一个样本吗？ – Identity1

当我首先写下这个问题时，部分问题就不存在了。现在，这证明你们不知道我在问什么，并推测我想要一个解决方案。你甚至没有正确阅读我的问题。请不要无理由评论。 – Identity1

写了一些Scala代码来实现这一点使用区间的树！

class IntervalSearchTree { 
    var root=new IntervalNode(null,null,null,null,null); 

    class IntervalNode(var left:IntervalNode,var start:Integer,var end:Integer,var maxEnd:Integer,var right:IntervalNode); 

    def add(start:Integer,end:Integer):Unit={ 
     var node:IntervalNode=root 
     while(node!=null){ 
     if(end>node.maxEnd) 
      node.maxEnd=end 
     if (start < node.start) { 
       if (node.left == null) { 
        node.left = new IntervalNode(null, start, end, end, null); 
        return; 
       } 
       node = node.left; 
      } else { 
       if (node.right == null) { 
        node.right = new IntervalNode(null, start, end, end, null); 
        return; 
       } 
       node = node.right; 
      } 
     } 
     root = new IntervalNode(null, start, end, end, null); 
    } 

    def overlap(start:Integer,end:Integer):Unit={ 

     var intervalNode:IntervalNode=root; 
     while (intervalNode != null) { 
     if (intersection(start, end, intervalNode)){ 
      println(intervalNode.start+"-"+intervalNode.end) 
     } 
     if (leftSubTree(start, end, intervalNode.left)) { 
       intervalNode = intervalNode.left; 


      } else { 

       intervalNode = intervalNode.right; 

      } 


     } 

    } 

    def within(start:Integer,end:Integer):Unit={ 
     var intervalNode:IntervalNode = root; 
     while (intervalNode != null) { 
      if (subset(start, end, intervalNode)){ 
      println(intervalNode.start+"-"+intervalNode.end) 
     } 
     if (leftSubTree(start, end, intervalNode.left)) { 
       intervalNode = intervalNode.left; 


      } else { 

       intervalNode = intervalNode.right; 

      } 
     } 

    } 


    def subset(start:Integer,end:Integer,intervalNode:IntervalNode):Boolean={ 
     return start<intervalNode.start && end >intervalNode.end ; 
    } 

    def intersection(start:Integer,end:Integer,intervalNode:IntervalNode):Boolean={ 
     return start < intervalNode.end && end > intervalNode.start; 
    } 

    def leftSubTree(start:Integer,end:Integer,intervalLeftSubtree:IntervalNode):Boolean={ 
     return intervalLeftSubtree != null && intervalLeftSubtree.maxEnd > start; 
    } 


    def main(args: Array[String]): Unit = { 
     var intervalSearchTree=new IntervalSearchTree() 
     intervalSearchTree.add(17, 19); 
     intervalSearchTree.add(5, 8); 
     intervalSearchTree.add(21, 24); 
     intervalSearchTree.add(22, 24); 
     intervalSearchTree.add(20, 26); 
     intervalSearchTree.add(20, 24); 
     intervalSearchTree.add(4, 8); 
     intervalSearchTree.add(5, 9); 
     intervalSearchTree.add(15, 18); 
     intervalSearchTree.add(7, 10); 
     intervalSearchTree.add(16, 22); 

     //Input for testing overlaps 
     println("Overlaps"); 
     intervalSearchTree.overlap(23, 25); 
     //Input for testing overlaps 
     println("Within"); 
     intervalSearchTree.within(4, 25); 
    } 




}

来源

2015-05-27 12:34:39 Identity1