August 2017
Intermediate to advanced
360 pages
8h 35m
Chinese
Content preview from 算法技术手册（原书第2 版）
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.
282
｜
第
10
章
range (space, node.above, results)
end
❶
如果待搜索的空间包含整个
k-d
树中的结点所关联的区域，则将其子孙结点加入
结果中。
❷
如果点包含于待搜索的空间中，
确保其被加入结果中。
❸
有可能需要搜索
上方
子结点和
下方
子结点。
10.6.1 输入 / 输出
输入是一个由
n
个
d
维空间中的点组成的点集
P
以及一个
d
维的超立方体，该立方体指
即为待执行的范围查询。范围查询与
d
维数据集中的坐标轴相匹配，对于输入集合中的
每一维，都指定了一个单独的范围。对于
d
=
2
的二维空间，范围查询需要同时指定
x
坐标轴上的范围以及
y
坐标轴上的范围。
范围查询
的结果包含了完整的被目标范围包含的点集。结果中的点是无序的。
10.6.2 使用环境
k-d
树在高维度情况下性能较差，因此该算法和整体方案都应当局限于小型维度的数据。
对于二维数据下的
最近邻
问题和
范围查询
问题，
k-d
树提供了极好的性能。
10.6.3 解决方案
例
10-3
所示的
Java
解决方案是
DimensionalNode
类中的一个方法，它简单地将逻辑委
托给
KDTree
中的
range(IHypercube)
方法。当
DimensionalNode
的区域被目标范围查
询完全覆盖时，
k-d
树算法的效率最高。在这种情况下，
DimensionalNode
的所有子孙结
点都可以加入结果集合中，这是因为
k-d
树的性质保证了子结点会位于其所有祖先结点
区域以内。
例
10-3
：
DimensionalNode
的范围查询实现
public ...
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access
More than 5,000 organizations count on O’Reilly
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.Julian F.
I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.Addison B.
I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.Amir M.
I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.