博客

kd树原理

之前看KNN时，确实发现这个计算量很大。因此有人提出了kd树算法，其作用是，当你需要求得与预测点最近的K个点时，这个算法可以达到O(logN)的时间复杂度(相当于搜索一颗二叉树的时间耗损).
原理有一篇博文讲的十分精彩[这里写链接内容](http://blog.csdn.net/u010551621/article/details/44813299)

kd树python实现

这里给出的是kd树的建树、对预测点求得最近邻的k个点的python代码。
本博文的代码是在(http://blog.csdn.net/u010551621/article/details/44813299)的基础上进行的修改，感谢其清晰的原理和代码表达。

kd树节点结构


一个树节点包括：

1. 节点信息
2. 被分割的维度
3. 左孩子
4. 右孩子

python代码如下

class KD_node(object):
    #定义的kd树节点
    def __init__(self, point &