前面介绍了二叉搜索树,其支持的搜索、插入和删除等操作,时间复杂度均为O(h),h是树高。但是二叉搜索树对书的“平衡”没有要求,当其退化到近似链表结构后,树的高度比较高时,这些操作可能并不比在链表上快。
红黑树(Red-Black Tree)是平衡搜索树中的一种,可以保证在最坏情况下基本动态集合操作的时间复杂度为O(lgn),n为节点个数。
以下介绍红黑树的C语言代码实现,代码链接。
1 红黑树的性质
红黑树是一棵二叉搜索树,它的每个节点上增加了一个存储位来表示节点的颜色,可以是红或者黑。通过对一条从根到叶子的简单路径上各个节点的颜色进行约束,红黑树确保没有一条路径会比其它路径长出2倍,因而是近似于平衡的。
红黑树需要满足以下的红黑性质:
- 每个节点或是红色的、或是黑色的;
- 根节点是黑色的;
- 每个叶子节点挂的两个空子节点是黑色的;
- 如果一个节点是红色的,则它的两个子节点都是黑色的;
- 对每个节点,从该节点到其所有的后代叶节点的简单路径上,均包含有相同数目的黑色节点。
- 注:有些教材将叶子节点挂的两个空子节点NIL视为叶节点,这里我们为了和之前的二叉搜索树保持一致,不采用此种描述。
黑高:从某个节点出发(不含该节点),到达任意一个叶节点的空子节点的简单路径上的黑色节点个数称为该节点的黑高。
引理: 一棵有n个节点的红黑树的高度至多为2lg(n+1)
证明:
首先证明x为根的子树至少包含2bh(x)-1个内部节点。归纳法:
- 1.高度为0的节点x,其至少有0个内部节点;
- 2.对于具有两个子节点的x,其子节点都有黑高bh(x)或bh(x)-1,分别取决于其自身是红色还是黑色;
- 3.假设每个子节点有2bh(x)-1-1个内部节点;
- 4.那么可以归纳出以x为根的子树至少包含(2bh(x)-1-1)+(2bh(x)-1-1)+1=2bh(x)-1个节点。
假设h为树的高度,根据性质4,从根节点到叶节点(不包含根节点)的任何一条简单路径上都至少包含有一般的节点为黑色;于是有n≥2h/2-1,从而得到h≤2lg(n+1)
根据引理,可知在红黑树上进行查找会在O(lgn)时间内执行。
2 插入
2.1 前期分析
对于红黑树的插入,其操作可以在O(logn)时间内完成。由于红黑树的插入和删除操作都比较复杂,需要用到旋转等操作保证红黑性质,所以我们相比于搜索二叉树新增了parent
指针(当然没有这个指针也是可以实现的),当然,还有红黑树的节点着色,如下:
1 | typedef enum ColorType {RED, BLACK} ColorType; |
针对树的NIL节点,我们新建一个NilNode
节点,用作哨兵,我们将叶节点的左右子节点指向NilNode
,也将根节点的父节点指向NilNode
,当然,为了方便计,我们将NilNode
的父节点和左右子节点都指向自身,其颜色被涂成黑色。如下:
1 | typedef struct rbTree { |
首先需要考虑的是,插入节点的颜色,如果插入的是黑色,那势必会破坏红黑性质5(除非是root节点),其它每一条线路上黑色节点个数都将小于插入的这一条,所以我们将插入节点着色为红色。
然后我们将插入节点插入到树T内,就好像T是一棵普通的二叉树那样,如下(请暂时忽略最后一行):
1 | void rbtree_insert(rbTree_t *T, myElement x) |
以上操作可以保证:
- 性质1:插入的节点是红色的;
- 性质3:Nil节点是黑色的;
- 性质5:对每个节点,从该节点到其所有的后代叶节点的简单路径上,均包含有相同数目的黑色节点。
所以分析有以下情形:
- 如果插入的是根节点,那么破坏的是性质2,此时只需要将插入节点涂成黑色即可;
- 如果插入的不是根节点,那么性质2不可能被破坏,那么可能被破坏的只有性质4;
- 如果插入节点的父节点是黑色的,那么性质4也不会被破坏,即插入后的红黑树依然满足红黑性质;
- 如果插入节点的父节点是红色的,那么性质4即被破坏,那我们需要通过一系列的操作来使得插入后的红黑树依然满足红黑性质。
2.2 插入原则
所以我们总结插入的原则如下:
- 按照搜索树的特征插入;
- 插入时:插入节点涂成红色,进行以下判断:
- 如果插入的是根节点,将颜色改成黑色;
- 插入节点的父节点是黑色的,则插入完成;
- 插入的节点的父节点是红色的,则需要修复,且继续向上调整,继续做判断,直到为根或满足条件;
- 如果根修改之后为红色,则修改为黑色。
2.3 修复方法
针对以上分析需要修复的情况:插入节点的父节点是红色的,则其祖父节点一定是黑色的,否则插入前这棵树就不是一棵红黑树了。
定义父节点的兄弟节点为叔节点。
注:以下分析用到了以下两篇博客的图片:
红黑树的插入操作过程详细图解
红黑树(二)之 C语言的实现
2.3.1 情况1:叔节点为红色
此时将插入节点的父节点和叔节点都涂成黑色,将其祖父节点涂成红色,并以其祖父节点为刚插入节点在此进行以上的判断。
此修复对于祖父节点以上的子节点而言,虽然新增了父节点和叔节点两个黑色节点,但是也删除了祖父节点这个黑色节点,所以在满足其性质4的情况下,其性质5并没有改变,如果接下来满足:1.祖父节点的父节点是黑色节点;2.祖父节点是根节点(将其涂黑)两条性质后,循环判断即可结束。如果祖父节点的父节点依然是红色节点,那么则继续以祖父节点为插入节点继续判断,可能出现的哈市情况1,当然也有可能是以下情况。
2.3.2 情况2:叔节点为黑色,且插入节点和其父节点都是各自父节点的同侧
都为左儿子
此时将其父节点涂成黑色,将其祖父节点涂成红色并右旋。此操作得到的树一定满足性质4,也一定满足红黑树。
如果开始时其祖父节点是根节点,那么旋转后其父节点是根节点,且为黑色,则循环结束;如果开始是其祖父节点不是根节点,那么其祖父一定是黑色节点,旋转后,对于拥有这个子树的其曾祖父树而言,其没有改变任何一个枝干的黑色节点数,且其儿子节点的颜色没有改变,也不存在修改了性质4的点,同时因为其父节点涂黑,祖父节点涂红的操作,保证了祖父节点树的性质4,所以这棵数也是红黑树。
都为右儿子
这种情况是上一种情况的镜像,只需要将其祖父节点进行左旋就好了。
2.3.3 情况3:叔节点为黑色,且插入节点和其父节点都是各自父节点的异侧
插入节点为右儿子,父节点为左儿子
将其父节点左旋后以其父节点为插入节点继续判断。很明显可以看出,以其父节点左旋以后,父节点变为子节点,子节点变为父节点,情况变成了情况2中都为左儿子的情形。
插入节点为左儿子,父节点为右儿子
上一种情况的镜像情况,不详细展开了。
2.4 旋转
2.4.1 左旋
以上用到了旋转,左旋操作如下所示:
代码实现如下:
1 | void rbtree_left_rotate(rbTree_t *T, rbTreeNode_t *x) |
2.4.2 右旋
右旋操作如下所示:
代码实现如下:
1 | void rbtree_right_rotate(rbTree_t *T, rbTreeNode_t *y) |
2.5 插入再平衡的代码实现
以上分析的代码实现如下,对于以上三种情况,首先是根据父节点是祖父节点的左儿子还是右儿子进行分类,下面基本是上面的镜像情况。
1 | void rbtree_insert_fixup(rbTree_t *T, rbTreeNode_t *node) |
插入的分析基本如上,根据《数据结构与算法分析-C语言描述》的红黑树的例子,一次插入10,85,15,70,20,60,30,50,65,80,90,40,5,55
的红黑树如下所示(红色节点用双圆圈表示)。
而以上实现代码打印的红黑树如下,和图片是一致的。
1 | 30[B] |
2.6 分析
由于一棵有n个节点的红黑树高度为O(lgn),因此常规插入的时间是O(lgn),而rbtree_insert_fixup中,仅当情况1发生时,插入节点沿着树上升两层,while循环才会继续,直至出现情况2、3或者父节点为黑,所以其总次数也是O(lgn);只要出现情况2,那么这一步必然是最后一步;只要出现情况3,那么必然一次处理就能到情况2,所以该程序所作的旋转最多是2次。
通过以上分析,红黑树的插入最坏情况为O(lgn)。
3 查询操作
红黑树是一种搜索二叉树,所以其查询和二叉树没有什么本质区别,所以接下来就只给出代码。
3.1 查找特定值的节点
1 | rbTreePos_t *rbtree_search1(rbTreeNode_t *node, myElement x) |
3.2 查找最大值
1 | rbTreePos_t *rbtree_max1(rbTreeNode_t *node) |
3.3 查找最小值
1 | rbTreePos_t *rbtree_min1(rbTreeNode_t *node) |
4 删除
红黑树的删除分为两部分,一是查找到删除节点并删除,二是删除之后的自平衡。
4.1 删除节点
和搜索二叉树的删除一样,红黑树的删除操作如下所示,基本就是:
- 当该节点没有儿子,即为树叶时,直接删除该节点即可;
- 当该节点只有一个儿子时,直接用该孩子节点替换该节点即可;
- 当该节点有两个儿子时,用其右子树最小节点数据代替该节点数据,并删除那个最小节点。而右子树的最小节点不可能有左儿子,所以删除右子树只会出现以上1、2两种情况。
但是有一点区别就是,需要记住真正被删除节点的颜色,并记住顶替被删除节点的节点,这是因为后续进行再平衡时需要,基本代码如下(暂时忽略current和rbtree_delete_fixup等):
1 | void rbtree_transplant(rbTree_t *T, rbTreeNode_t *u, rbTreeNode_t *v) |
4.2 再平衡
分析有:
- 若真实删除的节点(若删除节点有两个子节点,删除的是其后继节点,或者也可以说是替换节点)是红色节点,那么红黑树的任何一条性质没有改变,无需做任何修改。
- 若真实删除的节点是黑色节点,则至少破坏了性质5,因此需要进行修复。
所以我们的修复方案是记住真实被删除节点的颜色(使用tmp的颜色)和代替其位置的节点(current),然后依此进行判断。这个时候将节点current(也就是图中的current,图片借鉴红黑树原理 新增,删除,打印)看成是双重颜色:双黑色(origin和被删除的节点都是黑色),红黑色(current是红色的,但是被删除节点是黑色的)。需要修正的情况有以下4种case。以下情况都是代替节点是其父节点左儿子的情况,若是右儿子,则情况是镜像的。循环条件就是代替节点current不是根节点且其颜色是黑色的,如果是红色或者根节点,直接涂黑就好了。循环操作的目标是将额外的黑色性质上移,循环开始的节点首先就是current,其后处理可能会变。
4.2.1 case1
这时候左子树中黑色节点减少一个,说明是无法满足性质5的,所以我们做出如下变化,此时并没有更改current的内存位置,不过其兄弟节点必然变成黑色,也就变成了case2/3/4中的一个。但是此时左右子树的黑高并没有改变,所以还是需要进行变换。
4.2.2 case2
case2的时候,当x的兄弟节点是黑色的,并且兄弟节点的左右子节点都是黑色的,那么将兄弟节点置为红色节点,并将循环节点置为其父节点。当其父节点是红色时,循环结束,最后将其父节点涂黑即可。若其父节点依然是黑色的,那么继续操作即可。
4.2.3 case3
case3时,处理如下,能将case3直接转换为case4。
4.2.4 case4
case4时,通过对某些颜色的修改,并对循环操作节点的父节点做依次左旋,可以去掉循环节点的额外黑色,此时红黑树重新满足红黑性质,无需再变化。为了推出循环,将循环指针指向根节点。
4.3 分析
不进行再平衡时,红黑树的删除操作时间是O(lgn)。再平衡中,情况1、3、4在各执行常数次数的颜色改变和至多三次旋转后便终止,情况2的循环是唯一可能重复执行的,每次指针都沿着树上升,至多O(lgn)次,且无任何旋转。所以整个删除操作的总时间为O(lgn)。
4.4 代码实现
1 | void rbtree_delete_fixup(rbTree_t *T, rbTreeNode_t *node) |
5 小结
红黑树的代码实现到此结束,具体写起来还是很有趣的,也麻烦大家指出有什么谬误。
其实红黑树的本质是利用红黑性质保证其相对的平衡性,其中性质1-3都是定义性的性质,而性质4、5保证了红黑树没有一条路径会比其它路径长出两倍,也就保证了红黑树的相对平衡性,从而避免了搜索二叉树的退化问题。
另外红黑树的插入、删除再平衡时间都能保持在O(lgn),且插入的翻转次数不超过2、删除的翻转次数不超过3,和严格的平衡二叉树AVL树相比,红黑树任何不平衡都会在三次旋转之内解决,而AVL是严格平衡树,因此在增加或者删除节点的时候,根据不同情况,旋转的次数比红黑树要多。所以红黑树的插入效率更高!!!