优先搜索树混乱
Priority Search Tree confusion
我找到的唯一合理的幻灯片集是 this，在第 15 页上说，用于构建：
- Sort all points by their x coordinate value and store them in the
leaf nodes of a balanced binary tree (i.e., a range tree)
- Starting at the root, each node contains the point in its subtree with the maximum value for its y coordinate that has not been stored
at a shallower depth in the tree; if no such node exists, then node
is empty
我实现了范围树 ，所以根据我在那里使用的示例，我现在有（对于 优先搜索树）：
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)。是的，所以我在两个 children 中进行，但是对于
简单，让我跟着左边的（从现在开始所有情况下）。
- 我检查 -3 是否是 x 范围以及 6 是否大于或等于
查询的 y 范围的上限（即 5）。是的，所以我
继续。
- 下一关也一样，所以我们进入下一关，现在请
专注于这个内部节点。它的最大 y 为 0，这表明
子树的max y为0，这是不正确的（left child是
(-5, 6))*.
我在 building/searching 过程中遗漏了什么？
换句话说：
检查树最左边的分支；它具有 max_y 值（引号中的第二个项目符号），7、6、4、0。
但是那个值不是表示存储在内部节点下的子树中的最大y值的值吗？如果是这样，这不适用于0 和点 (-5, 6) （没有使用 6，因为它在第 2 级使用）。
*我提出的特定查询可能不会因此而损坏，但另一个可以。
你上次的逻辑其实还是对的。当您点击标记为 (6,-3) 的节点时，(-5,6) 值应该已经被拾取。
现在，我不是数学专业的。但总体思路是这样的。在您实施的优先搜索树中，您实际上是在根据两个不同的条件进行搜索。
对于 x，它是范围的简单二进制搜索。
对于 y，您实际上是在将其作为优先级树进行搜索（适合搜索 y:inf 或 -inf:y，具体取决于您使用的是最大值还是最小值。）
请注意，在第 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. 检查节点的 "mid-point" 值（我们称之为 mx）。如果 mx 在 [x1:x2] 范围内，则遍历两条路径。如果 mx < [x1:x2]，则向左遍历。否则向右遍历。为您遍历的每条路径返回步骤 1。
编辑非常非常长的文本：
让我们 运行 通过您的示例。我已经使用字母（点的 "name"）标记了每个点。每个节点现在都有点名称的格式，括号中是 y 值，下面是 "mid-range" 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点的y(7)是否>=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点的y(6)是否>=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。下面没有更多要添加的点（因为我们之前已经 checked/added 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" 在范围内。
我找到的唯一合理的幻灯片集是 this，在第 15 页上说，用于构建：
- Sort all points by their x coordinate value and store them in the leaf nodes of a balanced binary tree (i.e., a range tree)
- Starting at the root, each node contains the point in its subtree with the maximum value for its y coordinate that has not been stored
at a shallower depth in the tree; if no such node exists, then node
is empty
我实现了范围树
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)。是的，所以我在两个 children 中进行，但是对于 简单，让我跟着左边的（从现在开始所有情况下）。
- 我检查 -3 是否是 x 范围以及 6 是否大于或等于 查询的 y 范围的上限（即 5）。是的，所以我 继续。
- 下一关也一样，所以我们进入下一关，现在请 专注于这个内部节点。它的最大 y 为 0，这表明 子树的max y为0，这是不正确的（left child是 (-5, 6))*.
我在 building/searching 过程中遗漏了什么？
换句话说：
检查树最左边的分支；它具有 max_y 值（引号中的第二个项目符号），7、6、4、0。
但是那个值不是表示存储在内部节点下的子树中的最大y值的值吗？如果是这样，这不适用于0 和点 (-5, 6) （没有使用 6，因为它在第 2 级使用）。
*我提出的特定查询可能不会因此而损坏，但另一个可以。
你上次的逻辑其实还是对的。当您点击标记为 (6,-3) 的节点时，(-5,6) 值应该已经被拾取。 现在，我不是数学专业的。但总体思路是这样的。在您实施的优先搜索树中，您实际上是在根据两个不同的条件进行搜索。 对于 x，它是范围的简单二进制搜索。 对于 y，您实际上是在将其作为优先级树进行搜索（适合搜索 y:inf 或 -inf:y，具体取决于您使用的是最大值还是最小值。）
请注意，在第 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. 检查节点的 "mid-point" 值（我们称之为 mx）。如果 mx 在 [x1:x2] 范围内，则遍历两条路径。如果 mx < [x1:x2]，则向左遍历。否则向右遍历。为您遍历的每条路径返回步骤 1。
编辑非常非常长的文本： 让我们 运行 通过您的示例。我已经使用字母（点的 "name"）标记了每个点。每个节点现在都有点名称的格式，括号中是 y 值，下面是 "mid-range" 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点的y(7)是否>=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点的y(6)是否>=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。下面没有更多要添加的点（因为我们之前已经 checked/added 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" 在范围内。