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.
274
｜
第
10
章
对于每个查询点
x
，
k-d
树算法会计算出
P
中距离
x
最近的相邻点。
如果两个点之间的距离“过于接近”（只有浮点误差之间的差别），那么
k-d
树算法可
能会选择错误的点。但是，由于所找到的点距离实际点非常接近，因此这个错误结果的
影响可以忽略不计。
10.5.2 使用环境
查找最近邻的穷举算法是计算待查询的点
x
与
P
中每个点
p
(
p
∈
P
)
的距离，从而比较选
择最近的一个。与穷举算法相比，
k
-
d
树算法在使用时需要考虑两个重要的费用：①构
建
k
-
d
树的费用；②在树结构中定位查询点
x
的费用。影响这些费用的因素如下：
维度
随着维度的增加，构建
k-d
树所需要的费用会掩盖它所能发挥的作用。一些权威人
士认为，在维度超过
20
之后，这种方法不如直接比较所有点来得高效。
输入集合中的点的数量
当点的数量很小时，构建树的费用可能会超过它所带来的性能提升。
二叉树结构之所以能够成为高效的搜索结构，是因为它在将结点插入树中或从树中移除
时可以保持平衡。但不幸的是，
k
-
d
树既无法简单地进行平衡处理，也不能移除点，这
与它所表示的维度平面的深层次结构信息有关。理想的解决方案是构建一棵初始的
k
-
d
树，它要么能够保证树中的叶结点均位于相同层次，要么能够保证叶结点之间的层次差
距在一层以内。
10.5.3 解决方案
例
10-1
给出了最近邻算法在给定
k
-
d
树上的实现。
例
10-1
：
k-d
树上的最近邻算法实现
// k-d
树方法。
public IMultiPoint nearest (IMultiPoint target) {
if (root ...
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.