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.
284
｜
第
10
章
//
不会影响结果的正确性。
if (space.getLeft(dimension) < coord) {
if (below != null) { below.range (space, results); }
}
if (coord < space.getRight(dimension)) {
if (above != null) { above.range (space, results); }
}
}
例
10-3
中所示的代码是一个修改过的树遍历实现，它会潜在地访问树中的每一个结点。
由于
k-d
树是以层次的方式划分
d
维数据集合，因此
范围查询
在每个结点
n
上将会确定
三个问题：
查询区域是否完全包含与结点
n
相关联的区域？
当这种情况发生时，区域遍历可以停止，因为所有子孙结点都属于查询结果。
查询区域是否包含与结点
n
相关联的点？
如果是，将该点加入结果集中。
查询区域与结点
n
表示的
d
维平面是否有交集？
要判断这一点需要经过两个步骤，因为查询区域既可能与结点
n
的下方子树相关联
的区域有交集，也可能与结点
n
的上方子树相关联的区域有交集。代码可能会执行
0
次、
1
次或
2
次的
range
递归遍历。
由于注意到
KDSearchResults
对象返回的结果既包含单个点也包含整棵子树，因此如果
想要获得所有点，则需要遍历结果中的每棵子树。
10.6.4 算法分析
查询区域有可能会包含树中的所有点，在这种情况下，所有点都会被返回，从而导致
O
(
n
)
的性能。但是，当
范围查询算法 ...
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.