算法导论拟阵

1. 关于算法导论

概念：

红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1972年由Rudolf Bayer发明的，他称之为"对称二叉B树"，它现代的名字是在 Leo J. Guibas 和 Robert Sedgewick 于1978年写的一篇论文中获得的。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。

红黑树是一种很有意思的平衡检索树。它的统计性能要好于平衡二叉树(有些书籍根据作者姓名，Adelson-Velskii和Landis，将其称为AVL-树)，因此，红黑树在很多地方都有应用。在C++ STL中，很多部分(目前包括set, multiset, map, multimap)应用了红黑树的变体(SGI STL中的红黑树有一些变化，这些修改提供了更好的性能，以及对set操作的支持)。

背景和术语：
红黑树是一种特定类型的二叉树，它是在计算机科学中用来组织数据比如数字的块的一种结构。所有数据块都存储在节点中。这些节点中的某一个节点总是担当启始位置的功能，它不是任何节点的儿子；我们称之为根节点或根。它有最多两个"儿子"，都是它连接到的其他节点。所有这些儿子都可以有自己的儿子，以此类推。这样根节点就有了把它连接到在树中任何其他节点的路径。

如果一个节点没有儿子，我们称之为叶子节点，因为在直觉上它是在树的边缘上。子树是从特定节点可以延伸到的树的某一部分，其自身被当作一个树。在红黑树中，叶子被假定为 null 或空。

由于红黑树也是二叉查找树，它们当中每一个节点都的比较值都必须大于或等于在它的左子树中的所有节点，并且小于或等于在它的右子树中的所有节点。这确保红黑树运作时能够快速的在树中查找给定的值。
用途和好处：
红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。这不只是使它们在时间敏感的应用如即时应用(real time application)中有价值，而且使它们有在提供最坏情况担保的其他数据结构中作为建造板块的价值；例如，在计算几何中使用的很多数据结构都可以基于红黑树。

红黑树在函数式编程中也特别有用，在这里它们是最常用的持久数据结构之一，它们用来构造关联数组和集合，在突变之后它们能保持为以前的版本。除了O(log n)的时间之外，红黑树的持久版本对每次插入或删除需要O(log n)的空间。

红黑树是 2-3-4树的一种等同。换句话说，对于每个 2-3-4 树，都存在至少一个数据元素是同样次序的红黑树。在 2-3-4 树上的插入和删除操作也等同于在红黑树中颜色翻转和旋转。这使得 2-3-4 树成为理解红黑树背后的逻辑的重要工具，这也是很多介绍算法的教科书在红黑树之前介绍 2-3-4 树的原因，尽管 2-3-4 树在实践中不经常使用。
属性：
红黑树是每个节点都有颜色特性的二叉查找树，颜色的值是红色或黑色之一。除了二叉查找树带有的一般要求，我们对任何有效的红黑树加以如下增补要求:

1.节点是红色或黑色。

2.根是黑色。

3.每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

4.从每个叶子到根的所有路径都包含相同数目的黑色节点。

这些约束强制了红黑树的关键属性: 从根到叶子的最长的可能路径不大于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值都要求与树的高度成比例的最坏情况时间，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。

在很多树数据结构的表示中，一个节点有可能只有一个儿子，而叶子节点包含数据。用这种范例表示红黑树是可能的，但是这会改变一些属性并使算法复杂。为此，本文中我们使用 "null 叶子" 或"空(null)叶子"，如上图所示，它不包含数据而只充当树在此结束的指示。这些节点在绘图中经常被省略，导致了这些树好像同上述原则相矛盾，而实际上不是这样。与此有关的结论是所有节点都有两个儿子，尽管其中的一个或两个可能是空叶子。

操作：
在红黑树上只读操作不需要对用于二叉查找树的操作做出修改，因为它也二叉查找树。但是，在插入和删除之后，红黑属性可能变得违规。恢复红黑属性需要少量(O(log n))的颜色变更(这在实践中是非常快速的)并且不超过三次树旋转(对于插入是两次)。这允许插入和删除保持为 O(log n) 次，但是它导致了非常复杂的操作。

2. 《算法导论》（第三版）目录

1.1 算法

1.2 作为一种技术的算法

2.1 插入排序

2.2 分析算法

2.3 设计算法

2.3.1 分治法

2.3.2 分析分治算法

3.1 渐近记号

3.2 标准记号与常用函数

4.1 最大子数组问题

4.2 矩阵乘法的 Strassen 算法

4.3 用代入法求解递归式

4.4 用递归树方法求解递归式

4.5 用主方法求解递归式

*4.6 证明主定理

4.6.1 对 b 的幂证明主定理

4.6.2 向下取整和向上取整

5.1 雇佣问题

5.2 指示器随机变量

5.3 随机算法

*5.4 概率分析和指示器随机变量的进一步使用

5.4.1 生日悖论

5.4.2 球与箱子

5.4.3 特征序列

5.4.4 在线雇佣问题

6.1 堆

6.2 维护堆的性质

6.3 建堆

6.4 堆排序算法

6.5 优先队列

7.1 快速排序的描述

7.2 快速排序的性能

7.3 快速排序的随机化版本

7.4 快速排序分析

7.4.1 最坏情况分析

7.4.2 期望运行时间

8.1 排序算法的下界

8.2 计数排序

8.3 基数排序

8.4 桶排序

9.1 最小值和最大值

9.2 期望为线性时间的选择算法

9.3 最坏情况为线性时间的选择算法

10.1 栈和队列

10.2 链表

10.3 指针和对象的实现

10.4 有根树的表示

11.1 直接寻址表

11.2 散列表

11.3 散列函数

11.3.1 除法散列法

11.3.2 乘法散列法

*11.3.3 全域散列法

11.4 开放寻址法

11.5 完全散列

12.1 什么是二叉树

12.2 查询二叉搜索树

12.3 插入和删除

12.4 随机构建二叉搜索树

13.1 红黑树的性质

13.2 旋转

13.3 插入

13.4 删除

14.1 动态顺序统计

14.2 如何扩张数据结构

14.3 区间树

15.1 钢条切割

15.2 矩阵链乘法

15.3 动态规划原理

15.4 最长公共子序列

15.5 最优二叉搜索树

16.1 活动选择问题

16.2 贪心算法原理

16.3 赫夫曼编码

*16.4 拟阵和贪心算法

*16.5 用拟阵求解任务调度问题

17.1 聚合分析

17.2 核算法

17.3 势能法

17.4 动态表

17.4.1 表扩张

17.4.2 表扩张和收缩

18.1 B 树的定义

18.2 B 树上的基本操作

18.3 从 B 树上删除关键字

19.1 斐波那契结构

19.2 可合并堆操作

19.3 关键字减值和删除一个结点

19.4 最大度数的界

20.1 基本方法

20.2 递归结构

20.2.1 原型 van Emde Boas 结构

20.2.2 原型 van Emde Boas 结构上的操作

20.3 van Emde Boas 树及其操作

20.3.1 van Emde Boas 树

20.3.2 van Emde Boas 树的操作

21.1 不相交集合的操作

21.2 不相交集合的链表表示

21.3 不相交集合森林

*21.4 带路径压缩的按秩合并的分析

22.1 图的表示

22.2 广度优先搜索

22.3 深度优先搜索

22.4 拓扑排序

22.5 强连通分量

23.1 最小生成树的形成

23.2 Kruskal 算法和 Prim 算法

24.1 Bellman-Ford 算法

24.2 有向无环图中的单源最短路径问题

24.3 Dijkstra 算法

24.4 差分约束和最短路径

24.5 最短路径性质的证明

25.1 最短路径和矩阵乘法

25.2 Floyd-Warshall 算法

25.3 用于稀疏图的 Johnson 算法

26.1 流网络

26.2 Ford-Fulkerson 方法

26.3 最大二分匹配

*26.4 推送-重贴标签算法

*26.5 前置重贴标签算法

27.1 动态多线程基础

27.2 多线程矩阵乘法

27.3 多线程归并排序

28.1 求解线性方程组

28.2 矩阵求逆

28.3 对称正定矩阵和最小二乘逼近

29.1 标准型和松弛型

29.2 将问题表达为线性规划

29.3 单纯形算法

29.4 对偶性

29.5 初始基本可行解

30.1 多项式的表示

30.2 DFT 和 FFT

30.3 高效 FFT 实现

31.1 基础数论概念

31.2 最大公约数

31.3 模运算

31.4 求解模线性方程

31.5 中国余数定理

31.6 元素的幂

31.7 RSA 公钥加密系统

*31.8 素数的测试

*31.9 整数的因子分解

32.1 朴素字符串匹配算法

32.2 Rabin-Karp 算法

32.3 利用有限自动机进行字符串匹配

32.4 Knuth-Morris-Pratt 算法

33.1 线段的性质

33.2 确定任意一对线段是否相交

33.3 寻找凸包

33.4 寻找最近点对

34.1 多项式时间

34.2 多项式时间的验证

34.3 NP 完全性与可归约性

34.4 NP 完全性的证明

34.5 NP 完全问题

34.5.1 团问题

34.5.2 顶点覆盖问题

34.5.3 哈密顿回路问题

34.5.4 旅行商问题

34.5.5 子集和问题

35.1 顶点覆盖问题

35.2 旅行商问题

35.2.1 满足三角不等式的旅行商问题

35.2.2 一般旅行商问题

35.3 集合覆盖问题

35.4 随机化和线性规划

35.5 子集和问题

A.1 求和公式及其性质

A.2 确定求和时间的界

B.1 集合

B.2 关系

B.3 函数

B.4 图

B.5 树

B.5.1 自由树

B.5.2 有根树和有序树

B.5.3 二叉树和位置树

C.1 计数

C.2 概率

C.3 离散随机变量

C.4 几何分布与二项分布

C.5 二项分布的尾部

D.1 矩阵与矩阵运算

D.2 矩阵的基本性质