算法新解

劉新宇，1999年和2001年分別獲得清華大學自動化系學士和碩士學位，之後長期從事軟件研發工作。他關注基本算法和數據結構，尤其是函數式算法，目前就職於亞馬遜中國倉儲和物流技術團隊。
 

序一常成博士，4數網主編
序二姚冬，YY直播架構師
前言

第一部分樹

第1章二叉搜索樹：數據結構中的“hello world” 3 

1.1定義3 
1.2數據組織5 
1.3插入6 
1.4遍歷8 
1.5搜索10 
1.5.1 lookup 10 
1.5.2最小元素和最大元素11 
1.5.3前驅和後繼12 
1.6刪除14 
1.7隨機構建二叉搜索樹18 

第2章插入排序的進化19 

2.1簡介19 
2.2插入20 
2.3改進一：二分查找20 
2.4改進二：使用鍊錶22 
2.5使用二叉搜索樹的最終改進26 
2.6小結27 

第3章並不復雜的紅黑樹28 

3.1紅黑樹的定義32 
3.2插入33 
3.3刪除36 
3.4命令式的紅黑樹算法* 44 
3.5小結47 

第4章AVL樹48

4.1 AVL樹的定義48 
4.2插入51 
4.2.1平衡調整53 
4.2.2模式匹配57 
4.3刪除59 
4.4 AVL樹的命令式算法* 59 
4.5小結63 

第5章基數樹：Trie和Patricia 65 

5.1整數Trie 65 
5.1.1整數Trie的定義67 
5.1.2插入67 
5.1.3查找69 
5.2整數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的應用92 
5.5.1電子詞典和單詞自動補齊92 
5.5.2 T9輸入法97 
5.6小結102 

第6章後綴樹103

6.1後綴Trie 104 
6.1.1節點轉移和後綴鏈接105 
6.1.2 on-line構造107 
6.2後綴樹111 
6.3後綴樹的應用121 
6.3.1字符串搜索和模式匹配121 
6.3.2查找最長重複子串123 
6.3.3查找最長公共子串125 
6.3.4查找最長回文127 
6.3.5其他128 
6.4小結128 

第7章B樹129 

7.1插入131 
7.2刪除139 
7.2.1刪除前預合併139 
7.2. 2先刪除再修復139 
7.3搜索153 
7.4小結155 

第二部分堆

第8章二叉堆159 

8.1用數組實現隱式二叉堆159 
8.1.1定義159 
8.1.2 Heapify 160 
8.1.3構造堆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使用左偏堆實現堆排序174 
8.2.5 skew堆174 
8.3伸展堆177 
8.3.1定義177 
8.3.2堆排序183 
8.4小結183 

第9章從吃葡萄到世界杯：選擇排序的進化184 

9.1查找最小元素186 
9.1.1標記186 
9.1.2分組188 
9.1.3選擇排序的性能189 
9.2細微改進190 
9.2.1比較方法參數化190 
9.2.2細微調整191 
9.2.3雞尾酒排序192 
9.3本質改進196 
9.3.1錦標賽淘汰法196 
9.3.2使用堆排序進行最後的改進204 
9.4小結204 

第10章二項式堆、斐波那契堆和配對堆205 

10.1二項式堆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配對堆237 
10.3.1定義237 
10.3.2基本堆操作238 
10.4小結244 

第三部分隊列和序列

第11章並不簡單的隊列247 

11.1單向鍊錶和循環緩衝區實現的隊列247 
11.1.1單向鍊錶實現247 
11.1.2循環緩衝區實現251 
11.2純函數式實現253 
11.2.1雙列表隊列254 
11.2.2雙數組隊列：一種對稱實現255 
11.3小改進：平衡隊列257 
11.4進一步改進：實時隊列259 
11.5惰性實時隊列266 
11.6小結269 

第12章序列：最後一塊磚271 

12.1二叉隨機訪問列表271 
12.1.1普通數組和列表271 
12.1.2使用森林表示序列272 
12.1.3在序列的頭部插入273 
12.2二叉隨機訪問列表的數值表示279
12.3命令式雙數組列表285 
12.3.1定義285 
12.3.2插入和添加286 
12.3.3隨機訪問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刪除時處理不規則的手指樹300 
12.5.5在序列的尾部添加元素304 
12.5.6從尾部刪除元素306 
12.5.7連接307 
12.5.8手指樹的隨機訪問312 
12.6小結325 

第四部分排序和搜索

第13章分而治之：快速排序和歸併排序329 

13.1快速排序329 
13.1.1基本形式330 
13.1.2嚴格弱序331 
13.1.3劃分331 
13.1.4函數式劃分算法的小改進335 
13.2快速排序的性能分析337 
13.3工程實踐中的改進340 
13.4針對最差情況的工程實踐348
13.5其他工程實踐351 
13.6其他351 
13.7歸併排序352 
13.8原地歸併排序360 
13.8.1死板原地歸併360 
13.8.2原地工作區362 
13.8.3原地歸併排序與鍊錶歸併排序366 
13.9自然歸併排序368 
13.10自底向上歸併排序374 
13.11並行處理377 
13.12小結377 

第14章搜索379 

14.1序列搜索379 
14.1.1分而治之的搜索379 
14.1.2信息復用400 
14.2解的搜索428 
14.2.1深度優先搜索和廣度優先搜索428 
14.2.2搜索最優解468 
14.3小結498 

附錄列表500 
列表的定義500 
列表的基本操作502 
變換527 
提取子列表536 
fold 543 
搜索和匹配549 
zip和unzip 555 
小結558 
參考文獻559
索引563