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

Question

间隔由开始和结束定义。

给定一组可能重叠的区间（例如，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

Answer 1

写了一些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);
    }




}

Answer 2

这个问题的数据结构叫做区间树：

一个有序的树数据结构来保存区间，它允许人们有效地找到与任何给定区间或点重叠的所有区间。

两种有效的方法：

• 使用扩充树
• 使用面向中间或长度的树

在搜索所有重叠区间的链接中，所提出的算法预计比传统的区间树（增强树）搜索操作更快，添加元素稍慢。

实现间隔树的各种方法：

• Standford在通用实用程序包edu.stanford.nlp.util中实现了IntervalTree，并提供了许多有用的方法

当实现一个解决方案时，你应该知道java集合处理的性能