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.
空间树结构
｜
271
空间树结构
图 10-4：使用基于点划分的四叉树
图 10-5：R 树示例
根结点代表了包含树中其他矩形的最小矩形区域（
x
low
，
y
low
，
x
high
，
y
high
）。每个内部结
点都有一个关联的矩形区域，类似地，该结点会包含其子孙结点的所有矩形。
R
树中的
实际矩形只在叶结点中存放。除了根结点以外，每个矩形区域（无论是内部结点还是叶
结点）都会被其父结点完全包含。
下面将使用这些不同的空间结构来解决本章开篇列出的问题。
10.5 最近邻查询
给定一个二维平面的点集
P
，要求找到
P
中距离目标查询点
x
最近的点。我们将展示如
何使用
k
-d
树来高效地执行这些查询。假定树可以高效地划分这些点，那么每一次在树
上的递归遍历大约会舍去一半的点。在一个点正常分布的
k-d
树中，第
i
层的结点所代
表的矩形区域大小约为第
i+
1
层的两倍。这个特征将
最近邻查询
的费用降低至
O
(log
n
)
，
因为它可以在确定某个点离最近点过远时，舍去包含该点的整棵子树。
272
｜
第
10
章
如图
10-6
所示，当插入目标点（图中显示为小的黑色正方形）后，它会成为
9
号点所关
联结点的子结点。如果此时调用最近邻查询，算法会舍去整棵左子树，因为垂直距离
dp
更远一些，所以任何在该区域的点都不可能离目标点更近。再在右子树上执行时，算法
会检测到
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.