二维树最近邻算法澄清

我想实现一个2d树的递归最近邻算法。递归（和展开递归）仍然是一种混淆，我和我已经找到了最好的伪代码是从这个StackOverflow的问题：二维树最近邻算法澄清

然而答案使用“中位数”的价值，这我不是确定如何计算。另外维基百科关于kd-trees的文章有一个最近邻居伪代码，它不使用中间值。

我想知道是否有可能在不使用中值的情况下构造最近邻居算法的递归版本。如果任何人都可以为我提供伪代码，我将不胜感激。

2015-04-26 Adam me

不知道这是否会完全澄清的东西给你，但你可能对这个[问题]看看我最近的【答案】（http://stackoverflow.com/a/29868500/2573395）（HTTP：/ /stackoverflow.com/questions/29853162/improving-mitchells-best-candidate-algorithm），它提供了2D KD树的最小实现。 – Alex

语法对我来说并不熟悉，因为我主要使用Java。但我明天会通过你的答案，看看它是否有帮助，谢谢。 –

链接的文章的术语有点偏离。 OP称之为中位数就是分裂值。如果可能的话，这是很好的利用这些数据进行平均分割，因为它给了最低高度的树，肠道，这是不是必需的。例如。如果您没有提前访问所有数据，则无法找到中位数。所有kd树建设和搜索依赖于_splitting_值是否是中位数或没有。 – Gene

如果你不想使用中位数，你可以使用mean。 Here，有简单的方法：

例1：这些数字的平均值是多少？

6，11，7
Add the numbers: 6 + 11 + 7 = 24 
Divide by how many numbers (there are 3 numbers): 24/3 = 8 
中庸是8

不过，我强烈建议你去的中位数，因为尺寸允许它在你的情况。

实施例：找到的12，图3和5

中位数把它们顺序为：

3，5，12

中间数为5，因此，中位数是5 。

Source

你没有做真的需要对它们进行排序。伪排序就足够了，例如使用Quickselect。

以C++为例，您可以使用nth_element()来有效地查找中位数。你可以看到我的问题here，其中我需要一般维度的中位数。在2D的情况下，它可以确保简化。

来源

2015-04-27 11:33:34 gsamaras

二维树最近邻算法澄清

回答

相关问题