CLRS学习指南

学习笔记 算法

以下内容源自2015年寒假的教学笔记，适用于2016年的学习，持续更新，请保持关注。有问题请发Email联系bintou2010@qq.com.

第一部分 基础

第一章 算法

1、什么是算法？（An algorithm is thus a suquence of computational steps that transform the input into the output.）
大家还需要去找答案，注意要进一步归纳总结。

术语：

• computational problem（计算性问题）

• decisional problem（判定性问题）

• 计算领域三大问题：什么是计算机？什么问题可计算（可解）？解某个问题需要多长时间、消耗多少资源？

2、算法能解决什么问题？
书本给出了很多实例，说明算法能解决很多很多问题，似乎要显示说算法无所不能。其实我们必须关心，什么问题算法不能解决。

扩展：停机问题（什么是停机问题，有什么重大意义？）

3、什么是数据结构？
需要慢慢填空......

4、难解问题
概念： P、NP、NPC，不理解可跳过，记住P是多项式时间内可解的问题集合即可。
思考： 难题为什么是难？有什么已知的难题？
换一个角度思考： 什么是容易解的问题？
术语： reduction（规约），这不容易的。主要用于对NPC的描述。

5、算法的效率
用实际的运算给出直观的感受，读者必须去感受。
比较：$log(N)$，$sqrt(N)$，$N$，$N^2$，$2^N$ ，$N!$

6、算法以及其他技术的讨论
讨论内容，有很多很多“？”，不是难点，但需要思考，对初学者，这种思考往往是提高水平的正确路径。

7、扩展思考与检索
为什么说算法是计算机科学的核心内容？算法的研究起源在哪里？什么时候开始人们认为：算法奠定了计算机科学的基础？

第二章 算法起步

2.1、插入排序（以实例带动讲解）

术语：Loop invariants（循环不变量？）
这是CLRS分析算法的一种重要技巧，要认真理解为何引入这个概念，以后如何运用这个概念。

伪代码的表示法，简单工作！

2.2、算法分析模型

2.2.1 重点：RAM

注意：本书讲解RAM以牺牲准确性为代价获得更通俗易懂的表达，原始的RAM模型可没这么简单。但是我喜欢这种讲解。
扩展思考：除了RAM模型还有什么分析算法的模型？

Additional Comments about RAM: 由于不少同学纷纷表示对RAM的不理解，我多说几句。首先声明，不理解RAM模型并不会严重影响后续阅读，所以你可以非常放心目前的“不理解”。但我依然建议大家看看多两遍课本这并不冗长的两页说明讲解。以下是一些要点：

1. RAM模型是用于分析算法的一种计算模型；并非真实的计算机。
2. 一种计算模型通常会包括：指令、内存、数据类型、指令调度等内容。然而，书本并不讲解这些，反而是强调，不要滥用RAM模型。言外之意是，这些我就不多说了，只要不按常规来，不乱出牌，基本就ok...... （体会，2.2 第三段的这种含义）。说白了，这里给出RAM模型但是并没有具体解释RAM模型！
3. 数据类型，只强调一点，大小为n的整数可以表达为c lg n比特。言外之意还是，不要乱来即可。（2.2 第四段）
4. 指令、内存层次结构、单cpu、指令的串行执行等等要求都非常常规。（2.2 第五、六段）
5. 指出分析是困难的，但难点是在数学：组合数学、概率论、代数等，跟RAM没多大关系。（2.2 第七段）
6. 最后展望未来，我们还有很多可以选择的计算模型。

总而言之，准确定义计算模型是复杂的，在保证计算模型不被滥用的情况下，我们可以牺牲准确性而得到相应的简洁性与清晰性。对于初入门的CSers，刚学完C语言的同学，刚好你们不懂什么内存层次、并发计算等（即所谓“滥用”之处），所以，把RAM下的程序理解为一般的C语言程序则刚刚好。毕竟你们想滥用模型也往往不知道如何滥用（这样说真的不好吗？）。

2.2.2 插入排序的效率分析

一个实例。
扩展思考：冒泡排序的效率如何分析？是什么？与插入排序相比，哪个算法更好？或者，各有什么优势劣势？

2.2.3 Worst-case and average-case analysis（难点！）

为何要区分两种不同的效率分析？如何理解这两个概念？我们更需要的是那种效率？

例子：对整数x、y，求x^y需要多少时间？也许我们没有准确答案，大概我们知道计算x的y次方要比计算x+y要耗更多的时间。然而，如果x = 2，算2^y只需要进行y次左移，并不比x + y慢。也就是说，在特定的情况下我们也许会有非常高效的算法，然而在一般情况下，算法需要执行更多的时间。因此我们需要平均复杂性来衡量这样的一般情况。有时候我们对特定情形下的最短时间并不感兴趣，因为我们比较保守，此时我们会问，最多需要多少时间（上界）来完成这项工作。此时，我们考虑最怀情况下的复杂性。

2.3、算法设计

重点：分治法
实例：归并排序，相信大家可以愉快地阅读下去，请注意Loop invariants的使用。
提示：递归树是非常好的工具，用起来！

2.4、习题（提示：该做题了！）

2.5、编程题

此题源自于某位同学的提问，课本建议“将插入排序与归并排序结合使用，当一组数的个数足够小时，使用插入排序进行处理，再进行合并”。从而提高排序的效率。问题是如何判断数组个数是多少才足够小呢？我的建议是，编程测试。
1、设计实现插入排序与归并排序结合使用的排序程序；
2、设置一个变量控制何时进行插入排序；
3、对1000k的随机数组进行排序，测试显示在不同的控制下排序的效率。

第三章 函数的增长

3.1、Asymptotic notation（渐进表示法）：Big O，Omiga，Theta

术语：上界、下界、紧致界
简单而言：最多做多少步？最少做多少步？最多做那么多步且最少也需要这么多步！
难点1：相关计算，多做题！

难点2：恼人的常数c
同学提问，常数c到底是多少？怎么理解BigO等等表达中需要乘一个常数？

回答：要理解这个恼人的c，首先要明白渐进式表达是一种松散的界，c可以理解为松散度系数。其次我们要理解这个c往往不影响我们的结论，尽管我们不知道它的真实大小。例子：考虑快速排序与归并排序，都是O(n lg n)的复杂度。那么我们可以说它们分别低于c_1 n lg n
（记为f）和c_2 n lg n（记为g），其中c_1和c_2是两个不同的常数，我们并不知道具体数值。现在我们想比较这两种排序的大小，因为我们很担心不同的常数项会对我们造成影响，f/g = c_1/c_2，得到一个常数！尽管我们还是不知道f/g的大小，但是我们知道这两个数值相比只差一个常数，当n增加得很大的时候，常数不变，往往就显得无关紧要了。值得注意的是，这里只是说，通常情况下c不影响，并不是说常数永远不对算法复杂性有影响。

3.2、标准表达及常用函数

提示：有很多比较难的函数，不一定要死记（能记住也是鼓励的！），先知道，用到了再查。或者在以后以专题的形式重点攻克。比如：Stirling公式。

Side Comments：曾经与某同学讨论算法的学习，他说自己学得很慢，碰到每一个难题都想去解决（不解决就不舒服斯基），不解决就没办法看其他内容。我不很同意这种做法，不懂应该成为常态！要先建立一种全局观，并有整体的思路，允许存在以后解决的技术和理论难点。拿这里来说，两页书的公式包含了很多的数学内容，就单单是一个Stirling公式，我就没有把握需要多少时间去把握它。如果纠结一个Stirling公式而不去看以下的内容，有意义吗？当然，相信这位同学也不是在纠结Stirling公式，只是举一个例子。

提示：除了理解和做题还有什么办法？

3.3、测试

以下测试是在CLRS的作者Cormen的主页上找到的，建议做一做：

• quiz--comparing-function-growth
• asymptotic-notation/e/quiz--asymptotic-notation

第四章 Recurrences（递归式）

本章讲解三种计算渐进复杂性界的方法：替换法、递归树法以及Master Theorem（主定理？？）

4.1 最大子数组问题

暂略～

4.2 矩阵乘法

暂略～

4.3、替换法：猜一个结果、证明结论（归纳法证明）

技巧1：猜测结果减去一个低阶子项使得证明得证；注意边界条件，可令n 大于某个 n_0项，使得边界条件成立。

技巧2：换元法，例如，令 m = lg n 。适用于处理递归式中有sqr(n)的情形。

4.4、递归树法

本质上是通过构造递归树，得到一个正确的猜测。还是要通过替换法进行结论证明！

4.5、主定理：菜谱式定理，证明可以先跳过。

目标：给定 T(n) = aT(n/b) + f(n)，a,b > 1，f(n)为正函数。求递归式的界。

直观上（忽略某些细节而言），是通过比较$n^{(log_b a)}$ 与 f(n)的大小进行判断:如果前者大，则是$\Theta(n^{(log_b a)})$；如果是后者大，答案则是$\Theta(f(n))$；如果一样大，则要乘上一个对数函数子项得到$\Theta(n^{(log_b a)} lg n)$ = $\Theta(f(n) lg n)$。

思考：为何是比较$n^{(log_b a)}$ 与 f(n)的大小呢？
提示：$n^{(log_b a)}$ 是不是等于 $a^{(log_b n)}$ ？ $a^{(log_b n)}$在递归式中代表什么含义？

Comment1：这种方法并不是万能的，有很大的局限。其次，在运用中不能忽略某些细节，比如，大小的比较，在这里要求的是多项式大或者多项式小。

Comment2：第一次阅读不要求证明并不能说明这里的证明就非常难。绝非如此，这个证明没有使用到复杂的技巧，只要把握住“递归树”的思路，理解并不困难。不畏难的同学，在进度跟得上的前提下，可先行阅读。特别是在假设$n=2^b$下的证明，不难理解。

Comment3：有意思的是，在应用替换法、递归树法、主定理方法做题的时候，同学们都会很自觉地根据自己的喜好进行选用。实际上，他们应该是对这三种方法有自己的评判和选择（能说是偏见吗？），但是又不自觉地归纳总结出来。比如，有同学认为替换法很随意，也难以猜对，所以不使用。又比如：有同学认为Master Theorem只是套公式，是死记硬背，没什么意思，也不选用。然后，认为递归树法比较靠谱。其实，我认为这样的理解都颇为片面。

首先，我提倡大家猜！要知道能建立一种直观是非常重要的，不要忘记，“猜”就是一种能力，在科研起步的早期，使用“猜”的方法去培养直观可又大收获。其次，使用递归树法不要忘记证明！递归树只不过是帮助猜测的的一种方法，结论必须得到证明。第三，有菜谱为何不用？没错，是死记硬背，不要忘记，“记忆力”就是智商的一种！而且，这套方法是前人经过整理证明出来的有效方法，可直接使用，因为担心自己不理解而不去使用算不算“因噎废食”？

因此，在此我提倡，做题的时候三种方法都使用起来。首先猜，猜对猜不对都要去猜一下。其次，画递归树，能画不能画都去尝试一下。如果递归树或者替换法能得到答案，最后用Master Theorem验证一下自己的答案。

当然，这并非万能方法。也许我们可以不断积累技巧，其中，“换元法”我还是建议大家多多练习。

2016年3月注记：最近，15图灵班对“主定理“的证明进行了讨论，也是本学期的第一次讨论。效果不错，讨论热烈。讨论过程表示，同学们基本上理解了该定理，也掌握了其中基本的证明技巧。相信，继续下去，这个讨论班会有较大的收获。

4.6、做习题检验这三种方法。本章强调练习！

第五章 概率分析与随机算法

建议在没有概率论基础时忽略。当然，这里要求的概率基础也比较少。建议掌握一些相关概念，比如，什么是概率分析，什么是随机算法。

期望大家走到这里的时候不要超过一周时间！

补录：
在实际的学习过程中，我还是坚持要求学生们进行了概率分析的学习，困難是他们没有上过概率课。因此，简单地补了几个概念：示性随机变量、期望值、期望的线性性。结果，此章的内容可以顺利完成。

这说明：在需要的时候对某些知识点进行补充并非不可能完成的任务。反过来证明了那些在此却步的同学并非能力不足，而是信心不足。

第二部分 排序与序性统计

这一部分出了讲排序等算法之外，实际上也讲了一种简单数据结构--数组和堆。

第六章 堆排序

6.1 堆

堆可以视为一种完全二叉树，也可视为数组。理解堆的关键不在堆本身，我宁愿大家先理解完全二叉树。估计，作者此处假设读者已经掌握了一定的树的知识。如果你在第一次阅读碰到困难，不妨停下来看看树的概念，并画一棵树，然后体会、理解、证明几个关于树的结论。

树的概念：根、节点、叶子、左儿子、右儿子、父节点、树的高度

关于树的结论：n个元素的完全二叉树的高度是floor(lg n)；高度为h的完全二叉树的元素个数最多（最少）是多少？n个元素的完全二叉树，叶子的数目最多是多少？这些结论通常可以自己总结，然后用归纳法进行证明。

6.2、堆的操作与堆排序

有了树的概念之后，堆的操作与堆排序都是容易理解的。

6.5 优先队列

第七章 快速排序

这一章可说的东西暂时不多。相信大部分同学已经知道并学习过这个算法。与之前学习稍有区别的是，这里是讲两个版本的快排算法：确定性算法与随机化算法。后者与前者只有微妙的区别，就是在选择主元的时候是均匀随机地选择。

对随机快排的思考：为什么需要这样做？何时需要这样做？这样做得到什么好处？

这一章的难点在QSort的效率分析。由于是概率分析，在没有概率基础的情况下，暂时跳过。

排序算法的两种重要属性：in-place 和 stable。

QSort中的Partition方法比较，这篇Blog的回答真是太专业了。为什么Hoare的Partition算法更有优势反而不写在正文，留做思考题呢？

经验教训：简单的概率知识作为CLRS的先验知识还是非常有必要。实际上，所需要的概率知识也不是很多，应该在第一学期就适当地让同学们掌握。比如，使用Pass等人的Discrete Mathematics的Lecture作为基础就不错。

第八章 线性时间排序算法

1、排序算法的下界
利用判定树模型证明所有使用元素对比的排序算法的复杂度下界是$\Omega(n*log ~\ n)$。基本思路：判定树是一棵二叉树，中间节点是元素之间的对比，叶子是排好序后数组下标的全排列（有点绕口）。如果有n个元素，则数组下标的全排列有n!种可能，即判定树的叶子个数（记为l）至少有n!个。二叉树的树高为h，它有多少叶子？把以上推理记为：n! <= l <= 2^h 。简单计算得出结论。

难点在于判定树模型，为何可以把HeapSort、QSort、MergeSort等等使用对比的排序算法的行为抽象为判断树？我暂时也没有非常合理简单的讲解可以提供，需要大家自己体会。其实我看书本也没能解释得很清楚。总而言之，结论非常重要。

扩展思考、练习： 如何比较HeapSort、QSort、MergeSort的优劣？它们都有相同的复杂性，而且已经达到最优，说明它们的性能相同？最好用实践来检验，任何已知结论都不可靠，需要验证。

2、计数排序
这是一种具有线性复杂性的排序算法，当然，有优势必然要付出一定的代价。
思考：这里的代价是什么呢？

基本思路：所有待排序的元素（或用于排序的关键字）都是某个范围之内的整数值。首先，输入待排序的数组A，统计其中某个数值出现的次数，存于C数组；从而得出小于或等于某个数值的数值的个数，还是存于C数组；最后，根据C数组的统计，将A数组中的元素放入数组B合适的位置中，B即为输出。这三个步骤都是线性时间的复杂度，加起来依然是线性复杂度。

3、基数排序
基本思路：首先，把待排序元素的键值分成d个数位，每个digit有k个可能值。然后使用具有stability属性（比如，使用计数排序）的排序算法，分别针对d个数位进行排序。复杂性：Theta(d*(n+k))。基数排序的快速依赖于它调用的计数排序。

思考：线性时间的基数排序是不是击败了其他所有的排序算法？为何？

4、桶排序
基本思路：对n个元素进行排序，均匀随机地将这n个元素丢入n个桶之中。每个桶都有一个编号n_i，编号越小的桶里面的元素就越小。使用插入排序对桶中元素进行排序。按桶编号顺序输出桶中元素。

复杂性分析：里面用到了随机变量、随机变量的期望等概率论中内容。抛开这些不谈，能不能从直观上看到某些东西呢？把n个元素丢入桶中需要的时间是Theta(n)，然后对n个桶中的元素排序。每一个桶假设有n_i个元素，那么就需要O(n_i^2)的时间（插入排序！）。拍脑瓜的时候来了，均匀随机地在n个桶中放n个元素，平均（所谓期望无非就是平均）每个桶里面有多少个元素？如果你算对了，书上的那一堆吓人的公式大概都是浮云了~

提示：桶排序使用了特定的数据结构，可在后续数据结构的内容学完之后再对桶排序进行编程练习。

第九章 中值及序位统计

本章最难懂不是其算法，而是其标题（吐槽！）。中文版直接将Statistics翻译为统计学（“中位数和顺序统计学”）让人摸不着头脑。实际上，本章只是考虑对n个元素求其最小值、最大值和中间值；一般化地，求n个元素的第i小的那个元素，称为Selection算法。

1、最大值与最小值
简单思路： 按顺序从第一个元素开始，逐个元素对比，并保存下当前最大（最小）的元素位置。Theta(n)的复杂性。

疑问：这样做是不是最好的做法（常用词：optimal）呢？答案，yes！继续提问：why？

稍微难一点的问题：如何同时求最大值与最小值。

2、平均复杂性为线性时间的Selection算法
思路：使用QSort算法对数组进行划分的思路，是一种分治法，使用了递归。
提示：放心跳过大量的概率复杂性分析。

3、最坏情况为线性时间的Selection算法
思路：
复杂性分析：

第二部分结束。个人认为，第二部分的内容比第一部分稍容易，除了概率分析（刚好大家也可以跳过）之外，没有什么理论难点。所以，期望大家走到这里只是第二周学习的结束。无论你认为是快还是慢，都可以反思一下，为什么？也可以进行讨论。

第三部分 数据结构

相信CLRS的作者会假定自己的学生或者读者懂一点点数据结构，但是要求掌握的并不多（也许这种要求之低可以低到以至于可以忽略）。因此，在引入数据结构的时候，作者强调了“动态集合”的操作：检索、插入、删除、最小值、最大值、前驱成员、后继成员等，完全是高度的抽象。字典是本章主要考察的实现对象。

反思：在学习CLRS之前是否需要集合论及简单的数据结构知识？尽管不知道大家如何想，实际上，如果CLRS是第一学期之后学习，要满足这两种前驱知识的需求也并不难达到。

注意：本章强调实践，使用C++及OO编程的技术做完本章习题，基本就覆盖了普通Data Structures with C++ 的内容（我对比了William Ford的《Data Structures with C++》的目录得出此结论）。如果我的学生可以完成这些内容的学习，就必须问一句：数据结构还必须那样教吗？

第十章 基础数据结构

1、栈与队列
应该没有什么难度，大家可以自学并实现相关算法。自觉利用OO编程，设计相关的Object。

2、链接表
唯一的难点在于：指针！所以，还是认为第一学期的课程必须包括指针编程的训练。

3、实现指针与对象
这一节讲解如何在不提供指针与对象的程序语言中实现指针与对象。很奇怪的目的，是吗？因为我们现在大部分的语言都已经实现了指针与对象。所以，看完这一章感觉不奇怪的话，那么任务就完成了。不要忘记，C/C++是使用其他程序语言实现的程序语言。我们往往对C语言中的指针运算感到困惑，比如指针的++、--运算，指针的指针，指针的指针的指针等等，扫除这些困惑的一种方法就是了解这种变量的实现方法！（注，问正确的问题，是你走出正确理解的重要一步。）

4、表达有根树
这一节有两个重要内容：二叉树与带根树的实现方法。需要讲解的内容不多，重点在于通过指针结构实现树及其各种遍历、查询。有根树与二叉树的区别仅仅在于前者的节点会有任意多个后代节点，每一个节点都有一个指针指向自己的父亲节点，也有一个指针指向自己的右边兄弟节点。编程！

第11章 Hash表
Hash表是实现字典的有效数据结构。Hash表也许会被翻译为”哈希表“或者“散列表”，只是这种翻译也许并不需要。直观而言，字典，即通过关键词检索相对应的数据项。

1、直接寻址
使用关键词（key）作为存储的检索号（对应一个存储位置：slot）。高效简单，前提是key的范围足够小。

2、Hash表
与直接寻址相比，这里使用Hash函数将Key映射到一个存储位置K。使用Hash函数的原因是Key的范围很大，但是真正使用到的Key只是一小部分。比如，中国有13亿人口，要存储所有人的个人信息。如果以姓名为Key，这也许是一个无穷大的范围，我们没必要为每一个可能存在的姓名准备一个存储位置。

因此，这里的关键是设计合理的Hash函数。我们要求Hash函数可高效实现，并且尽可能避免碰撞（Collision）。所谓碰撞，即存在两个不同的key，k1和k2，使得h(k1) == h(k2)。首先，我们看Hash函数h的定义，一定要明确，碰撞存在！为什么？

当碰撞发生之后，如何处理存在的冲突呢？ Chaining！

3、Hash函数
解决上一节遗留问题，如何设计“好”的Hash函数。

a. 什么是好的Hash函数？

b. 使用除法

c. 使用乘法

* Universal Hashing 第一次阅读跳过，然而开学后的学习中Universal Hashing依然是可以进行的内容。目前看效果一般，主要是更深入的学习与研究没办法开展。另外就是此内容在表述上不同的教材有一定的区别，也带来一定的困难。不过，依然令人满意。以后可以以专题的形式再次学习。

4.开放寻址
不使用列表，在数组的基础上直接实现碰撞发生的处理。算法简单，分析有点困难，还是要卡在随机变量及期望！放过定理证明先。

*5、完全Hash (暂时跳过)

第12章 二叉搜索树
1、 什么是二叉搜索树 ？
二叉搜索树是满足以下特性的二叉树：x是树的节点，x的左子树的所有非空节点的key都比x的key要小，x的右子树的所有非空节点的key都比x的key要大。
三种遍历方式：前序、中序与后序。简单而言，从根出发，有三种选择：先访问根节点再访问子树；先访问左子树，访问根节点，再访问右子树；先访问子树，最后访问根节点。

2、二叉搜索树的查询、遍历
容易！理解思路：树是一种递归结构，即树的子孙节点都是一棵树。因此，首先通过递归的思路去理解是最合适的。比如：简单的中序遍历来说，输入：一棵树的树根。遍历：递归遍历树根的左子树，访问树根节点，递归遍历树根的右子树。

3、二叉搜索树的插入与删除
插入算法容易。删除算法稍微复杂。这里要注意，第三版在此处有非常大的改进。我看的是第二版，情况分析是清晰的，但是伪代码经过了整合优化，可读性较差。第三版的Delete算法描述清晰BigO(n)倍。所以，无论多么著名的书，都可以质疑。

一个简单的证明题，用于帮助理解删除操作过程：删除z节点，当其左子树与又子树都不为Nil，找其successor y节点（Case 3） 。请证明，y的左子树必为nil。

若干课外资料：
a、一份纯C的BST教程，作者声称非常不喜欢理论:-D。
b、一份Python的BST教程，适当的时候可以学习一下Python。

*4、二叉搜索树的随机生成
给定一系列元素，以随机的顺序将它们插入二叉树中。目的，得到一棵“较矮”的树。重点在概率分析。

第13章 红黑树
本章的主要任务还是与树的高度作斗争，要得到矮的树，关键是要树平衡发展。红黑树是一种特殊的二叉搜索树，每一个节点增加一个颜色属性（红节点或者黑节点），目的是建立平衡二叉树，这是重点也是难点。
1、什么是红黑树
红黑树有五点属性需要把握：每个节点不是红就是黑；根节点是黑节点；所有的叶子都是黑；每一个红节点的孩子都是黑节点；每一节点走到叶子的不同路径包含相同个数的黑节点（保证黑高相同，也就保证了树高的平均）。

2、树的旋转
一种插入、删除的辅助操作，用于保证红黑树的属性。容易～

3、插入、删除
与二叉树的插入删除主要有一点不同，即插入、删除会导致红黑树属性变化，因此必须修补，使得原有属性得以保持。这里应该算是一个难点，也许是除了数学概率分析之外，数据结构当中的第一个难点。要克服这里的困难应该如何做？建议在阅读了基本内容（先忽略大部分的算法）之后，多用笔纸画图，对不同实例进行分析，比如，在何种情况下插入节点会（或者不会）导致属性改变？首先要通过这种简单的运算得到直观，再详细阅读课本印证自己的观点。简而言之，作图将会给你带来理解上的帮助。

当困难到来的时候、考验到来的时候，离进步就不远了。你只需要深呼吸、沉一口气，把它攻克下来！ 当然也需要讲一点学习技巧。1、手头有笔纸，把5种RBT的属性记下来作参考。2、根据不同的实例不断画图。3、跟着作者的思路，doubly-black node是一个关键。4、对RBT不要着急编程，不要让程序成为你理解的绊脚石。先理解，让程序成为你加深理解的工具。

问题：为何在RBTree中使用T.nil取代原来BSTree中的NIL？
回答：首先要注意到T.nil是object，具备各种attributes；不同的是，NIL只是一个标记。其次，T.nil的作用很大，书本用了一个高度概况的字眼来描述：处理RBTree处理中的边界条件。实际上，在详细分析算法的时候，对RBTree进行处理的几种操作包括对叶子的操作，比如，旋转。这个时候叶子就不能仅仅是一个标记，而是一个完整的对象。这种情况很多，你如果没有发现，说明你对算法的分析没有覆盖算法执行的许多情形。为什么要统一用一个T.nil？答案就简单了，节省空间。这是一个好问题。如果你没有理解到这个问题的价值，说明你没有真正理解T.nil的作用与意义。

第14章 数据结构的扩展
本节内容试图在“教科书式”数据结构与“工程实践中”的数据结构之间搭建桥梁，通过实例展示在工程实践中如果扩展教科书数据结构来完成特定的功能、满足相关的要求。大部分的情况下，我们只需要“扩展”教科书数据结构，而无需重新定义全新的数据结构。那些张口就说“学校授课内容很重要，但是......”“老师授课只注重理论，缺乏实践......”的人请闭嘴吧，至少你要明白什么是“工程实践”再说话，明白教科书、老师怎么理解“工程实践”再瞎说吧。

这一部分的内容主要还是关于红黑树。

1、动态序性统计
红黑树的一种应用，在节点中增加某些信息，用于讲O(n)复杂度的序性统计下降到O(lg n)。可作为第二节的引入。

2、如何扩展数据结构
四个步骤，一个定理。

3、区间树
这一节是对第2节所提出方法的具体实例。

本部分难度不大，但考虑到本部分需要大量的编程，10天时间完成吧！搞完了就安心过春节了。

第四部分 高级算法设计与分析
高级，到底高级在哪里？Advanced，我宁愿理解为“更进一步”的。在此之前的算法设计与分析只有分治法，到了这一章我们并不是抛弃分治法另起炉灶，而是，进一步，进一步......，一步一步地使得算法具有更好的效率。如果这么想，整个思路就很清晰了：动态规划这一章就是讲当大问题分解成子问题，如果重复的子问题不断出现该如何解决。贪心算法更进一步，如果子问题的分割在特定问题的时候具有某种可利用的属性，那么我们可以如何优化算法。因此，不要被“高级”吓倒，也不要被“高级”误导：这里的内容不存在更高级别的抽象，而且思路与之前的内容联系紧密，并非逻辑关联性不强的飞跃。因此，第一个问题必须改成：Where do you advance from？

第15章 动态规划
动态规划只是一个名词，完全无法体现其应有的内涵。

第16章 贪心算法

第17章 平摊分析法
平摊分析的目的？
平摊分析的三种方法：累加平均、记账法、势能分析法。
理解的难度不大。最大的收获在讲解习题、看视频（竞争分析）。
如何灵活使用？

以上内容，从阅读的角度，一个星期也许够了，但是从做题的角度看，我无法估计！建议尽可能快地完成本部分阅读。然后进入一个反馈循环，再阅读再讨论，加强习题。

第五部分 高级数据结构

第18章、B树
平衡的搜索树，主要用于磁盘检索。每个节点有多个键值，有多个孩子节点。我认为需要提醒的两点：插入只在叶子进行；删除可在任意节点进行。叶子的定义与BST树有重大区别。

第19章、Fibonacci堆
1、之前有Binary Heap的内容，为何要提出Fibonacci Heap？有何优势？有何劣势？具体操作怎么做？复杂性是多少？解决这些基本问题。
2、这种Heap与Fibonacci数列有什么关系？这是难点。

第20章、van Emde Boas树
发明者Peter van Emde Boas，荷兰科学家。简记为vEB树。

第21章、用于不相交集合的数据结构

高级数据结构之所有“高级”的原因是什么？ “进一步”，到底是如何进一步的？思考！

第六部分 图算法

第七部分 高级专题

Appendix A. 本文助记符（统一借助LaTex的记号）
1、"^" 代表“帽子”，N^2表示N的平方。
2、“_"代表下标，比如n_2表示n带下标2。
3、"\in" 表示集合的包含关系，比如，A \in B表示A集合是B集合的子集。
4、BigO，Theta，Omiga，一个英国朋友，两个希腊朋友:-D
5、floor、ceiling，分别代表下取整与上取整的那两个符号。

Appendix B. 相关网络资源
0、CLRS的主页
1、《算法导论》网易公开课
2、作者之一Cormen的主页
3、作者之一Rivest的主页（大名鼎鼎的图灵奖得主啊！）
4、Khan Academy‘s algorithms tutorials
5、进阶阅读：Readings in Algorithms，Stanford的一门课程，里面有比较前沿的papers列表，还有我希望大家可以学习的FFT。留给我自己看看。
6、Algorithm Unlocked，CLRS作者之一的Cormen的新作，据说比CLRS更浅显易懂。我看过目录和部分章节，易懂也许是的，但是内容就少了很多，而且论述的顺序与风格充满了作者的个人趣味。按作者的本意来说，Algorithm Unlocked只是一盘开胃菜，可以作为学习CLRS的辅助阅读。我看确实如此！然而我看不出有任何理由推荐我的学生去看这本书，因为对大部分的人而言这真是很大一盘餐前小点，你很容易就找出很多很多理由拒绝进行这样的学习：哇啊是英语；哇啊真是太理论；哇啊我又不做科学家.....如果你真的下决心去吃它，还不如立即开始CLRS。如果你不下决心，去浅尝则止，收获也不会很多，那还不如不看。（2015年2月5日补记.）
7、Algorithms，Papadimitriou等人2006年出版的一本算法书，我经常翻看，还不错，篇幅小，简洁。有中文注释版名为《算法概论》，推荐购买。这是一篇网络评论。
8、Algorithm Design，Jon Kleinberg 等人2005年的著作，非常著名。不适合入门，有些高级且较新的内容。这里有Lecture Slides.（当年大一就抱着它啃的哪位同学估计已经放弃算法学习了吧......）
9、http://codeforces.com/，竞赛网站？据说有很多好的代码。