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.
空间树结构
｜
301
空间树结构
# CT6 [
重新插入孤立条目
]
将集合
Q
中的结点条目重新插入。
for n in Q:
for rect,ident in n.leafOrder():
self.add (rect, ident)
# D4 [
缩短树的高度
]
在树被调整之后，如果根结点只有一个子结点，
#
让子
结点成为新的根结点。
while self.root.count == 1 and self.root.level > 0:
self.root = self.root.children[0]
if self.root.count == 0:
self.root = None
return True
10.8.4 算法分析
R
树结构之所以高效，是因为它能够在矩形插入之后让自身保持平衡。由于所有矩形都
存储在
R
树中
相同高度
的叶结点上，因此内部结点起到了中间计算的作用。虽然参数
m
和
M
决定了结构的细节，但是总体上我们能够保证树的高度为
O
(log
n
)
，其中
n
是
R
树
中结点的数量。
split
方法将矩形分配在两个结点之间，它使用启发式的方法以最小化包
含这两个点的外框总面积。其他一些启发式做法参见相关文献。
R
树的搜索性能依赖于树中矩形的数量和矩形的
密度
，或者说依赖于包含给定点的矩形
的平均数量。对于由单位正方形中随机坐标组成的
n
个矩形，大约有
10%
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.