我有坐标点 (x,y) 说我有 10 000 个点。现在当一个新点作为测试查询给出时说（p，q）。我必须检查坐标点中的每个点。如果文本查询的 x 坐标是来自在线搜索的 PY，我开始知道 Rmq-range min/max 查询数据结构可以帮助我，但我不知道该怎么做。有人能帮我怎么做吗..c ++中的任何参考或代码帮助都会有很大帮助.谢谢
问问题
1511 次
1 回答
3
如果您的目标是检查该点是否存在于数据集中，那么您可以使用许多非常有用的数据结构来保存数据，每个数据结构都支持非常有效的查找。
对于初学者，如果您只需要知道该点是否存在，您始终可以将所有点存储在标准哈希表或平衡二叉搜索树中。这将分别提供 O(1) 或 O(log n) 查找时间。此外，这些结构往往在大多数编程语言中都可用。
另一方面，如果您计划对数据进行更高级的操作，例如在数据集中搜索离某个测试点最近的 k 个点，或者尝试找到某个边界区域中的所有点，您可能想考虑使用kd-tree或quadtree。标准二进制搜索的这些变体提供快速查找（O(log n) 时间）。kd-tree 还支持非常快速的 k-最近邻搜索和边界体积内的搜索。此外，如果您有任何实现标准二叉搜索树的经验，那么 kd-tree 的实现非常容易。
希望这可以帮助！
于 2011-08-25T00:58:57.850 回答