频道栏目
首页 > 程序开发 > 软件开发 > C语言 > 正文
红黑树算法的层层剖析与逐步实现
2011-04-09 18:18:12           
收藏   我要投稿

本文主要参考:算法导论第二版
本文主要代码:参考算法导论。
本文图片来源:个人手工画成、算法导论原书。
推荐阅读:Leo J. Guibas 和 Robert Sedgewick 于1978年写的关于红黑树的一篇论文。

引言: 

昨天下午画红黑树画了好几个钟头,总共10页纸。
特此,再深入剖析红黑树的算法实现,教你如何彻底实现红黑树算法。

经过我上一篇博文,“教你透彻了解红黑树”后,相信大家对红黑树已经有了一定的了解。
个人觉得,这个红黑树,还是比较容易懂的。
不论是插入、还是删除,不论是左旋还是右旋,最终的目的只有一个:
即保持红黑树的5个性质,不得违背。

再次,重述下红黑树的五个性质:
一般的,红黑树,满足一下性质,即只有满足一下性质的树,我们才称之为红黑树:
1)每个结点要么是红的,要么是黑的。
2)根结点是黑的。
3)每个叶结点,即空结点(NIL)是黑的。
4)如果一个结点是红的,那么它的俩个儿子都是黑的。
5)对每个结点,从该结点到其子孙结点的所有路径上包含相同数目的黑结点。


抓住了红黑树的那5个性质,事情就好办多了。
如,
1.红黑红黑,要么是红,要么是黑;
2.根结点是黑;
3.每个叶结点是黑;
4.一个红结点,它的俩个儿子必然都是黑的;
5.每一条路径上,黑结点的数目等同。
   五条性质,合起来,来句顺口溜就是:(1)红黑 (2)黑 (3)黑 (4&5)红->黑 黑。

 

本文所有的文字,都是参照我昨下午画的十张纸(即我拍的照片)与算法导论来写的。

希望,你依照此文一点一点的往下看,看懂此文后,你对红黑树的算法了解程度,一定大增不少。

 

ok,现在咱们来具体深入剖析红黑树的算法,并教你逐步实现此算法。

此教程分为10个部分,每一个部分作为一个小节。且各小节与我给的十张照片一一对应。

 

一、左旋与右旋

     先明确一点:为什么要左旋?

因为红黑树插入或删除结点后,树的结构发生了变化,从而可能会破坏红黑树的性质。

为了维持插入、或删除结点后的树,仍然是一颗红黑树,所以有必要对树的结构做部分调整,从而恢复红黑树的原本性质。

而为了恢复红黑性质而作的动作包括:

结点颜色的改变(重新着色),和结点的调整。

这部分结点调整工作,改变指针结构,即是通过左旋或右旋而达到目的。

从而使插入、或删除结点的树重新成为一颗新的红黑树。

 

ok,请看下图:

\

如上图所示,‘找茬’

如果你看懂了上述俩幅图有什么区别时,你就知道什么是“左旋”,“右旋”。

 

在此,着重分析左旋算法:

左旋,如图所示(左->右),以x->y之间的链为“支轴”进行,

使y成为该新子树的根,x成为y的左孩子,而y的左孩子则成为x的右孩子。

算法很简单,还有注意一点,各个结点从左往右,不论是左旋前还是左旋后,结点大小都是从小到大。

 

左旋代码实现,分三步(注意我给的注释):

The pseudocode for LEFT-ROTATE assumes that right[x] ≠ nil[T] and that the roots parent is nil[T].

LEFT-ROTATE(T, x)
 1  y ← right[x]            ▹ Set y.
 2  right[x] ← left[y]                   //开始变化,y的左孩子成为x的右孩子

 3  if left[y]  !=nil[T]

 4  then p[left[y]] <- x                

 5  p[y] <- p[x]                       //y成为x的父母
 6  if p[x] = nil[T]

 7     then root[T] <- y

 8     else if x = left[p[x]]
 9             then left[p[x]] ← y
10             else right[p[x]] ← y
11  left[y] ← x             //x成为y的左孩子(一月三日修正)

12  p[x] ← y
//注,此段左旋代码,原书第一版英文版与第二版中文版,有所出入。

//个人觉得,第二版更精准。所以,此段代码以第二版中文版为准。

 

左旋、右旋都是对称的,且都是在O(1)时间内完成。因为旋转时只有指针被改变,而结点中的所有域都保持不变。

最后,贴出昨下午关于此右旋算法所画的图:

左旋(第2张图):

\

//此图有点bug。第4行的注释移到第11行。如上述代码所示。(一月三日修正)

 

二、左旋的一个实例

不做过多介绍,看下副图,一目了然。

LEFT-ROTATE(T, x)的操作过程(第3张图):

\ 

--------------------- 

提醒,看下文之前,请首先务必明确,区别以下俩种操作:

1.红黑树插入、删除结点的操作

         //如插入中,红黑树插入结点操作:RB-INSERT(T, z)。

2.红黑树已经插入、删除结点之后,

为了保持红黑树原有的红黑性质而做的恢复与保持红黑性质的操作。

        //如插入中,为了恢复和保持原有红黑性质,所做的工作:RB-INSERT-FIXUP(T, z)。

ok,请继续。

 

三、红黑树的插入算法实现

RB-INSERT(T, z)   //注意我给的注释...
 1  y ← nil[T]                 // y 始终指向 x 的父结点。
 2  x ← root[T]              // x 指向当前树的根结点,
 3  while x ≠ nil[T]
 4      do y ← x
 5         if key[z] < key[x]           //向左,向右..
 6            then x ← left[x]
 7            else x ← right[x]         // 为了找到合适的插入点,x 探路跟踪路径,直到x成为NIL 为止。
 8  p[z] ← y         // y置为 插入结点z 的父结点。
 9  if y = nil[T]
10     then root[T] ← z
11     else if key[z] < key[y]
12             then left[y] ← z
13             else right[y] ← z     //此 8-13行,置z 相关的指针。
14  left[z] ← nil[T]
15  right[z] ← nil[T]            //设为空,
16  color[z] ← RED             //将新插入的结点z作为红色
17  RB-INSERT-FIXUP(T, z)   //因为将z着为红色,可能会违反某一红黑性质,

                                            //所以需要调用RB-INSERT-FIXUP(T, z)来保持红黑性质。

17 行的RB-INSERT-FIXUP(T, z) ,在下文会得到着重而具体的分析。

还记得,我开头说的那句话么,

是的,时刻

点击复制链接 与好友分享!回本站首页
相关TAG标签 算法
上一篇:红黑树的介绍和实现(二)
下一篇:红黑树c源码实现与剖析
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站