习题3.2

3.2 利用例题3.2构造的kd树求点 的最近邻点。


（1）从根节点开始，的，进入左节点，而进入右节点，目标节点在叶节点对应的区域中，这一点也可以观察图1特征空间的划分得出来，在左上角的矩形区域中。

（2）将点作为当前最近邻点。

（3）然后回退到父结点 ：由于 ，因此将作为当前最近邻点。然后以点 为圆心，到的距离为半径作圆。该圆与结点的另一子结点 所在的区域相交，因此需要在点 所在的区域寻找最近邻。由于 ，因此将点作为当前最近邻点。
继续回退到点 ，由于 ，因此点 不能成为当前最近邻点。且之前的圆不与点 的区域相交，即另一子结点 所在的区域相交，因此不可能在点 所在的区域找到最近邻点。

（4）到此为止我们已经回退到根结点，搜索结束，我们得到点的最近邻点为 。