algorithm - 范围树 : why not save space by default?

Question

假设您在二维平面上有一组 S 唯一点。现在，您期待着一堆问题，形式为“S 中是否存在点 p？”您决定构建一个 Range Tree 来存储您的 S 并回答这个问题。 Range Tree 背后的基本思想是首先在 0-th 坐标上构建一个平衡的二叉搜索树 Tree0，然后在这个 Tree0< 的每个节点上 构建另一个平衡搜索树 Tree1 但这次使用 1-st 坐标作为键。 Wikipedia article for Range Tree .

现在，我期望为 Tree0 的每个节点 n0 构建的 Tree1 将恰好包含那些 0 -th 坐标等于 n0 中的键。但是，如果您阅读更多有关 Range Trees 的内容，您会发现情况并非如此。具体来说:

1. Tree0 的根 r0 包含一个包含所有点的 Tree1。
2. r0 的左子节点包含一个 Tree1，它包含所有 0-th 坐标小于 的点r0 处的第 0 坐标。
3. r0 的右子节点包含一个 Tree1，它包含所有 0-th 坐标大于 的点>r0.

如果您继续这个逻辑，您将看到在范围树的每个级别，所有点都只存储一次。因此，每个级别都需要 n 内存，并且由于平衡的 Tree0 的深度是 logn，这给出了 O(nlogn)作为内存要求。

但是，如果您只存储其第 0 坐标完全匹配节点键的点，那么您将为整个树存储每个点一次(而不是树的每个级别)，这给出了 O(n) 内存要求。

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

Answer 1

(将@user3386109 的评论扩展为完整答案。)

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

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

希望这对您有所帮助!