范围树实现

Question

我试图实施一系列树，但我真的很困惑，这里是我的文字：

现在假设我有一个这样的树：

我想找到14点和19点之间的点。V_Split在此处为17，根据算法从17移动到14，我应该报告17和23的正确子树。但23不在1之间4和19。我应该在这里做什么？

如果我不考虑17，那么17本身不会被报告。然后再次如果我想找到12和19之间的点，14将不会被包括在内！

Answer 1

前一段时间，我实现了维基百科的Range Tree文章（范围查询部分）中描述的步骤，这些看起来像您的文本。主要想法是找到vsplit点，然后二分搜索vsplit的左侧和右侧孩子，在我们移动时抓住所有“范围内”节点。

我想保持数据结构（TreeNode）真正的基础，以使其更容易理解（因为我没有看到需要将每个节点存储为叶子，正如文章所建议的那样）。无论如何，下面你可以找到我的课程的主要方法，它包含了一步一步解释的一般想法。随意从我的github repository抓取整个代码，但我会建议先尝试自己编写getLeftNodes（）/ getRightNodes（）。

/** 
    * Range trees can be used to find the set of points that lay inside a given 
    * interval. To report the points that lie in the interval [x1, x2], we 
    * start by searching for x1 and x2. 
    * 
    * The following method will use a regular balanced binary search tree for 
    * this purpose. More info in https://en.wikipedia.org/wiki/Range_tree 
    * 
    * @param x1 
    *   Low (start) range position 
    * @param x2 
    *   High (end) range position 
    * @param root 
    *   A balanced binary search tree root 
    * @return 
    */ 
    public HashSet<Integer> getNodesInRange(int x1, int x2, TreeNode root) { 
     if (x1 >= x2) { 
      throw new IllegalArgumentException("Range error: x1 must be less than x2"); 
     } 

     // At some vertex in the tree, the search paths to x1 and x2 will 
     // diverge. Let vsplit be the last vertex that these two search paths 
     // have in common. 
     TreeNode vsplit = root; 
     while (vsplit != null) { 
      if (x1 < vsplit.data && x2 < vsplit.data) { 
       vsplit = vsplit.left; 
      } else if (x1 > vsplit.data && x2 > vsplit.data) { 
       vsplit = vsplit.right; 
      } else { 
       break; 
      } 
     } 

     // Report the value stored at vsplit if it is inside the query interval. 
     HashSet<Integer> nodesInRange = new HashSet<>(); 
     if (vsplit == null) { 
      return nodesInRange; 
     } else if (inRange(vsplit.data, x1, x2)) { 
      nodesInRange.add(vsplit.data); 
     } 

     // Continue searching for x1 in the range tree (vSplit to x1). 
     getLeftNodes(x1, x2, nodesInRange, vsplit.left); 
     // Continue searching for x2 in the range tree (vSplit to x2). 
     getRightNodes(x1, x2, nodesInRange, vsplit.right); 

     return nodesInRange; 
    } 

此实现的时间复杂度的目标应该是为O（log（n））的，因为我们在每一个所以做三个二进制搜索（VSPLIT +左+右）正在为O（log（n））的应该也体面有效。

编码这有助于我理解范围树的一般想法（在代码挑战中非常有用），我希望它对你也一样。

注意：我确定有更简单的实现（以及更高效的实现）！