高级数据结构PDF电子书下载

第1章 哈希表 1

1.1 哈希表的基本原理 1

1.2 哈希表的基本概念 2

1.3 哈希函数的构造 3

1.4 哈希表的基本操作 5

1.5 冲突的处理 6

1.6 哈希表的性能分析 11

1.7 哈希表的应用举例 12

1.8 本章习题 26

第2章 树与二叉树 30

2.1 树 30

2.1.1 树的存储结构 31

2.1.2 树的遍历 32

2.2 二叉树 35

2.2.1 普通树转换成二叉树 37

2.2.2 二叉树的遍历 38

2.2.3 二叉树的其他操作 39

2.2.4 二叉树的形态 41

2.3 二叉排序树 45

2.4 哈夫曼二叉树 61

2.5 字典树 67

2.6 本章习题 79

第3章 优先队列与二叉堆 86

3.1 优先队列 86

3.2 二叉堆 88

3.2.1 Put操作 88

3.2.2 Get操作 89

3.3 可并堆 98

3.3.1 左偏树的定义 98

3.3.2 左偏树的基本操作 99

3.4 本章习题 106

第4章 并查集 113

4.1 并查集的主要操作 113

4.2 并查集的实现 114

4.2.1 并查集的数组实现 114

4.2.2 并查集的链表实现 114

4.2.3 并查集的树实现 115

4.3 并查集的应用举例 119

4.4 本章习题 133

第5章 线段树 140

5.1 线段树的应用背景 140

5.2 线段树的初步实现 140

5.2.1 线段树的结构 140

5.2.2 线段树的性质 141

5.2.3 线段树的存储 141

5.2.4 线段树的常用操作 142

5.2.4.1 线段树的构造 142

5.2.4.2 线段树的查询 143

5.2.4.3 线段树的修改 143

5.2.4.4 线段树的延迟修改 144

5.3 线段树在一些经典问题中的应用 147

5.3.1 逆序对问题 147

5.3.2 矩形覆盖问题 150

5.4 线段树的扩展 155

5.4.1 用线段树优化动态规划 155

5.4.2 将线段树扩展到高维 160

5.4.3 线段树与平衡树的结合 167

5.5 线段树与其他数据结构的比较 176

5.6 线段树的应用举例 176

5.7 本章习题 188

第6章 树状数组 191

6.1 树状数组的问题模型 191

6.2 树状数组的基本思想 191

6.3 树状数组的实现 193

6.3.1 子集的划分方法 193

6.3.2 查询前缀和 194

6.3.3 修改子集和 194

6.4 树状数组的常用技巧 195

6.4.1 查询任意区间和 195

6.4.2 利用sum数组求出原数组a的某个元素值 195

6.4.3 找到某个前缀和对应的前缀下标index 195

6.4.4 成倍扩张／缩减 196

6.4.5 初始化树状数组 196

6.5 树状数组与线段树的比较 196

6.6 树状数组扩展到高维的情形 196

6.7 树状数组的应用举例 197

6.8 本章习题 213

第7章 伸展树 216

7.1 伸展树的主要操作 216

7.1.1 伸展操作 217

7.1.2 伸展树的基本操作 218

7.2 伸展树的算法实现 219

7.3 伸展树的效率分析 223

7.4 伸展树的应用举例 225

7.5 本章习题 237

第8章 Treap 242

8.1 Treap的基本操作 242

8.2 Treap的算法实现 245

8.3 Treap的应用举例 249

8.4 本章习题 255

第9章 平衡树 260

9.1 AVL树 260

9.2 红-黑树 268

9.3 SBT 278

9.3.1 SBT的基本操作 279

9.3.2 SBT的效率分析 284

9.3.3 SBT的算法实现 288

9.4 本章习题 292

第10章 块状链表与块状树 297

10.1 块状链表的基本思想 297

10.2 块状链表的基本操作 298

10.3 块状链表的扩张 302

10.3.1 维护区间和以及区间最值 302

10.3.2 维护局部数据有序化 303

10.3.3 维护区间翻转 303

10.4 块状链表与其他数据结构的比较 303

10.5 分块思想在树上的应用——块状树 303

10.6 块状链表的应用举例 304

10.7 本章习题 335

第11章 后缀树与后缀数组 339

11.1 后缀树的简介 339

11.2 后缀树的定义 339

11.3 后缀树的构建 340

11.3.1 后缀树的朴素构建算法 340

11.3.2 后缀树的线性时间构建算法 340

11.3.2.1 隐式树的朴素构建 341

11.3.2.2 扩展规则约定 342

11.3.2.3 后缀链加速 343

11.3.2.4 进一步加速 344

11.3.2.5 后缀树拓展到多串的形式 345

11.3.2.6 代码实现 345

11.3.2.7 相关证明 351

11.4 后缀树的应用 352

11.4.1 字符串（集合）的精确匹配 352

11.4.1.1 情形一 352

11.4.1.2 情形二 353

11.4.1.3 情形三 353

11.4.1.4 情形四 354

11.4.2 公共子串问题 354

11.4.2.1 情形五 354

11.4.2.2 情形六 355

11.4.2.3 情形七 356

11.4.2.4 情形八 356

11.4.2.5 情形九 358

11.4.3 重复子串问题 358

11.4.3.1 情形十 358

11.4.3.2 情形十一 359

11.4.3.3 情形十二 360

11.5 后缀数组的简介 361

11.6 后缀数组的定义 361

11.7 后缀数组的构建 362

11.7.1 一种直接的构建算法 362

11.7.2 倍增算法 362

11.7.2.1 倍增算法描述 363

11.7.2.2 倍增算法代码 363

11.7.3 由后缀树得到后缀数组 365

11.7.4 DC3算法和DC算法 366

11.7.4.1 DC3算法 366

11.7.4.2 DC算法 371

11.8 LCP的引入 372

11.9 后缀数组的应用 374

11.9.1 后缀排序的直接应用 374

11.9.1.1 Burrows-Wheeler变换 374

11.9.1.2 多模式串的匹配 374

11.9.2 通过引入LCP优化 375

11.9.2.1 多模式串的匹配 375

11.9.2.2 重复子串问题 376

11.9.2.3 最长回文子串 379

11.9.2.4 最长公共子串 380

11.9.3 后缀数组的应用举例 381

11.10 本章习题 399

第12章 树链剖分与动态树 401

12.1 树链剖分的思想和性质 401

12.2 树链剖分的实现及应用 403

12.3 动态树的初探 419

12.3.1 动态树的常用功能 419

12.3.2 动态树的简单情形 420

12.4 动态树的实现 422

12.4.1 动态树的基本操作及其实现 422

12.4.1.1 动态树的问题模型 422

12.4.1.2 用Splay维护实路径 422

12.4.2 动态树操作的时间复杂度分析 424

12.4.2.1 动态树操作的次数 425

12.4.2.2 Splay操作的平摊时间 425

12.5 动态树的经典应用 425

12.5.1 求最近公共祖先 425

12.5.2 并查集操作 425

12.5.3 求最大流 426

12.5.4 求生成树 426

12.6 动态树的应用举例 426

12.7 本章习题 443

致射 445