CLRS 上对 Red Black Tree (RBT) 的介绍简直是一团乱麻，代码又乱，解释又罗嗦，我完全没有实现它的兴趣……
不得不佩服 Robert Sedgewick 啊，他在 Algorithms in C 里先介绍 2-3-4 Tree，把 RBT 作为 2-3-4 Tree 的一种表示方式来介绍 Red Black Tree，这样就清楚多了。当然，Sedgewick 本来就是 Red Black Tree 的发明者之一 <http://en.wikipedia.org/wiki/Red-black_tree>，他能够讲清楚也就不奇怪了。除了解释清楚以外，Sedgewick 使用递归实现，因此代码很简洁，看起来很舒服。
不过即使如此，Red Black Tree 还是很复杂，所以即使看了 Sedgewick 的代码以后还是没有自己实现的冲动。好在 Sedgewick 已经考虑过这个问题，其结果就是 Left-Leaning Red Black Tree<http://www.cs.princeton.edu/%7Ers/talks/LLRB/RedBlack.pdf>。（这 份幻灯片做得非常好！Apple 的 Keynote 貌似不错啊。）LLRBT 跟 RBT 的不同之处在于 2-3-4 Tree 的 3 node 在 LLRBT 中只有一种表示方式，因此 LLRBT 减少了 RBT 的插入/删除需要处理的情况数量，从而大大减小了复杂度。RBT 的 Java 迭代实现要用 150 行代码，而递归实现需要 46 行代码，LLRBT 递归则只需要 33 行。删除需要的代码行数也大大减小了，实现难度当然也大大降低了。
> CLRS 上对 Red Black Tree (RBT) 的介绍简直是一团乱麻，代码又乱，解释又罗嗦，我完全没有实现它的兴趣……
> 不得不佩服 Robert Sedgewick 啊，他在 Algorithms in C 里先介绍 2-3-4 Tree，把 RBT 作为 2-3-4 > Tree 的一种表示方式来介绍 Red Black Tree，这样就清楚多了。当然，Sedgewick 本来就是 Red Black Tree > 的发明者之一 <http://en.wikipedia.org/wiki/Red-black_tree>，他能够讲清楚也就不奇怪了。除了解释清楚以外，Sedgewick > 使用递归实现，因此代码很简洁，看起来很舒服。
> 不过即使如此，Red Black Tree 还是很复杂，所以即使看了 Sedgewick 的代码以后还是没有自己实现的冲动。好在 Sedgewick > 已经考虑过这个问题，其结果就是 Left-Leaning Red Black Tree<http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf>。（这份幻灯片做得非常好！Apple > 的 Keynote 貌似不错啊。）LLRBT 跟 RBT 的不同之处在于 2-3-4 Tree 的 3 node 在 LLRBT > 中只有一种表示方式，因此 LLRBT 减少了 RBT 的插入/删除需要处理的情况数量，从而大大减小了复杂度。RBT 的 Java 迭代实现要用 150 > 行代码，而递归实现需要 46 行代码，LLRBT 递归则只需要 33 行。删除需要的代码行数也大大减小了，实现难度当然也大大降低了。
> CLRS 上对 Red Black Tree (RBT) 的介绍简直是一团乱麻，代码又乱，解释又罗嗦，我完全没有实现它的兴趣……
> 不得不佩服 Robert Sedgewick 啊，他在 Algorithms in C 里先介绍 2-3-4 Tree，把 RBT 作为 2-3-4 > Tree 的一种表示方式来介绍 Red Black Tree，这样就清楚多了。当然，Sedgewick 本来就是 Red Black Tree > 的发明者之一 <http://en.wikipedia.org/wiki/Red-black_tree>，他能够讲清楚也就不奇怪了。除了解释清楚以外，Sedgewick > 使用递归实现，因此代码很简洁，看起来很舒服。
> 不过即使如此，Red Black Tree 还是很复杂，所以即使看了 Sedgewick 的代码以后还是没有自己实现的冲动。好在 Sedgewick > 已经考虑过这个问题，其结果就是 Left-Leaning Red Black Tree<http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf>。（这份幻灯片做得非常好！Apple > 的 Keynote 貌似不错啊。）LLRBT 跟 RBT 的不同之处在于 2-3-4 Tree 的 3 node 在 LLRBT > 中只有一种表示方式，因此 LLRBT 减少了 RBT 的插入/删除需要处理的情况数量，从而大大减小了复杂度。RBT 的 Java 迭代实现要用 150 > 行代码，而递归实现需要 46 行代码，LLRBT 递归则只需要 33 行。删除需要的代码行数也大大减小了，实现难度当然也大大降低了。
|
