algorithm - 优先搜索树困惑

Question

我找到的唯一合理的幻灯片集是this，在第15页中说，对于建筑：
按其x坐标值对所有点排序，并将它们存储在
平衡二叉树（即范围树）的叶节点
从根开始，每个节点在其子树中包含其未被存储的y坐标的最大值。
树中较浅的深度；如果不存在这样的节点，则节点
是空的
我实现了一个range treejust before，因此根据我在那里使用的示例，我现在有了（对于优先级搜索树）：

                             7
                      ------ 0 ---------------------
                      |                            |
                      6                            6
                ---- -3 ----                  ---- 4 ------ 
                |          |                  |           |
                4          2                  1           3
          ---- -4 -       -2              --- 3 ---       5
          |       |       / \             |       |      / \
          0    (-3,4) (-2,2)(0,7)        NIL   (4,-4) (5,3)(6,-1)
         -5                               2    
         / \                             / \
    (-5,6) (-4,0)                    (2,1) (3,6)

在这里，每个内部节点都是这样的：

mid_x
max y

我提出的范围查询是（-inf，1）x（-0.5，5），即（x_low，x_high）x（y_low，y_high）。
所以，让我们从根开始，检查x（=0）是否在（-inf，1）中
如果7>（-0.5，5）是的，因此我在两个孩子身上继续，但是
简单点，让我跟着左一个（从现在开始）。
我检查-3是否为x范围，以及6是否大于或等于
查询y范围的上限（即5）。是的，所以我
继续。
下一层也一样，所以我们要上一层，现在请
关注这个内部节点它的最大y值为0，这表示
子树的最大y为0，这是不正确的（左子树是
（-5，6））*。
在构建/搜索过程中我遗漏了什么？
换句话说：
检查树的最左边的分支；它有as max_y值（引号中的第二个项目符号），7、6、4、0。
但是，这个值不是指示在内部节点下的子树中存储的最大Y值的值吗？如果是，则对于 0和点 (-5, 6)（6不使用，因为它用于第2级）。
*我提出的特定查询可能不会因此而损坏，但另一个可能会损坏。

Answer 1

你最后的逻辑还是正确的。当您点击标记为（6，-3）的节点时，-5,6）值应该已经被拾取。
现在，我不是数学专业的学生但总的来说是这样的。在您实现的优先级搜索树中，实际上是在搜索两个独立的条件。
对于x，这是对范围的简单二进制搜索。
对于y，您实际上是将其作为优先级树进行搜索（适合搜索y:inf或-inf:y，这取决于您使用的是max还是min）
注意，在第15页的底部，它指出树适合于半无限范围（一个是无限的）。继续往下读，你会看到树是如何为y的半无限范围优化的。
简而言之，由于树是以x作为二进制搜索，y作为优先级（使用最大剩余值）构建的，因此最佳搜索是[x1:x2]，[y1:inf]。
树中的每个节点实际上存储了两个东西。
一。x的中点（或左树中的max-x，以及向左或向右遍历的决定基于>x检查）。
2子树中y值最高的点，它没有被加到上一个子树中。
搜索算法基本上是这样的从根开始，使用[x1:x2]，[y1:inf]条件
一。检查指定给节点的点的y值。如果y>y1，则转到2，否则停止向下遍历（因为指定给节点的点具有最高的y值，如果检查失败，则其下没有其他节点可以完成[y1:inf]。
2检查点的x值是否在[x1:x2]范围内如果是，请在输出中包含该点继续执行步骤3，无论是否包含该点。
三。检查节点的“中点”值（我们称之为mx）。如果mx在[x1:x2]范围内，则沿两条路径遍历如果mx小于[x1:x2]，则向左移动。否则向右移动。对于所遍历的每个路径，请返回到步骤1。
编辑非常长的文本：
让我们来看看你的例子。我用字母（点的“名称”）对每个点做了额外的注释。现在，每个节点都具有点的名称格式，其y值在父项中，其下方的“中间范围”x。对于叶节点，那些带有“*”的节点意味着它们已经被分配到树的某个位置，如果到达它们，应该被视为零。

                              7(E)
                       ------ 0 ---------------------
                       |                            |
                      A(6)                         G(6)
                 ----- -3 -----                  ---- 4 -------- 
                 |            |                  |             |
                 C(4)        D(2)               F(1)          I(3)
           ---- -4 -         -2              --- 3 ---         5
           |       |         / \             |       |        / \
           B(0)  C*(-3,4)D*(-2,2)E*(0,7)     NIL   H(4,-4) I*(5,3)J(6,-1)
          -5                                 2   
          / \                               / \
    A*(-5,6)B*(-4,0)                   F*(2,1) G*(3,6)

让我们运行一个示例查询[-2:4][1:inf]（或任何y>=1）
从根开始，我们看到E点。
点E（7）的y是否大于等于1对。
E（0）点的X是否在[-2:4]中？是的
将e添加到输出。
中点（也是0）在范围内吗？是的
从E节点开始，需要穿过两边。
首先，我们向左走，我们看到A点。
点a（6）的y是否大于等于1？对。
点A（-5）的x是否在[-2:4]中不。
跳过a，但继续遍历（仅y检查停止遍历）。
中点在[-2:4]范围内吗不，在左边。
由于-3<[-2:4]，我们只需要向右移动现在我们看到d点。
点d（2）的y是否大于等于1？不！跳过该点并停止向下遍历，因为在d下没有我们没有输出的其他点（注意，即使e低于d，当我们在开始访问根时，e已经输出）。
我一直走到A，因为我们不需要走左边的路，继续走。
现在我又回到了根目录，这两个目录都需要遍历既然我们走左边，我们就走右边。这里，我们看到G点
点G（6）的y是否大于等于1是的
点g（3）的x是否在[-2:4]中？是的
把G加到输出，现在我们有了（E，G）。
G的中点在范围内吗？是的，我们必须穿过两边。
我们先向左走。我们看到f。
点f（1）的y是否大于等于1？是的
f（2）点的x是否在[-2:4]中？是的
把f加到输出，现在我们有（e，f，g）
中间点是f在[-2:4]吗？是的，我们必须穿过两边。
我们再往左拐，看…没有。下面没有要添加的点（因为我们之前已经检查/添加了f，g）。
让我们回到F然后沿着右边走，我们看到H。
点H（-4）的y是否大于等于1不。不要添加点，停止遍历。
我们回到f，它已经穿越了两条路径。
我们回到G，它仍然需要正确的路径遍历。
我们沿着这条路走，看到我。
点I（3）的y是否大于等于1是的
点I（5）的x是否在[-2:4]中不。
跳过f。
在I处的中点在[-2,4]范围内吗不，它更大。
因为它更大，我们只需要穿过左边，所以让我们这样做。
沿着左边走我们看到…我，再一次。因为我们已经看到了我，它是一个叶节点，所以我们停止遍历并返回到i。
我说完了（不需要向右走）。回到G。
G完成（两边横过）。回到E。
完成（两边都穿过）既然E是根节点，我们现在就结束了。
结果是“e，f，g”在范围内。