如何在范围树中搜索？

Question

我读了几张幻灯片，例如 one 的最后一页，其中描述了搜索算法。但是，我有一个基本问题。数据位于 2D space.

我首先根据点的x值构建一个二叉搜索树。每个内部节点都根据位于该内部节点子树中的点的 y 值持有一个 BST。

然后我认为我应该搜索范围查询 [x1, x2] 中的点，然后检查这些点是否在请求的 [y1, y2] 范围内查询得到满足。但是，算法建议您应该在内部节点的基于 y 的 BST 中搜索，如果内部节点的范围在 [x1, x2] 内，但我不明白。

如果我们这样做，那么在我的示例中，我们将（无缘无故地）搜索根的基于 y 的 BST。检查示例：

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

我希望执行的范围查询是 (-oo, 1) x (0, 5)^*.

如果我查看根，它的值为 0，因此它包含在 (-oo, 1) 中，所以如果我遵循该算法，我将搜索根的整个基于 y 的树？

那应该是一棵包含所有点的树，所以继续在基于x的树中搜索没有意义。此外，这将导致访问的节点多于必要的节点。

_{如果重要的话，我正在 c++ 中实施。}

*_{对 [-inf, 1] 范围内的 x 和 [0, 5] 范围内的 y 执行范围查询。}

Answer 1

你提出的算法不太正确 - 你应该将你正在查询的范围与你正在查看的节点的范围进行比较，而不是节点的值。

例如，最初你应该比较(-inf, 1)和(-5, 6)，这是树的数据范围（你也可以使用(-inf, inf)作为树的数据范围或任何包含 (-5, 6) 的区间），而不是值 0。递归地，您应该将查询范围与以您正在查询的节点为根的子树的范围进行比较。

此外，范围更新可以在搜索时完成——在节点处拆分时，left/right 递归调用间隔的 upper/lower 边界是节点值。

如何在范围树中搜索？

How to search in a Range Tree?

c++

algorithm

search

computational-geometry

range-tree