没有合适的资源?快使用搜索试试~ 我知道了~
首页算法新解:从二叉搜索树到红黑树
算法新解:从二叉搜索树到红黑树
需积分: 50 32 下载量 45 浏览量
更新于2024-07-06
2
收藏 5.94MB PDF 举报
"541127 算法新解.pdf" 这本书主要探讨了算法在解决实际问题中的应用和威力,特别强调了算法和数据结构的重要性。作者刘新宇在书中详细介绍了几种基础算法及其优化,包括最小子集问题、丑数问题以及不同类型的排序和树结构,如二叉搜索树、插入排序的演变、红黑树和AVL树。 在最小子集问题中,作者通过两个改进方案展示了算法如何提升效率,分别是单次遍历和分而治之的策略,强调了在追求简洁与性能之间寻找平衡的重要性。丑数问题部分,作者讨论了暴力求解方法和构造性解法,进一步提出利用多个队列来优化算法,展示了数据结构的威力。 书中对二叉搜索树进行了深入解析,包括其定义、数据组织、插入、遍历、搜索、删除以及随机构建的方法。二叉搜索树作为一种基础数据结构,其特性使得插入、查找和删除操作具有较高的效率。此外,作者还介绍了插入选排序的进化过程,从基本的线性搜索到二分查找,再到链表的运用,最后通过引入二叉搜索树实现更高效的排序。 红黑树是一种自平衡二叉搜索树,作者详细阐述了如何通过颜色属性保持树的平衡,并介绍了插入和删除操作的具体步骤。命令式的红黑树算法则进一步帮助理解其内部机制。AVL树是另一种自平衡二叉搜索树,具有严格的平衡条件,书中详细讲解了AVL树的插入、删除以及平衡调整过程,包括四种不同的旋转操作。 最后,书中提到了基数树(Trie),这是一种特殊的树形数据结构,常用于高效地存储和检索字符串集合。基数树在字符串查找和关联数据存储方面有广泛应用。 这本书是学习算法和数据结构的优秀资源,它不仅涵盖了基础知识,还深入探讨了优化和实际应用,对于提升算法思维和解决问题的能力大有裨益。
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/76312519/bg10.jpg)
16 前⾔
这⼀⽅法并不需要额外的空间
1
。每次调⽤需要进⾏O(|A|)次⽐较来划分出⼦
序列A
′
和A
′′
。之后,问题的规模减半,所以这个算法⽤时为T (n) = T (n/2) +
O(n),化简可知其结果为O(n)。我们也可以这样分析其复杂度:第⼀次需
要O(n)次⽐较来划分⼦序列A
′
和A
′′
,第⼆次仅需要⽐较O(n/2)次,第三次需
要⽐较O(n/4)次……总时间为O(n + n/2 + n/4 + ...) = O(2n) = O(n)。
在有些函数式编程语⾔,例如Haskell中,划分⼀个序列已经被作为库函数提
供了。下⾯的例⼦代码实现了分⽽治之的算法。
import Data.List
minFree xs =bsearch xs 0 (length xs - 1)
bsearch xs l u | xs == [] = l
| length as == m - l + 1 = bsearch bs (m+1) u
| otherwise = bsearch as l m
where
m = (l + u) `div` 2
(as, bs) =partition (≤m) xs
0.2.3 简洁与性能――鱼和熊掌
使⽤命令式编程语⾔的读者可能会担⼼这种实现的性能。对于最⼩的可分配
ID问题,递归的深度为O(lg n),于是调⽤栈的⼤⼩也是O(lg n)。因此空间复杂
度并不能被忽略。实际上,我们可以通过将递归转换为迭代来避免空间上的占
⽤
2
,如下⾯的C语⾔例⼦程序。
int min_free(int* xs, int n) {
int l=0;
int u=n-1;
while(n) {
int m = (l + u) / 2;
int right, left = 0;
for(right = 0; right < n; ++ right)
if(xs[right] <= m) {
swap(xs[left], xs[right]);
++left;
}
if(left == m - l + 1) {
xs = xs + left;
n = n - left;
l = m+1;
} else {
n = left;
u = m;
}
}
return l;
}
1
有⼈认为需要O(lg n)的栈空间来做递归调⽤的簿记(book-keeping)。我们稍后会看到,这⼀
调⽤实际上是尾递归,有些编译器,例如gcc可以通过-O2选项消除递归。我们也可以⼿⼯将递归转
换为迭代。
2
由于我们的函数是尾递归形式,⼤多数函数式编程语⾔会⾃动转换优化尾递归函数。
![](https://csdnimg.cn/release/download_crawler_static/76312519/bg11.jpg)
0.3. 丑数――数据结构的威⼒ 17
这段程序使⽤了类似“快速排序”中的分割⽅法将数组中的元素分成两部份。
所有left之前的元素都不⼤于m,⽽所有left和right之间的元素都⼤于m,如
图1所⽰。
x[i]<=m x[i]>m ...?...
left right
图 1: 数组划分的过程。所有位于0 ≤ i < lef t的元素满⾜x[i] ≤ m,所有位
于lef t ≤ i < right的元素满⾜x[i] > m,剩余的元素尚未处理。
这⼀程序运⾏快速并且不需要额外的栈空间。但是和前⾯的Haskell程序⽐起
来,并不那么直观、简洁,需要仔细阅读。有时我们需要在简洁与性能之间进
⾏平衡。
0.3 丑数――数据结构的威⼒
如果说最⼩可⽤ID问题还有⼀些应⽤价值,那么接下来这个问题就纯粹是为
了“有趣”了。我们要寻找第1500个“丑数”。所谓丑数,就是只含有2、3或5这三
个因⼦的⾃然数。前三个丑数按照定义分别是2、3和5。数字60 = 2
2
3
1
5
1
是第25
个丑数。数字21 = 2
0
3
1
7
1
由于含有因⼦7,所以不是丑数。前10个丑数如下表:
2,3,4,5,6,8,9,10,12,15
如果我们认为1 = 2
0
3
0
5
0
也是⼀个合法的丑数,则1就是第⼀个丑数。
0.3.1 暴⼒解法
这道题⽬看起来并不复杂,我们可以从1开始,逐⼀检查所有⾃然数,对于每个
整数,我们⽤除法把所有的2、3和5的因⼦都去掉,如果结果是1,则找到了⼀
个丑数,当遇到第n = 1500个丑数时就找到答案了。
1: function Get-Number(n)
2: x ← 1
3: i ← 0
4: loop
5: if Valid?(x) then
6: i ← i + 1
7: if i = n then
8: return x
9: x ← x + 1
10: function Valid?(x)
11: while x mod 2 = 0 do
12: x ← x/2
![](https://csdnimg.cn/release/download_crawler_static/76312519/bg12.jpg)
18 前⾔
13: while x mod 3 = 0 do
14: x ← x/3
15: while x mod 5 = 0 do
16: x ← x/5
17: if x = 1 then
18: return T rue
19: else
20: return F alse
这⼀暴⼒解法对于较⼩的n没有问题。但是根据这个⽅法编写的C语⾔程
序,在我的计算机上耗时40.39秒才找到了第1500个丑数(859963392)。当试图求
第15000个丑数时,程序运⾏了10分钟也没能找到答案,我只好把它强⾏停⽌。
0.3.2 改进⼀、构造性解法
在上⾯的暴⼒解法中,取模运算和除法运算很耗时[2]。并且这些运算被循环执
⾏了很多次。我们可以转换⼀下思路,不再检查⼀个数是否仅含有是2、3或5的
因⼦,⽽是从这三个因⼦中构造需要的整数。
我们从1开始,分别乘以2或3或5来⽣成整数。这样问题就变成如何依次⽣成
丑数。我们可以使⽤队列这种数据结构来解决这个问题。
队列从⼀侧放⼊元素,然后从另⼀侧取出元素。所以先放⼊的元素会先被取
出。这⼀特性被称为先进先出FIFO(First-In-First-Out)。
我们的思路是先把1作为唯⼀的元素放⼊队列,然后我们不断从队列另⼀侧
取出元素,分别乘以2、3和5,这样就得到了3个新的元素。然后把它们按照⼤
⼩顺序放⼊队列。注意,这样产⽣的整数有可能已经在队列中存在了。这种情
况下,我们需要丢弃重复产⽣的元素。另外新产⽣的整数还有可能⼩于队列尾
部的某些元素,所以我们在插⼊时,需要保持它们在队列中的⼤⼩顺序。图2描
述了这⼀思路的步骤。
根据这⼀思路的算法实现如下:
1: function Get-Number(n)
2: Q ← NIL
3: Enqueue(Q, 1)
4: while n > 0 do
5: x ← Dequeue(Q)
6: Unique-Enqueue(Q, 2x)
7: Unique-Enqueue(Q, 3x)
8: Unique-Enqueue(Q, 5x)
9: n ← n − 1
10: return x
11: function Unique-Enqueue(Q, x)
12: i ← 0
13: while i < |Q| ∧ Q[i] < x do
14: i ← i + 1
15: if i < |Q|∧ x = Q[i] then
16: return
17: Insert(Q, i, x)
在将元素插⼊队列时,算法需要O(|Q|)时间找到合适位置。如果已经存在,
则直接返回。
![](https://csdnimg.cn/release/download_crawler_static/76312519/bg13.jpg)
0.3. 丑数――数据结构的威⼒ 19
1
1*2=2 1*3=3 1*5=5
(1) 初始状态,队列仅含有唯
⼀的元素1
2 3 5
2*2=4 2*3=6 2*5=10
(2) 新产⽣的元素2、3和5加⼊
队列
3 4 5 6 10
3*2=6 3*3=9 3*5=15
(3) 新产⽣的元素4、6和10按照
顺序被插⼊队列
4 5 6 9 10 15
4*2=8 4*3=12 4*5=20
(4) 新产⽣的元素9和15加⼊队
列,重复元素6被丢弃
图 2: 使⽤队列依次⽣成丑数的前4个步骤
粗略估计,队列的长度会随着n增加(每取出⼀个元素会插⼊最多三个新元
素,增加的⽐率≤ 2),所以总运⾏时间为O(1 + 2 + 3 + ... + n) = O(n
2
)。
图3的数据显⽰了队列的访问次数和n之间的关系,这些点连成了⼆次曲线,
反映了算法的复杂度是O(n
2
)。
图 3: 队列访问次数和n的关系
依照此⽅法实现的C语⾔程序仅⽤时0.016秒就输出了正确答案859963392,⽐
暴⼒解法快了2500倍。
这⼀解法也可以⽤递归的⽅式给出,令X为所有仅含有因⼦2、3或5的整数
的⽆穷序列。下⾯的等式给出了⼀个有趣的关系。
X = {1} ∪ {2x : ∀x ∈ X} ∪ {3x : ∀x ∈ X} ∪ {5x : ∀x ∈ X} (2)
其中符号∪表⽰去除重复 并保 持⼤⼩顺序。若X = {x
1
, x
2
, x
3
...},Y =
{y
1
, y
2
, y
3
, ...},X
′
= {x
2
, x
3
, ...},Y
′
= {y
2
, y
3
, ...},我们可以定义∪如下:
![](https://csdnimg.cn/release/download_crawler_static/76312519/bg14.jpg)
20 前⾔
X ∪ Y =
X : Y = ϕ
Y : X = ϕ
{x
1
, X
′
∪ Y } : x
1
< y
1
{x
1
, X
′
∪ Y
′
} : x
1
= y
1
{y
1
, X ∪ Y
′
} : x
1
> y
1
在⽀持惰性求值的函数式编程语⾔,例如Haskell中,上述⽆穷序列及函数可
以定义为如下代码:
ns = 1:merge (map (∗2) ns) (merge (map (∗3) ns) (map (∗5) ns))
merge [] l = l
merge l [] = l
merge (x:xs) (y:ys) | x <y = x : merge xs (y:ys)
| x ==y = x : merge xs ys
| otherwise = y : merge (x:xs) ys
通过求ns !! (n-1),我们可以得到第1500个丑数:
>ns !! (1500-1)
859963392
0.3.3 改进⼆、使⽤多个队列
上⾯的解法虽然⽐暴⼒法快了很多,但是仍然有⼀些不⾜。它会产⽣很多的重
复的元素,并且最终都被丢弃了。其次,它需要扫描队列以保证队列中的元素
有序。因此⼊队操作从常数时间O(1)退化为线性时间O ( |Q|)。
我们可以⽤三个队列来进⾏改进。这三个队列表⽰为Q
2
,Q
3
和Q
5
。它们初
始化为Q
2
= {2},Q
3
= {3}和Q
5
= {5}。我们每次从这三个队列的头部选择最
⼩的⼀个元素x取出,然后进⾏下⾯的检查:
• 如果x是从Q
2
取出的,我们将2x加⼊Q
2
,3x加⼊Q
3
,5x加⼊Q
5
。
• 如果x是从Q
3
取出的,我们只将3x加⼊Q
3
,5x加⼊Q
5
,⽽不需要将2x加
⼊Q
2
。这是因为2x已经在Q
3
中了。
• 如果x是从Q
5
取出的,我们只将5x加⼊Q
5
,⽽不需要处理2x和3x了。
我们不断从这三个队列中取出最⼩的,直到取出第n个元素。图4给出了构造
丑数的前4步。
按照这个思路,算法可以实现如下。
1: function Get-Number(n)
2: if n = 1 then
3: return 1
4: else
5: Q
2
← {2}
6: Q
3
← {3}
7: Q
5
← {5}
8: while n > 1 do
9: x ← min(Head(Q
2
), Head(Q
3
), Head(Q
5
))
10: if x = Head(Q
2
) then
11: Dequeue(Q
2
)
剩余537页未读,继续阅读
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
小胜算法
- 粉丝: 4
- 资源: 2
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- Vue实现iOS原生Picker组件:详细解析与实现思路
- Arduino蓝牙小车:参数调试与功能控制
- 百度Java面试精华:200页精选资源涵盖核心知识点
- Swift使用CoreData填坑指南:CoreData在Swift 3.0的变化
- 微距离无线充电器创新设计及其实验探索
- MTK Android平台开发全攻略:44步详解流程
- RecyclerView全面解析:替代ListView的新选择
- Android开发:自动适配中英文键盘解决方案
- Android调用WebService接口教程
- Android开发:BitmapUtil图片处理全解析与实例
- Android多线程断点续传实现详解
- PCA算法在人脸识别会议签到系统中的应用
- EventBus 3.0:Android事件总线详解与实战应用
- Android FileUtil:全面解析文件操作实用技巧与实例
- RecyclerView添加头部和尾部实战教程
- Android实现微博滑动固定顶部栏实战与优化
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)