我正在尝试为2d树实现递归最近邻居算法 . 递归（和展开递归）仍然让我感到困惑，我发现的最好的伪代码来自StackOverflow这个问题：
2D KD Tree and Nearest Neighbour Search
然而，答案使用“中位数”值，我不知道如何计算 . 关于kd-tree的维基百科文章也有一个不使用中值的最近邻伪代码 .
我想知道是否有可能在不使用中值的情况下构造Nearest Neighbors算法的递归版本 . 如果有人能为我提供伪代码，我将不胜感激 .
我正在尝试为2d树实现递归最近邻居算法 . 递归（和展开递归）仍然让我感到困惑，我发现的最好的伪代码来自StackOverflow这个问题：
2D KD Tree and Nearest Neighbour Search
然而，答案使用“中位数”值，我不知道如何计算 . 关于kd-tree的维基百科文章也有一个不使用中值的最近邻伪代码 .
我想知道是否有可能在不使用中值的情况下构造Nearest Neighbors算法的递归版本 . 如果有人能为我提供伪代码，我将不胜感激 .
1 回答
如果你不想使用中位数，你可以使用均值 . Here，有一个简单的方法：
但是，我强烈建议你去中位数，因为尺寸允许你的情况 .
Source
你真的不需要对它们进行排序 . 伪排序就足够了，例如使用Quickselect .
例如，在C中，您可以使用nth_element()来有效地找到中位数 . 你可以看到我的问题here，我需要一般尺寸的中位数 . 在2D的情况下，它可以确保简化 .