《恶评算法导论》http://t.cn/A6Yn0jOZ

在之前一篇文章里，我提到学会 AVL tree 或者 b tree 的重要性。后来在基础班的讨论会，有同学问我他还听说过「红黑树」（red-black tree），问我红黑树和 AVL tree 有什么差别。我只告诉他红黑树是“随机的”，并不是精确地平衡的，所以查找效率没有 AVL tree 那么有保证。

其实我没写过红黑树。最早的时候我学的是 AVL tree，并实现过它。虽然我实现过 AVL tree，但当时觉得很麻烦，很容易弄错，所以其实害怕写它。因为对 AVL tree 的恐惧，又听说红黑树更简单，而且好像效率差不多，就以为红黑树是好东西。后来每次看书上讲的红黑树，都没看明白它是怎么回事，也没动手实现过红黑树。然而我仍然觉得红黑树比 AVL tree 好，因为人们都那么说。

我之前为什么害怕写 AVL tree 呢？本科学数据结构的时候，我用 C 语言写过 AVL tree，当时觉得很容易弄错，很麻烦。后来学会了高级一些的语言和正确的编程理念，才发现之前写 AVL tree 觉得很难，大部分是因为之前的编程教学的误导。当年的老师们总是一来就跟学生强调“函数调用的开销大”，要避免写不必要的函数。所以 AVL tree 保持平衡的代码都直接写在同一个 insert 函数里面，而没有“帮助函数”。因为没有把“左转”和“右转”的代码单独写成帮助函数，所以就很混乱，缺乏模块化，容易出错。就算最后折腾出来，也不好理解，也许还有隐藏的 bug。后来就忘了怎么写出来的。

一般人学这种数据结构，最后差不多都是这种结局。学过，写过，然后就忘了。

总之，早年对 AVL tree 的恐惧，加上对红黑树的各种宣传（却没有实际的理解），导致了我以为红黑树会更好。既然有同学提起红黑树，我就想起这个事，而且我意识到“红黑树更好”这个想法，也许是一种误传。所以我查了一下红黑树和 AVL tree 的差别，发现这篇 Stack Overflow 帖子。

排名最高的回答说，对于“insert intensive”的任务使用红黑树，他好像觉得 AVL tree 的旋转操作更多。下面几个其它人也这么认为，然而这些回答全都只有说法，而没有依据。

想想，AVL 和红黑树这种平衡树，要加入新 key 的时候，都需要先进行查找，就成了 O(log n) 时间。因为红黑树不是精确的平衡，它的高度一般比 AVL 要高，查找的路径长，所以谁的加入速度快，还真不一定。旋转操作其实不是那么费时间的，都是 O(1) 操作。而且我真的看不出来“红黑树旋转少”这个说法有什么依据。

这条回答还抬出一些“权威实践”作为依据。说 Java 和 C++ 的标准库代码，还有 Linux 内核的调度器里面，都用的红黑树。然而我觉得这些都不能作为依据。特别是 Linux 内核调度器这种东西，我不明白调度器为什么会需要用到查找结构。调度器本来不会有很多需要查找的数据，所以对于查找不应该有什么特别的要求，随便用一种数据结构应该都能满足要求，甚至可以根本不用这类数据结构。其实 Linux 内核调度器折腾了几万行代码，弄得很复杂，效果还不如 FreeBSD 3000 行代码的简单调度器。可以参考这个讲座。

在后面终于看到有人提了一句，说很多人用红黑树，是因为他们只学过红黑树，从没学过 AVL tree，因为《算法导论》（评论中提到的“CLRS”）里面没讲 AVL tree，只讲了红黑树。而且好的 AVL tree 代码实现比较难找到。

这篇回复引起了我的注意。《算法导论》就是那本“MIT 经典算法教材”，英文名为《Introduction to Algorithms》。四个作者的名字开头连起来是 CLRS，所以常被称为 CLRS。似乎每个计算机科学领域都会出现这么一本“经典教材”，忽然间垄断世界上几乎所有大学的教学。这些“经典教材”一般写得都不咋地，甚至之前从来没听说过那些作者。我一直纳闷为什么会出现这样的现象。

所以《算法导论》没讲 AVL tree，这个事情引起了我的注意。在我看来，AVL tree 就是查找二叉树（binary search tree, BST）的一个自然而简单扩展。有了 BST 之后，只需要加上“平衡”这个特性，它就成了 AVL tree。所以之前的数据结构课，讲了 BST 之后一般都是讲 AVL tree。然而看《算法导论》的目录，我发现它讲了 BST 之后，直接就是红黑树，完全没有 AVL tree 的章节。这很奇怪。

另外翻到后面讲 b tree 的章节（第 18 章），我发现它只讲了 b tree 的基本的加入节点和“节点分裂”操作，却只字没提到 b tree 和 AVL tree 一样，是需要进行“平衡”的，否则不能保证查找效率。书中举的加入节点的例子，正好是平衡的例子，没出现需要旋转的情况，所以读者看了还以为 b tree 加入节点操作就这么简单。然而其实保持平衡才是 b tree 最烧脑的操作。如果你没把握它的思路，会比 AVL tree 还烧脑。

所以《算法导论》直接没讲 AVL tree，而 b tree 章节中只字不提“平衡旋转操作”。这让我产生了对《算法导论》作者们的严重怀疑，他们到底知不知道什么是 b tree？没有平衡旋转操作的“b tree”并不是真的 b tree！作为这么多大学使用的教材，这种严重的“疏忽”是不可接受的。

所以我才意识到，为什么之前我提到自己实现了 b tree 之后，有些人例行地评论：”王垠实现了个 b tree，就以为了不起”。他们天真地以为 b tree 是《算法导论》讲过的，所以他们已经理解了 b tree 是什么，所以实现了 b tree 不算什么。然而他们真的知道 b tree 是什么吗？他们亲手实现过真正的 b tree 吗？

仔细看看《算法导论》的 b tree 代码吧，那能叫代码吗？那只是“伪码”，是不能运行的，而且它的样式非常的糟糕，混淆而难以理解。在我看来，这些代码一塌糊涂，难以入目。直接忽略平衡操作，伪码还看不明白，你说学生看这书，怎么可能写出真正的 b tree 代码来？

不知从什么时代开始，算法书上开始用“伪码”表示程序，而不是真实可以运行的代码。教授们告诉人们“伪码”的好处，说它可以避免学生被一种语言套住，更加简洁云云。然而我发现实际情况却是，伪码并不比实际的编程语言简洁。正好相反，这些“伪码语言”可以很糟糕，比如《算法导论》里的伪码。所以《算法导论》是用一种很糟糕的语言，写出了一些难以入目的不能运行的代码。

真正的数据结构和算法教学，必须使用真的可以运行的代码，而不是伪码。否则就只有纸上谈兵，自以为懂了。

这也许就是为什么之前在某公司需要用 b tree 的时候，我发现网络上找不到好的 b tree 代码可以用。就像之前的评论里说的，好的 AVL tree 的实现很难找，好的 b tree 实现当然更难找。《算法导论》的效果，尽然是让 AVL tree 和 b tree 的知识消失！

所以多年之后回头看《算法导论》，我对它的评价已经跌入谷底。为什么这种误人子弟的“经典教材”不断地出现？我感觉到有 Matrix 的隐秘操作在里面。也许这种教材的出现不是为了改善教学，而是为了实现 Matrix 的愚民计划。他们知道，如果人们的头脑里没有真的知识，就能被任意地操纵。