一、构造kd树

k近邻法最简单的实现方法是线性扫描，弊端是计算量大。为了提高搜索的效率，可以考虑使用特殊的存储结构存储训练数据。比如kd树方法。

KDTree的构建是一个递归的过程

注意: KDTree左边的点比父节点小，右边的点比父节点大。

这里面有提到，KDTree搜索时效率未必是最优的，这个和样本分布有关系。随机分布样本KDTree搜索的平均计算复杂度是O(log N)，空间维数接近训练样本数N时，搜索效率急速下降，几乎O(N)

看维度，如果维度比较高，搜索效率很低。当然，在考虑维度的同时也要考虑样本的规模。

二、搜索kd树

见代码实现