1

我找到的唯一合理的幻灯片集是this，在第 15 页中说，用于构建：

  • 将所有点按其 x 坐标值排序，并将它们存储在平衡二叉树（即范围树）的叶节点中
  • 从根开始，每个节点都包含其子树中的点，其 y 坐标的最大值尚未存储
    在树中较浅的深度；如果不存在这样的节点，则节点
    为空

我之前实现了一个范围树，所以根据我在那里使用的示例，我现在有（对于优先搜索树）：

                             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）。

  1. 所以，让我们从根开始，我检查 x (=0) 是否在 (-inf, 1) 中，如果 7 > (-0.5, 5)。是的，因此我在两个孩子中进行，但为简单起见，让我跟随左边的孩子（从现在开始）。
  2. 我检查 -3 是否是 x 范围，以及 6 是否大于或等于查询的 y 范围的上限（即 5）。是的，所以我继续。
  3. 下一层也一样，因此我们进入下一层，现在请关注这个内部节点。它有 as max ya 0，表示子树的最大 y 为 0，这是不正确的（左孩子为 (-5, 6)) *。

我在构建/搜索过程中缺少什么？

换句话说：

检查树的最左边的分支；它的max_y值（引用中的第 2 个项目符号）为 7、6、4、0。

但是那个值不是表示存储在内部节点下的子树中的最大 y 值吗？0如果是这样，这对于和点不成立(-5, 6)（不使用 6，因为它用于第 2 级）。

*我提出的特定查询可能不会因此而受损，但另一个可以。

4

1 回答 1

2

你最后的逻辑其实还是正确的。当您点击标记为 (6,-3) 的节点时，应该已经拾取了 (-5,6) 值。现在，我不是数学专业的。但总体思路是这样的。在您实施的优先搜索树中，您实际上是在两个单独的条件上进行搜索。对于 x，它是对范围的简单二分搜索。对于 y，您实际上是在将其作为优先级树进行搜索（适合搜索 y:inf 或 -inf:y，具体取决于您使用的是 max 还是 min。）

请注意，在第 15 页的底部，它声明树适用于半无限范围（一个是无限的）。继续往下读，你会看到树是如何针对 y 的半无限范围进行优化的。

简而言之，由于您的树是使用 x 作为二分搜索和 y 作为优先级（使用最大剩余值）构建的，因此最佳搜索是 [x1:x2],[y1:inf]。

树中的每个节点本质上存储 2 个东西。1、x的中点（或者是左树中的max-x，左右遍历的决定是基于>x检查）。2. 子树中未添加到前一个的 y 值最高的 POINT。

搜索算法本质上是这样的。从根开始，使用标准 [x1:x2], [y1:inf] 1. 检查分配给节点的 POINT 的 y 值。如果y > y1，则执行2，否则停止向下遍历（由于分配给节点的POINT具有最高的y值，如果检查失败，则其下方没有其他节点可以满足[y1：inf]。2.检查如果该点的 x 值在 [x1:x2] 范围内。如果是，则将该点包含在输出中。无论您是否包含该点，都继续执行步骤 3。3. 检查节点的“中点”值（我们称它为 mx）。如果 mx 在 [x1:x2] 的范围内，则沿两条路径遍历。如果 mx < [x1:x2]，则向左遍历。否则向右遍历。为您的每条路径返回步骤 1遍历。

编辑非常非常长的文本：让我们来看看你的例子。我已经使用字母（点的“名称”）标记了每个点。每个节点现在都有点名称的格式，括号中是 y 值，下方是“中间范围”x。对于叶节点，带有“*”的节点表示它们已经分配到树上的某个位置，如果您到达它们，则应将其视为 NIL。

                              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 检查停止遍历）。
  • A 的中点是否在 [-2:4] 的范围内？不，在左边。
  • 由于 -3 < [-2:4]，我们只需要向右遍历。现在我们看到 D 点。
  • 点 D(2) 的 y >= 1 吗？不！跳过该点并停止向下遍历，因为在 D 下没有其他点我们没有输出（注意，即使 E 在 D 之下，当我们开始访问 root 时已经输出了 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)
  • 中点是 [-2:4] 中的 F 吗？是的，我们必须穿越两边。
  • 让我们再次向左走，我们看到... NIL。下面没有要添加的点（因为我们之前已经检查/添加了 F，G）。
  • 让我们回到 F 并沿着右侧向下移动，我们看到 H。
  • H点的y (-4) >= 1？不，不要添加点并停止遍历。
  • 我们回到 F，它已经遍历了两条路径。
  • 我们回到 G，它仍然需要它的正确路径遍历。
  • 我们沿着正确的路径走，看到我。
  • 点 I (3) 的 y >= 1 吗？是的
  • 点 I (5) 的 x 在 [-2:4] 中吗？不。
  • 跳过 F。
  • I 处的中点是否在 [-2,4] 范围内？不，更大。
  • 既然比较大，我们只需要遍历左边，就这样吧。
  • 遍历左侧，我们看到......我，再次。由于我们已经看到了 I，并且它是一个叶节点，我们停止遍历并返回到 I。
  • 我完成了（不需要向右遍历）。回到 G。
  • G 完成（两边都遍历）。回到 E。
  • E 完成（两边都遍历）。由于 E 是根节点，我们现在完成了。

结果是“E,F,G”在范围内。

于 2016-05-14T05:00:06.980 回答