CLRS 上对 Red-Black Tree (RBT) 的介绍简直是一团乱麻,代码又乱,解释又罗嗦,我完全没有实现它的兴趣……
不得不佩服 Robert Sedgewick 啊,他在 Algorithms in C 里先介绍 2-3-4 Tree,把 RBT 作为 2-3-4 Tree 的一种表示方式来介绍 RBT,这样就清楚多了。当然,Sedgewick 本来就是 Red-Black Tree 的发明者之一,他能够讲清楚也就不奇怪了。除了解释清楚以外,Sedgewick 使用递归实现,因此代码很简洁,看起来很舒服。
不过即使如此,Red-Black Tree 还是很复杂,所以即使看了 Sedgewick 的代码以后还是没有自己实现的冲动。好在 Sedgewick 已经考虑过这个问题,其结果就是 Left-Leaning Red-Black Tree。(这份幻灯片做得非常好!Apple 的 Keynote 貌似不错啊。)LLRBT 跟 RBT 的不同之处在于 2-3-4 Tree 的 3-node 在 LLRBT 中只有一种表示方式,因此 LLRBT 减少了 RBT 的插入/删除需要处理的情况数量,从而大大减小了复杂度。RBT 的 Java 迭代实现要用 150 行代码,而递归实现需要 46 行代码,LLRBT 递归则只需要 33 行。删除需要的代码行数也大大减小了,实现难度当然也大大降低了。
我用 Common Lisp 试着实现了 LLRBT,确实很简单。不过我还在想怎样才能迭代实现 LLRBT,找到了 FreeBSD 用头文件实现的 LLRBT,被彻底雷到了,这宏用的太牛了!
Update: 其实 LLRBT 是在好几个月前看到的,最近才想到写出来。FreeBSD 中 LLRBT 实现的作者 Jason Evans 写过一篇文章 “Left-leaning red-black trees are hard to implement“,不过他写文章时候使用的算法中 4-node 对应 RBT 中向左倾斜的 3 个节点,可能因此比较难以实现。Sedgewick 在后来的幻灯片中更新了算法,4-node 变为平衡的三个节点。Evans 还比较了 LLRBT 和其他树实现的性能,在文章的注释中也提到了他将算法改为迭代所采用的办法。