假设您在二维平面上有一组唯一点S。现在，您期望以“ p中存在点S？”的形式出现一系列问题。您决定构建一个范围树来存储您的S并回答这个问题。范围树的基本思想是，首先在Tree0坐标上构建一个平衡的二叉搜索树0-th，然后在Tree0的每个节点上构建另一个平衡的搜索树Tree1，但是这次使用[ C0]作为您的关键。 1-st。
[现在，我期望为Wikipedia article for Range Tree的每个节点Tree1构建的n0将完全容纳Tree0坐标等于0-th的键的那些点。但是，如果您阅读有关范围树的更多信息，则会发现情况并非如此。具体来说：
n0的根r0包含保存所有点的Tree0。Tree1的左子包含一个r0，该Tree1保留0-th坐标小于0-th处的r0坐标的所有点。r0的右子包含一个Tree1，其中包含0-th坐标大于r0中的坐标的所有点。如果继续执行此逻辑，您会看到在范围树的每个级别上，所有点都存储一次。因此，每个级别都需要n内存，并且由于平衡Tree0的深度为logn，因此将O(nlogn)作为内存要求。
但是，如果只将其0-th坐标完全匹配的点存储在节点上，则每个点将在整个树中存储一次（而不是在树的每个级别上），给出O(n)内存要求。
在每个级别的范围树中将点存储一次的原因是什么？它允许进行某种范围内的查询吗？到目前为止，在我看来，您可以对O(nlogn)版本执行的任何查询也都适用于O(n)版本。我想念什么？
（将@ user3386109的评论扩展为完整答案。）
有几种不同的数据结构用于存储点的2D集合，每种结构都针对不同类型的查询进行了优化。顾名思义，范围树针对range search，查询形式进行了优化，其形式为“这是一个矩形，该矩形中的所有点是什么？”设计范围树的结构（将每个点存储在几个不同的子树中），以便您可以在一维中找到包含矩形一个轴的节点范围，然后发现下一维中另一个维中的所有节点矩形的如果您不打算对此表格进行任何查询，则无需以这种方式存储内容。您实质上是在为不需要使用的东西付费。
还有其他数据结构可用于存储一组点并查看是否存在特定点。如果这是您唯一需要回答的问题，则可能只需要一个简单的哈希表。您还可以使用常规的BST，在该BST中，首先按点的第一部分比较点，然后按点的第二部分进行比较。 （如果需要，您也可以在此处使用k-d树。）
希望这会有所帮助！