首页 > 程序开发 > 软件开发 > C语言 >

红黑树算法的层层剖析与逐步实现

2011-04-09

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

本文主要参考:算法导论第二版
本文主要代码:参考算法导论。
本文图片来源:个人手工画成、算法导论原书。
推荐阅读: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) ,在下文会得到着重而具体的分析。

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

是的,时刻

相关文章
最新文章
热点推荐