我正在寻找一些用于范围搜索的数据结构。我认为范围树提供了很好的时间复杂度（但有一些存储要求）。
然而，在我看来，其他数据结构，如KD-trees，比范围树更受讨论和推荐。这是真的？如果是这样，为什么？
问问题
627 次
2 回答
1
我希望这是因为 kd-trees 可以直接扩展到包含点以外的对象。这使它在虚拟世界中有很多应用，我们希望快速查询三角形。范围树的类似扩展并不简单，事实上我从未见过。
快速回顾一下：kd-tree 可以在 O(n log n) 时间内将 d 空间中的一组 n 点预处理为使用 O(n) 空间的结构，以便可以回答任何 d 维范围查询在 O(n 1-1/d + k) 时间内，其中 k 是答案的数量。范围树需要 O(n log d-1 n) 时间进行预处理，占用 O(n log d-1 n) 空间，并且可以在 O(log d-1 n + k) 时间内回答范围查询。
如果我们谈论的是 2 维或 3 维空间，范围树的查询时间显然比 kd 树的查询时间要好得多。然而，kd-tree 有几个优点。首先，它总是只需要线性存储。其次，它总是在 O(n log n) 时间内构建。第三，如果维度非常高，它将优于范围树，除非您的点集非常大（尽管可以说，此时线性搜索几乎与 kd-tree 一样快）。
我认为另一个重要的一点是，kd-trees 比范围树更广为人知。在参加计算几何课程之前，我从未听说过范围树，但我之前听说过并使用过 kd-trees（尽管是在计算机图形设置中）。
编辑：当你有数百万个点时，你问什么是 2D 或 3D 固定半径搜索更好的数据结构。我真的不能告诉你！我倾向于说，如果您执行许多查询，范围树会更快，但对于 3D，构建速度会慢 O(log n) 倍，并且内存使用可能会在速度之前成为问题。我建议集成这两种结构的良好实现，并简单地测试什么对您的特定要求有更好的工作。
于 2015-04-18T14:09:47.520 回答
0
对于您的需求（2D 或 3D 粒子模拟），您需要一个能够进行所有最近邻查询的数据结构。覆盖树是最适合此任务的数据结构。我在计算最近邻以进行核密度估计时遇到了它。这个Wikipedia 页面解释了树的基本定义，John Langford 的页面有一个 C++ 实现的链接。
单个查询的运行时间为 O(c^12*logn)，其中 c 是数据集的扩展常数。这是一个上限——在实践中，数据结构比其他数据结构执行得更快。本文表明，粒子模拟所需的所有最近邻居（对于所有数据点）的批处理运行时间为 O(c^16*n)，并且这种理论线性界限也可以满足您的需要. 构建时间为 O(nlogn)，存储时间为 O(n)。
于 2015-04-20T11:40:05.303 回答