如何在范围树中搜索？ [英] How to search in a Range Tree?

问题描述

我读了几张幻灯片，像这样一个 s的最后一页，其中描述了搜索算法。但是，我有一个基本问题。数据位于2D空间中。

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

然后我应搜索位于范围查询[x1，x2]中的点，然后检查所请求的[y1，y2]范围查询是否满足该点。然而，该算法建议，如果内部节点的范围在[x1，x2]内，但是我不知道，则应该在内部节点的基于y的BST中搜索。

---

如果我们这样做，那么在我有一个例子中，我们将搜索（没有原因）基于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的树？ p>

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

---

_{=/ questions / tagged / c％2b％2bclass =post-tagtitle =show questions tagged'c ++' =tag> c ++ ，if that matters。}

* _{在[-inf，1]范围内为x执行范围查询，y范围为[0，5]。} / p>

解决方案

您提出的算法不太对 - 您应该将查询的范围与您所在节点的范围进行比较

例如，最初你应该比较（ - inf，1）与（ - 5，6），这是树的数据范围（也可以使用（ - inf，inf）作为树的数据范围或任何包含（ - 5，6）的区间，而不是值0.递归地，你应该比较

此外，范围更新可以在搜索时完成 - 当在节点分割时，左/右递归调用间隔的上/下界是节点值。

I read several slides, like this one's last page, where the describe the search algorithm. However, I have a basic question. The data lie in a 2D space.

I first build a Binary Search Tree based on the x value of the points. Every inner node holds a BST based on the y value of the points that lie in the subtree of that inner node.

Then I think I should search for the points that lie in the range query [x1, x2] and then check if for that points the requested [y1, y2] range query is satisfied. However, the algorithm suggests that you should search in the y-based BST of an inner node, if the range of the inner node is inside [x1, x2], but I don't get that.

---

If we do that, then in an example I have, we will search (without a reason) the y-based BST of the root. Check the example:

                      ------ 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)

And the range query I wish to perform is (-oo, 1) x (0, 5)^*.

If I look at the root, it has value 0, thus it's enclosed in (-oo, 1), so if I follow the algorithm I am going to search the whole y-based tree of the root?

That should be a tree that contains all the points, so there is no point in continuing searching in x-based tree. Moreover, that will result in more visited nodes than the necessary.

---

_{I am implementing that in c++, if that matters.}

*_{Performing a range query for x's in the range [-inf, 1] and y's in the range [0, 5].}

解决方案

The algorithm you are proposing is not quite right - you should compare the range you are querying with the range of the node you are looking at, not the value of the node.

E.g., initially you should compare (-inf, 1) with (-5, 6), which is the data range of the tree (you can also use (-inf, inf) as the data range of the tree or any interval that encloses (-5, 6), for that matter), instead of the value 0. Recursively you should compare the query range with the range of the subtree rooted at the node you are querying at.

Also, the range update can be done while searching - when splitting at a node, the upper/lower bound of the left/right recursive call interval is the node value.

这篇关于如何在范围树中搜索？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！