R树和R *树的范围搜索复杂度

Question

R树和R *树的范围搜索复杂度是多少？我了解范围搜索过程：类似于DFS搜索，它访问每个节点，并且如果节点的边界框与目标范围相交，则将该节点包含在结果集中。更确切地说，我们还需要考虑它使用的分支定界策略：如果父节点不与目标相交，那么我们不访问它的子节点。那么复杂度应该小于O（n），其中n是节点的数量。我真的不知道如何计算给定树叶数（或数据点）的节点数量。 有人可以在这里给我一个解释吗？谢谢。

Answer 1

显然，如果您的范围是[-∞;∞]在每个维度上，最坏的情况必须至少为O（n）。它可能跟O（n log n）一样坏，然后是因为树。

假设答案是单个条目，平均情况可能是O（log n） - 只有少数几条通过树的路径需要遵循（如果你有足够的重叠）。

它是登录到您的页面大小的基础。所以它通常不会超过5，因为你永远不会想要超过1000^5 = 10^15个物体的树木。

出于所有实际的目的，假设运行时复杂度只是答案集大小O（s）。选择2％的数据需要两倍于1％的长度。