阅读 ‧ 电子书库

解决方案

图9-21是实现kd树的类的UML设计图。这个结构是基于二叉树的，但是主要的差异是DimensionalNode对象维护的额外信息，即Hypercube区域。

例9-5是寻找x最近点算法的kd树实现代码。图9-20是这个算法的伪代码，其最初几步是如何调用这个算法。

例9-5：最邻近点查询的kd树实现

广告：个人专属 VPN，独立 IP，无限流量，多机房切换，还可以屏蔽广告和恶意软件，每月最低仅 5 美元

理解最邻近点算法的关键在于我们要能够快速定位点x所在的区域，因为这个区域内很可能存在最近的点。之后我们从根节点到这个区域，递归地检查是否存在其他的更近的点，因为kd树的矩形区域划分是根据输入集的变化而变化。在一棵不平衡的kd树中，这个检查过程的开销可能会达到O(n)，因此我们需要更加合理地处理输入。

我们有两个地方可以改进样例解的性能。首先，我们使用原始的double数组来表示点，然后在这之上进行比较。其次，DimensionalNode有一个方法，这个方法返回两个d维点的距离是否小于当前得到的最小距离，这个方法（在本书的代码库中）将会在距离超过已知最小距离时立即退出。