3

假设您S在二维平面上有一组独特的点。现在，您期待着一堆“点p存在于S？”形式的问题。你决定建立一个范围树来存储你的S问题并回答这个问题。范围树背后的基本思想是，您首先Tree0在0-th坐标上构建平衡二叉搜索树，然后在此构建的每个节点上再Tree0构建另一个平衡搜索树Tree1，但这次使用1-st坐标作为键。Range Tree 的维基百科文章。

现在，我期待Tree1为 的每个节点构建的n0那些Tree0点将准确地保存其0-th坐标等于键 from 的那些点n0。但是，如果您阅读有关范围树的更多信息，您会发现情况并非如此。具体来说：

  1. 的根r0包含Tree0包含Tree1所有点的 a。
  2. 的左孩子r0包含 a Tree1，其中包含0-th坐标小于0-th处坐标的所有点r0。
  3. 的右孩子r0包含 a Tree1，其中包含0-th坐标大于 from的所有点r0。

如果你继续这个逻辑，你会看到在 Range Tree 的每一层，所有的点都只存储一次。因此，每个级别都需要n内存，并且由于平衡的深度Tree0是logn，这O(nlogn)就是内存要求。

但是，如果您只存储其0-th坐标与节点处的键完全匹配的点，那么您将在整个树（而不是树的每个级别）中存储每个点一次，这会产生O(n)内存需求。

在范围树中每个级别存储一次点的原因是什么？它是否允许某种很酷的范围查询或其他东西？到目前为止，在我看来，您可以对该版本执行的任何查询O(nlogn)也适用于该O(n)版本。我错过了什么？

4

1 回答 1

1

（将@user3386109 的评论扩展为完整答案。）

有几种不同的数据结构用于存储点的 2D 集合，每种数据结构都针对不同类型的查询进行了优化。顾名思义，范围树针对范围搜索进行了优化，查询形式为“这是一个矩形，该矩形中的所有点是什么？” 范围树的结构 - 将每个点存储在几个不同的子树中 - 旨在让您可以在一维中找到包含矩形一个轴的节点跨度，然后发现下一维中位于另一维中的所有节点的矩形。如果您不打算对该表单进行任何查询，则无需以这种方式存储内容。您实际上是在为您不会使用的东西付费。

您可以使用其他数据结构来存储一组点并查看是否存在特定点。如果这是您需要回答的唯一问题，那么您可能只需要使用一个简单的哈希表。您还可以使用常规 BST，其中点首先通过它们的第一个组件进行比较，然后再通过它们的第二个组件进行比较。（如果你愿意，你也可以在这里使用 kd 树。）

希望这可以帮助！

于 2020-06-10T18:43:44.923 回答