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.
空间树结构
｜
281
空间树结构
10.5.5 衍生算法
在我们所展示的实现中，
nearest
方法都是自顶向下从根结点一路遍历到计算出的父结
点。另一种实现则可以从父结点自底向上遍历到根结点。
10.6 范围查询
给定矩形区域
R
[
x
low
,
y
low
,
x
high
,
y
high
]
和点集
P
，查找
P
中哪些点位于目标矩形
T
中？可以
用穷举法检查
P
中的所有点来进行判断，所花费的时间为
O
(
n
)
。那么，有没有更好的方
法呢？
对于
最近邻问题
，我们将点组织到了
k-d
树中，从而达到了在
O
(
log
n
)
的时间内完成最
近邻查询。借用相同的数据结构，我们可以在
O
(
n
0.5
+
r
)
的时间内计算范围查询，其中
r
是查询结果中点的数量。当输入集合包含
d
维数据点时，该解决方案可以在
O
(
n
1-1/
d
+
r
)
的时间内解决
d
维的范围查询问题。
给定目标区域
T
覆盖了整个左半平面直到刚好超过图
10-10
中的
7
号点，我们可以从图
中看到所有这三类情况。由于
T
并没有覆盖整个与根结点相关联的无限区域，因此
范围
查询
检查了
T
是否包含
1
号点，结果它的确包含，因此
1
号点被加入结果中。接下去，
T
扩展到其
上方
和
下方
的子结点，因此共有两次递归调用。第一次递归调用位于
1
号点
之下
，
T
完整地包含了
2
号点关联的区域。因此，
2
号点及其所有子孙结点都被加入结果中。
第二次递归最终发现
7
号点并将其加入结果中。
范围查询算法小结
最坏情况和平均情况：
O
(
n
1-1/
d
+
r
)
最坏情况：
O
(
n
)
range (space)
results = new Set
range ...
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.