我在看维基百科上的杜兰特树。例如，我在python中实现了构建kd树的算法。
但是，使用kd树进行knn搜索的算法会切换语言，而且还不完全清楚。英语的解释开始有意义了，但它的某些部分（例如它们“展开递归”以检查其他叶节点的区域）对我来说并没有真正意义。
这是如何工作的？如何用python中的kd树进行knn搜索？这并不意味着是一个"send me the code!"类型的问题，我也不希望这样。请简单解释一下：）
最佳答案
本页，第3页：
在三维空间中给定一组n个点，构造了kd树
递归如下。首先，我们找到第i个的中值
点的坐标（最初，i=1）。也就是说，计算m值，
使至少50%的点的ith坐标大于或等于
到m，而至少50%的点的ith坐标较小
大于或等于m。存储x的值，并对集p进行分区
在pl和pr中，其中pl只包含具有ith坐标的点
小于或等于m，pr=pl±1。然后重复这个过程
在pl和pr上递归，用i+1替换i（如果i=d，则为1）。
当节点上的点集的大小为1时，递归停止。
以下段落讨论了它在解最近邻中的用途。
或者，这里是book introduction。
编辑：我应该补充一下，scipy有一个kdtree实现：
original 1975 paper by Jon Bentley
scipy.spatial
关于python - KD树最近邻搜索如何工作？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/4418450/