首页 » 算法技术手册 » 算法技术手册全文在线阅读

《算法技术手册》解决方案

关灯直达底部

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

图 9-21 kd树核心思想

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

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

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

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