由刘新宇所著的《算法新解／图灵原创》一书是按照教材的风格编写的，由浅入深，每个算法从实际应用场景出发，阐述数学原理，再给出伪代码，并且提供实际可以运行的实现。最后，作者还给出了供课后思考练习的习题。我希望这本书有机会成为计算机教学中的基础教材之一。

这本书采用了一种新颖的发布方式，它像一个开源软件项目一样，作者像管理源代码一样管理书的内容，允许读者参与其中贡献思路代码，帮助修改错误，以及在其整个生命周期罩持续改进。

由刘新宇所著的《算法新解／图灵原创》一书分4部分，同时用函数式和传统方法介绍主要的基本算法和数据结构，数据结构部分包括二叉树、红黑树、AVL树、Trie、Patricia、后缀树、B树、二叉堆、二项式堆、斐波那契堆、配对堆、队列、序列等；基本算法部分包括各种排序算法、序列搜索算法、字符串匹配算法（KMP等）、深度优先与广度优先搜索算法、贪心算法以及动态规划。

本书适合软件开发人员、编程和算法爱好者，以及高校学生阅读参考。

序一 常成博士，4数网主编

序二 姚冬，YY直播架构师

前言

第一部分 树

 第1章 二叉搜索树：数据结构中的“hello world”

1.1 定义

1.2 数据组织

1.3 插入

1.4 遍历

1.5 搜索

 1.5.1 lookup

 1.5.2 最小元素和最大元素

 1.5.3 前驱和后继

1.6 删除

1.7 随机构建二叉搜索树

 第2章 插入排序的进化

2.1 简介

2.2 插入

2.3 改进一：二分查找

2.4 改进二：使用链表

2.5 使用二叉搜索树的最终改进

2.6 小结

 第3章 并不复杂的红黑树

3.1 红黑树的定义

3.2 插入

3.3 删除

3.4 命令式的红黑树算法

3.5 小结

 第4章 AVL树

4.1 AVL树的定义

4.2 插入

 4.2.1 平衡调整

 4.2.2 模式匹配

4.3 删除

4.4 AVL树的命令式算法

4.5 小结

 第5章 基数树：Trie和Patricia

5.1 整数Trie

 5.1.1 整数Trie的定义

 5.1.2 插入

 5.1.3 查找

5.2 整数Patricia

 5.2.1 定义

 5.2.2 插入

 5.2.3 查找

5.3 字符Trie

 5.3.1 定义

 5.3.2 插入

 5.3.3 查找

5.4 字符Patricia

 5.4.1 定义

 5.4.2 插入

 5.4.3 查找

5.5 Trie和Patricia的应用

 5.5.1 电子词典和单词自动补齐

 5.5.2 T9输入法

5.6 小结

 第6章 后缀树

6.1 后缀Trie

 6.1.1 节点转移和后缀链接

 6.1.2 on-line构造

6.2 后缀树

6.3 后缀树的应用

 6.3.1 字符串搜索和模式匹配

 6.3.2 查找最长重复子串

 6.3.3 查找最长公共子串

 6.3.4 查找最长回文

 6.3.5 其他

6.4 小结

 第7章 B树

7.1 插入

7.2 删除

 7.2.1 删除前预合并

 7.2.2 先删除再修复

7.3 搜索

7.4 小结

第二部分 堆

 第8章 二叉堆

8.1 用数组实现隐式二叉堆

 8.1.1 定义

 8.1.2 Heapify

 8.1.3 构造堆

 8.1.4 堆的基本操作

 8.1.5 堆排序

8.2 左偏堆和skew堆：显式的二叉堆

 8.2.1 定义

 8.2.2 合并

 8.2.3 基本堆操作

 8.2.4 使用左偏堆实现堆排序

 8.2.5 skew堆

8.3 伸展堆

 8.3.1 定义

 8.3.2 堆排序

8.4 小结

 第9章 从吃葡萄到世界杯：选择排序的进化

9.1 查找最小元素

 9.1.1 标记

 9.1.2 分组

 9.1.3 选择排序的性能

9.2 细微改进

 9.2.1 比较方法参数化

 9.2.2 细微调整

 9.2.3 鸡尾酒排序

9.3 本质改进

 9.3.1 锦标赛淘汰法

 9.3.2 使用堆排序进行最后的改进

9.4 小结

 第10章 二项式堆、斐波那契堆和配对堆

10.1 二项式堆

 10.1.1 定义

 10.1.2 基本的堆操作

10.2 斐波那契堆

 10.2.1 定义

 10.2.2 基本堆操作

 10.2.3 弹出操作的性能分析

 10.2.4 减小key

 10.2.5 “斐波那契堆”名字的由来

10.3 配对堆

 10.3.1 定义

 10.3.2 基本堆操作

10.4 小结

第三部分 队列和序列

 第11章 并不简单的队列

11.1 单向链表和循环缓冲区实现的队列

 11.1.1 单向链表实现

 11.1.2 循环缓冲区实现

11.2 纯函数式实现

 11.2.1 双列表队列

 11.2.2 双数组队列：一种对称实现

11.3 小改进：平衡队列

11.4 进一步改进：实时队列

11.5 惰性实时队列

11.6 小结

 第12章 序列：最后一块砖

12.1 二叉随机访问列表

 12.1.1 普通数组和列表

 12.1.2 使用森林表示序列

 12.1.3 在序列的头部插入

12.2 二叉随机访问列表的数值表示

12.3 命令式双数组列表

 12.3.1 定义

 12.3.2 插入和添加

 12.3.3 随机访问

 12.3.4 删除和平衡

12.4 可连接列表

12.5 手指树

 12.5.1 定义

 12.5.2 向序列的头部插入元素

 12.5.3 从头部删除元素

 12.5.4 删除时处理不规则的手指树

 12.5.5 在序列的尾部添加元素

 12.5.6 从尾部删除元素

 12.5.7 连接

 12.5.8 手指树的随机访问

12.6 小结

第四部分 排序和搜索

 第13章 分而治之：快速排序和归并排序

13.1 快速排序

 13.1.1 基本形式

 13.1.2 严格弱序

 13.1.3 划分

 13.1.4 函数式划分算法的小改进

13.2 快速排序的性能分析

13.3 工程实践中的改进

13.4 针对最差情况的工程实践

13.5 其他工程实践

13.6 其他

13.7 归并排序

13.8 原地归并排序

 13.8.1 死板原地归并

 13.8.2 原地工作区

 13.8.3 原地归并排序与链表归并排序

13.9 自然归并排序

13.10 自底向上归并排序

13.11 并行处理

13.12 小结

 第14章 搜索

14.1 序列搜索

 14.1.1 分而治之的搜索

 14.1.2 信息复用

14.2 解的搜索

 14.2.1 深度优先搜索和广度优先搜索

 14.2.2 搜索最优解

14.3 小结

附录 列表

 列表的定义

 列表的基本操作

 变换

 提取子列表

 fold

 搜索和匹配

 zip和unzip

 小结

参考文献

索引