算法：用kd树的最近邻搜索

输入：已构造的kd树：目标点；

输出：的最近邻

（1）在kd树中找出包含目标点的叶节点：从根节点出发，递归地向下访问kd树。若目标点当前维的坐标小于切分点的坐标，则移动到左子节点，否则移动到右子节点。直到子节点为叶节点为止。

（2）以此叶节点为“当前最近点”。

（3）递归地向上回退，在每个节点进行以下操作：

​ （a）如果该节点保存的实例点比当前最近点距离目标点更近，则以该实例点作为“当前最近点”

​ （b）当前最近点一定存在于该节点一个子节点对应的区域。检查该子节点的父节点的另一子节点（兄弟节点）对应区域是否有更近的点。具体地，检查另一子节点对应的区域是否与以目标点为球心、以目标点与“当前最近点”间的距离为半径的超球体相交。

​ 如果相交，可能在另一个子节点对应的区域内存在距目标点更近的点，移动到另一个子节点。接着递归地进行最近邻搜索；

​ 如果不相交，向上回退

（4）当回退到根节点时，搜索结束。最后的“当前最近点”即为的最近邻点。

如果实例点是随机分布的，kd树搜索的平均计算复杂度是 ，这里 是训练实例数。kd树更适用与训练实例数远大于空间维数时的k近邻搜索。当空间维数接近训练实例数时，它的效率会迅速下降，几乎接近线性扫描。