我阅读了几张幻灯片,比如这个的最后一页,其中描述了搜索算法。但是,我有一个基本问题。数据位于二维空间中。
我首先根据点的 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 执行范围查询。