第235页 | 算法技术手册 | 阅读 ‧ 电子书库

同步阅读进度,多语言翻译,过滤屏幕蓝光,评论分享,更多完整功能,更好读书体验,试试 阅读 ‧ 电子书库

解决方案

例9-6的Java实现是Dimensional Node类的一个方法,这个方法由kd树的search(IHypercube)代理。这个算法在DimensionalNode类表示的区域在查询的范围内时,效率最高。在这种情况下,DimensionalNode的所有后继节点都可以加入结果集中,因为kd树的性质保证一个节点表示的区域包括了其所有的后继节点表示的范围。

例9-6:范围查询实现

例9-6的代码是一个修改过的遍历树实现。kd树以一种层次的方式来划分d维点,范围查询在每个节点n上将会做三个决定:

这个节点n相关的区域是否已经完全包含了查询区域?

当这种情况发生时,查找将会停止,因为所有的后继节点都属于结果集。drain方法会遍历子树的所有节点,并且将这些点加入结果集中。

查询的区域包含节点n的点吗?

如果是的话,将这个点加入到结果集中。

查询区域会和n表示的点相交吗?

有两种方法可以检查这种情况:如果查询范围寻找n左边的点,那么遍历n的下子树,否则应该遍历上子树。

请支持我们,让我们可以支付服务器费用。
使用微信支付打赏


上一页 · 目录下一页


下载 · 书页 · 阅读 ‧ 电子书库