{Algo}说到红黑树

4003 views
Skip to first unread message

pongba

unread,
Jul 7, 2008, 10:23:42 AM7/7/08
to TopLanguage

就恰好看到chen yufei同学的博客上提到了。我得去看看Sedgewick老大是怎么说的。

via: http://chenyufei.name/blog/2008-07-07/left-leaning-red-black-tree/

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 的发明者之一,他能够讲清楚也就不奇怪了。除了解释清楚以外,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,被彻底雷到了,这宏用的太牛了!

prince on 7 July, 2008 at 7:35 pm #

wikipedia 上的RB-tree也是一坨的,看了都不想看。
最后还是死啃 CLRS 书看懂红黑树的。
不过让我现在描述红黑树,还是没有把握记得。

--
刘未鹏(pongba)|C++的罗浮宫
http://blog.csdn.net/pongba
TopLanguage
http://groups.google.com/group/pongba

hayate

unread,
Jul 7, 2008, 1:16:18 PM7/7/08
to pon...@googlegroups.com
感谢。
rb-tree已经忘了,但是我还记得当年在图书馆默写它的情景 :D
 
CLRS这部分确实不好看来不是我一个人的感觉,似乎书上一上来就列举rb-tree应该满足的几个条件,但是对于怎么想出这个tree以及怎么得出这些条件却语焉不详。

2008/7/7 pongba <pon...@gmail.com>:

就恰好看到chen yufei同学的博客上提到了。我得去看看Sedgewick老大是怎么说的。

via: http://chenyufei.name/blog/2008-07-07/left-leaning-red-black-tree/

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 的发明者之一,他能够讲清楚也就不奇怪了。除了解释清楚以外,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,被彻底雷到了,这宏用的太牛了!

Chen Yufei

unread,
Jul 7, 2008, 10:41:27 PM7/7/08
to TopLanguage
如果没有 Algorithms in C 的话直接看那份幻灯片好了, 书上的内容在幻灯片里面都有的。

FreeBSD 中 LLRBT 实现的作者 Jason Evans 写过一篇文章 “Left-leaning red-black trees
are hard to implement“<http://www.canonware.com/~ttt/2008/04/left-
leaning-red-black-trees-are-hard.html>,不过他写文章时候使用的算法中 4-node 对应 RBT 中向左
倾斜的 3 个节点,可能因此比较难以实现。Sedgewick 在后来的幻灯片中更新了算法,4-node 变为平衡的三个节点。Evans 还比较
了 LLRBT 和其他树实现的性能,在文章的注释中也提到了他将算法改为迭代所采用的办法。

pongba

unread,
Jul 7, 2008, 10:45:18 PM7/7/08
to pon...@googlegroups.com


2008/7/8 Chen Yufei <cyfd...@gmail.com>:

如果没有 Algorithms in C 的话直接看那份幻灯片好了, 书上的内容在幻灯片里面都有的。 

恩,谢谢yufei提醒。
P.S. 昨天下到了Algorithms in Java。应该讲的是一样的,除了语言实现的细节差别之外。
 
FreeBSD 中 LLRBT 实现的作者 Jason Evans 写过一篇文章 "Left-leaning red-black trees
are hard to implement"<http://www.canonware.com/~ttt/2008/04/left-
leaning-red-black-trees-are-hard.html
>,不过他写文章时候使用的算法中 4-node 对应 RBT 中向左
倾斜的 3 个节点,可能因此比较难以实现。Sedgewick 在后来的幻灯片中更新了算法,4-node 变为平衡的三个节点。Evans 还比较
了 LLRBT 和其他树实现的性能,在文章的注释中也提到了他将算法改为迭代所采用的办法。

pongba

unread,
Jul 8, 2008, 10:28:06 AM7/8/08
to pon...@googlegroups.com
基本看完了那个ppt。对于没有看的同学我还要再次大力推荐一下。这恐怕是目前为止地球上对红黑树讲得最透彻的ppt了。

2008/7/8 pongba <pon...@gmail.com>:



2008/7/8 Chen Yufei <cyfd...@gmail.com>:

如果没有 Algorithms in C 的话直接看那份幻灯片好了, 书上的内容在幻灯片里面都有的。 

恩,谢谢yufei提醒。
P.S. 昨天下到了Algorithms in Java。应该讲的是一样的,除了语言实现的细节差别之外。
 

David

unread,
Jul 9, 2008, 2:40:28 AM7/9/08
to TopLanguage
讲解的确很详细,不过好长。pongba有空不妨写一篇Introduction to RBT。

On 7月8日, 下午10时28分, pongba <pon...@gmail.com> wrote:
> 基本看完了那个ppt。对于没有看的同学我还要再次大力推荐一下。这恐怕是目前为止地球上对红黑树讲得最透彻的ppt了。
>
> 2008/7/8 pongba <pon...@gmail.com>:
>
>
>
> > 2008/7/8 Chen Yufei <cyfde...@gmail.com>:

Lee MaRS

unread,
Jul 9, 2008, 3:18:29 AM7/9/08
to pon...@googlegroups.com
看那个PPT就行了。

pongba写出来的只可能会比那个更长。

2008/7/9 David <chinata...@gmail.com>:

pongba

unread,
Jul 9, 2008, 3:57:05 AM7/9/08
to pon...@googlegroups.com


2008/7/9 Lee MaRS <lee...@gmail.com>:
看那个PPT就行了。

pongba写出来的只可能会比那个更长。

没错。

况且PPT图文并茂,我还真没见过这么优美的算法讲解。

Yufei Chen

unread,
Jul 10, 2008, 11:35:26 AM7/10/08
to pon...@googlegroups.com
leemars 是复旦的 Arch 教主吧?

2008/7/9 Lee MaRS <lee...@gmail.com>:

--
Best regards,
Chen Yufei

Lee MaRS

unread,
Jul 11, 2008, 3:36:58 AM7/11/08
to pon...@googlegroups.com
-_-bb 恩...

2008/7/10 Yufei Chen <cyfd...@gmail.com>:

hongtao wang

unread,
Jul 13, 2008, 9:22:04 AM7/13/08
to pon...@googlegroups.com
正在拜读CLRS,正看到红黑树,幸甚幸甚......

2008/7/7 pongba <pon...@gmail.com>:

就恰好看到chen yufei同学的博客上提到了。我得去看看Sedgewick老大是怎么说的。

via: http://chenyufei.name/blog/2008-07-07/left-leaning-red-black-tree/

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 的发明者之一,他能够讲清楚也就不奇怪了。除了解释清楚以外,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,被彻底雷到了,这宏用的太牛了!

Reply all
Reply to author
Forward
0 new messages