算法新解

序一 常成博士，4數(shù)網(wǎng)主編
序二 姚冬，YY直播架構(gòu)師
前言
第一部分 樹
第1章 二叉搜索樹：數(shù)據(jù)結(jié)構(gòu)中的“hello world” 3
1．1 定義 3
1．2 數(shù)據(jù)組織 5
1．3 插入 6
1．4 遍歷 8
1．5 搜索 10
1．5．1 lookup 10
1．5．2 最小元素和最大元素 11
1．5．3 前驅(qū)和后繼 12
1．6 刪除 14
1．7 隨機(jī)構(gòu)建二叉搜索樹 18
第2章 插入排序的進(jìn)化 19
2．1 簡(jiǎn)介 19
2．2 插入 20
2．3 改進(jìn)一：二分查找 20
2．4 改進(jìn)二：使用鏈表 22
2．5 使用二叉搜索樹的最終改進(jìn) 26
2．6 小結(jié) 27
第3章 并不復(fù)雜的紅黑樹 28
3．1 紅黑樹的定義 32
3．2 插入 33
3．3 刪除 36
3．4 命令式的紅黑樹算法 * 44
3．5 小結(jié) 47
第4章 AVL樹 48
4．1 AVL樹的定義 48
4．2 插入 51
4．2．1 平衡調(diào)整 53
4．2．2 模式匹配 57
4．3 刪除 59
4．4 AVL樹的命令式算法 * 59
4．5 小結(jié) 63
第5章 基數(shù)樹：Trie和Patricia 65
5．1 整數(shù)Trie 65
5．1．1 整數(shù)Trie的定義 67
5．1．2 插入 67
5．1．3 查找 69
5．2 整數(shù)Patricia 70
5．2．1 定義 71
5．2．2 插入 72
5．2．3 查找 78
5．3 字符Trie 80
5．3．1 定義 80
5．3．2 插入 81
5．3．3 查找 83
5．4 字符Patricia 84
5．4．1 定義 84
5．4．2 插入 85
5．4．3 查找 90
5．5 Trie和Patricia的應(yīng)用 92
5．5．1 電子詞典和單詞自動(dòng)補(bǔ)齊 92
5．5．2 T9輸入法 97
5．6 小結(jié) 102
第6章 后綴樹 103
6．1 后綴Trie 104
6．1．1 節(jié)點(diǎn)轉(zhuǎn)移和后綴鏈接 105
6．1．2 on-line構(gòu)造 107
6．2 后綴樹 111
6．3 后綴樹的應(yīng)用 121
6．3．1 字符串搜索和模式匹配 121
6．3．2 查找最長(zhǎng)重復(fù)子串 123
6．3．3 查找最長(zhǎng)公共子串 125
6．3．4 查找最長(zhǎng)回文 127
6．3．5 其他 128
6．4 小結(jié) 128
第7章 B樹 129
7．1 插入 131
7．2 刪除 139
7．2．1 刪除前預(yù)合并 139
7．2．2 先刪除再修復(fù) 139
7．3 搜索 153
7．4 小結(jié) 155
第二部分 堆
第8章 二叉堆 159
8．1 用數(shù)組實(shí)現(xiàn)隱式二叉堆 159
8．1．1 定義 159
8．1．2 Heapify 160
8．1．3 構(gòu)造堆 163
8．1．4 堆的基本操作 164
8．1．5 堆排序 168
8．2 左偏堆和skew堆：顯式的二叉堆 169
8．2．1 定義 170
8．2．2 合并 172
8．2．3 基本堆操作 173
8．2．4 使用左偏堆實(shí)現(xiàn)堆排序 174
8．2．5 skew堆 174
8．3 伸展堆 177
8．3．1 定義 177
8．3．2 堆排序 183
8．4 小結(jié) 183
第9章 從吃葡萄到世界杯：選擇排序的進(jìn)化 184
9．1 查找最小元素 186
9．1．1 標(biāo)記 186
9．1．2 分組 188
9．1．3 選擇排序的性能 189
9．2 細(xì)微改進(jìn) 190
9．2．1 比較方法參數(shù)化 190
9．2．2 細(xì)微調(diào)整 191
9．2．3 雞尾酒排序 192
9．3 本質(zhì)改進(jìn) 196
9．3．1 錦標(biāo)賽淘汰法 196
9．3．2 使用堆排序進(jìn)行最后的改進(jìn) 204
9．4 小結(jié) 204
第10章 二項(xiàng)式堆、斐波那契堆和配對(duì)堆 205
10．1 二項(xiàng)式堆 205
10．1．1 定義 205
10．1．2 基本的堆操作 209
10．2 斐波那契堆 220
10．2．1 定義 220
10．2．2 基本堆操作 221
10．2．3 彈出操作的性能分析 230
10．2．4 減小key 232
10．2．5 “斐波那契堆”名字的由來 234
10．3 配對(duì)堆 237
10．3．1 定義 237
10．3．2 基本堆操作 238
10．4 小結(jié) 244
第三部分 隊(duì)列和序列
第11章 并不簡(jiǎn)單的隊(duì)列 247
11．1 單向鏈表和循環(huán)緩沖區(qū)實(shí)現(xiàn)的隊(duì)列 247
11．1．1 單向鏈表實(shí)現(xiàn) 247
11．1．2 循環(huán)緩沖區(qū)實(shí)現(xiàn) 251
11．2 純函數(shù)式實(shí)現(xiàn) 253
11．2．1 雙列表隊(duì)列 254
11．2．2 雙數(shù)組隊(duì)列：一種對(duì)稱實(shí)現(xiàn) 255
11．3 小改進(jìn)：平衡隊(duì)列 257
11．4 進(jìn)一步改進(jìn)：實(shí)時(shí)隊(duì)列 259
11．5 惰性實(shí)時(shí)隊(duì)列 266
11．6 小結(jié) 269
第12章 序列：最后一塊磚 271
12．1 二叉隨機(jī)訪問列表 271
12．1．1 普通數(shù)組和列表 271
12．1．2 使用森林表示序列 272
12．1．3 在序列的頭部插入 273
12．2 二叉隨機(jī)訪問列表的數(shù)值表示 279
12．3 命令式雙數(shù)組列表 285
12．3．1 定義 285
12．3．2 插入和添加 286
12．3．3 隨機(jī)訪問 286
12．3．4 刪除和平衡 287
12．4 可連接列表 289
12．5 手指樹 293
12．5．1 定義 293
12．5．2 向序列的頭部插入元素 295
12．5．3 從頭部刪除元素 298
12．5．4 刪除時(shí)處理不規(guī)則的手指樹 300
12．5．5 在序列的尾部添加元素 304
12．5．6 從尾部刪除元素 306
12．5．7 連接 307
12．5．8 手指樹的隨機(jī)訪問 312
12．6 小結(jié) 325
第四部分 排序和搜索
第13章 分而治之：快速排序和歸并排序 329
13．1 快速排序 329
13．1．1 基本形式 330
13．1．2 嚴(yán)格弱序 331
13．1．3 劃分 331
13．1．4 函數(shù)式劃分算法的小改進(jìn) 335
13．2 快速排序的性能分析 337
13．3 工程實(shí)踐中的改進(jìn) 340
13．4 針對(duì)最差情況的工程實(shí)踐 348
13．5 其他工程實(shí)踐 351
13．6 其他 351
13．7 歸并排序 352
13．8 原地歸并排序 360
13．8．1 死板原地歸并 360
13．8．2 原地工作區(qū) 362
13．8．3 原地歸并排序與鏈表歸并排序 366
13．9 自然歸并排序 368
13．10 自底向上歸并排序 374
13．11 并行處理 377
13．12 小結(jié) 377
第14章 搜索 379
14．1 序列搜索 379
14．1．1 分而治之的搜索 379
14．1．2 信息復(fù)用 400
14．2 解的搜索 428
14．2．1 深度優(yōu)先搜索和廣度優(yōu)先搜索 428
14．2．2 搜索最優(yōu)解 468
14．3 小結(jié) 498
附錄 列表 500
列表的定義 500
列表的基本操作 502
變換 527
提取子列表 536
fold 543
搜索和匹配 549
zip和unzip 555
小結(jié) 558
參考文獻(xiàn) 559
索引 563