习题3.3

3.3 参照算法3.3，写出输出为x的k近邻的算法。

用kd树的k近邻搜索算法：
输入：已构造的kd树，目标点x；
输出：x的k近邻。
这里需要创建一个字典knears，用于存储目标点x的k近邻点以及与目标点的距离。
初始化：knears={}（一开始knears为空字典）
（1）在kd树中找出包含目标点x的叶结点：从根结点出发，递归地向下访问kd树。若目标点x当前维的坐标小于切分点的坐标，则移动到左子结点，否则移动到右子结点。直到子结点为叶结点为止。

（2）将此叶结点及其到目标点x的距离添加进字典中。

（3）递归地向上回退，在每个结点进行以下操作：
（a）如果字典中的元素个数不足k个，则将此结点及其到目标点x的距离添加进字典中；
（b）如果字典中的元素个数已经到达k个，需要计算该结点到目标点x的距离，若该距离不大于已存在于字典中的距离的最大值，则将该结点添加至字典中；
（c）检查该结点的另一个子结点对应的区域是否存在k近邻。具体地，检查另一子结点对应的区域是否于以目标点为圆心、字段中各结点至目标点x的距离的最大值为半径的超球体相交。
如果相交，则可能在另一个子结点对应的区域内存在k近邻点，此时将另一个子结点对应的区域内的所有点做以下循环处理：计算目标点x与该点的距离，若该距离不大于字典中距离的最大值，则将该点添加至字典中，否则不添加；如果不相交，继续向上回退。

（4）当回退到根结点时，搜索结束。此时我们得到了一个字典knears。knears具有以下形式： ，这里 。最后将字典knears中的元素按照距离值升序排序，前k个点就是目标点x的k近邻。