红黑树
博客专区 > frank21 的博客 > 博客详情
红黑树
frank21 发表于10个月前
红黑树
  • 发表于 10个月前
  • 阅读 9
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 十分钟定制你的第一个小程序>>>   

了解平衡二叉树的同学才能阅读这篇文章,如果不了解,猛戳这里https://my.oschina.net/sundq/blog/801731

##定义 红黑树也是一个二叉树,还要满足如下特性:

  1. 每个节点或者是黑色,或者是红色。
  2. 根节点是黑色。
  3. 每个叶子节点(NIL)是黑色。 [注意:这里叶子节点,是指为空(NIL或NULL)的叶子节点!]
  4. 如果一个节点是红色的,则它的子节点必须是黑色的
  5. 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

##红黑树结点的增加

为了不违反特性5,每次增加的新结点都是红色的结点,但还是可能违反特性1和特性4

  • 违反特性1,直接将结点的颜色图黑即可
  • 违反特性4,就要重新涂色和调整红黑树了。

为了使红黑树重新符合特性4,大家都知道一个重要的原则就是把新加的红色结点向上移,最好到根结点,这样直接把根节点涂黑就可以,但是很多时候没有到根结点,特性4就已经符合了,下面我们看看增加一个红色结点导致红黑树违反特性4的情况,我们从最简单的红黑树开始,如下图:

输入图片说明

这两种红黑树在增加新的红色结点时,导致违反特性4的有如下四种情况(new结点为新增结点)

输入图片说明

一般对于违反特性4的处理方法是给结点重新着色,下面分析下如何着色,以及给哪些结点着色

  • 新增结点是红色,如果不是根结点,它的颜色是不能重新着色的,因为如果变颜色,会违反特性5
  • 新增结点的兄弟结点也不能重新着色,如果他的颜色有变化,无论从黑变红,还是从红变黑,都会违反特性5
  • 目前看来只能对父结点和祖父结点着色了。

###a1情况

所以可以重新着色的就是new的父结点和祖父结点了,但是由于特性4的存在,导致在重新着色时,需考虑兄弟结点的颜色。我们再给父结点b着色时,必须考虑b的兄弟结点的颜色,以决定是否重新给兄弟结点着色,由于我们分析的是最简单的红黑树,所以b的兄弟结点为NULL,但是红黑 把NULL结点成为叶子结点(实际上这个结点不存在),所以也可以认为b的兄弟结点为黑色结点,为了保持特性5,我们可以同时分别将b涂黑,a涂红,这样可以保证a的左子树满足特性5,但是a的右子树就不满足了,因为a到右子树的叶子结点少了一个黑色结点,为了让a的有子树也可以分享b的黑色,可以将a结点右旋转,这样b到了子树的根节点,左右都满足特性5了, 下面变化图。

输入图片说明

###a2情况

这种情况其实和a1情况类型,知道平衡二叉树的同学都知道,只是把b结点左旋转一下就成了a1的情况,b1和b2其实是a1和a2问题的镜像,照猫画虎就可以解决了。

###兄弟结点为红色

上面我们讨论了没有兄弟结点或者兄弟结点为黑色的情况,现在分析下兄弟结点为红色的请情况,如下图:

输入图片说明

很明显,b肯定是要着为黑色的,根据特性4, d也要着为黑色的,然后把a作为红色的,那么左右子树到叶子结点的黑色结点数量并没有变化,不会违反特性5,此时,把a结点当做新增的结点,做以上几种情况的分析,指导根结点。

###伪代码

	while (p(cur_node) && color(p(cur_node)) == RED) //结点的增加没有破坏红黑树
	{
		if (p(p(cur_node)) == NULL) //父结点为根结点,直接将父结点涂黑即可
		{
			break;
		}

		if (p(cur_node) == left(p(p(cur_node)))) //a图
		{
			uncle_node = right(p(p(cur_node))); 
			if (uncle_node != NULL && color(uncle_node) == RED) //兄弟结点为红色的情况
			{
				color(p(cur_node)) = BLACK;
				color(uncle_node) = BLACK;	
				color(p(p(cur_node))) = RED; 
				cur_node = p(p(cur_node));
			}
			else
			{
				if (cur_node == right(p(cur_node))) //a2图
				{
					cur_node = p(cur_node);
					binary_tree_left_rotate(btree, cur_node);
				}
				else //a1图
				{
					color(p(cur_node)) = BLACK;
					color(p(p(cur_node))) = RED;
					binary_tree_right_rotate(btree, p(p(cur_node)));
				}
			}
		}
		else //b图
		{
			uncle_node = left(p(p(cur_node))); 
			if (uncle_node != NULL && color(uncle_node) == RED) //兄弟结点为红色
			{
				color(p(cur_node)) = BLACK; 
				color(uncle_node) = BLACK; 	
				color(p(p(cur_node))) = RED;
				cur_node = p(p(cur_node));
			}
			else
			{
				if (cur_node == left(p(cur_node))) //b2图
				{
					cur_node = p(cur_node);
					binary_tree_right_rotate(btree, cur_node);
				}
				else //b1图
				{
					color(p(cur_node)) = BLACK;
					color(p(p(cur_node))) = RED;
					binary_tree_left_rotate(btree, p(p(cur_node)));
				}
			}
		}
	}
	btree->root->color = BLACK; //涂黑根结点,根结点颜色的变化永远不会破坏红黑树,同样的道理,任意一结点的颜色变化都不会破坏以这个结点为根结点的子树的红黑树的特性

##红黑树结点的删除

红黑树删除一个结点首先按照二叉树删除结点的方法,删除一个结点。二叉树删除一个结点,一般是删除这个结点的后继结点。后继结点是要么沿着左孩子结点一直找他的右孩子结点,直到有孩子为空;或者沿着右孩子结点一直找左孩子结点,直到左孩子为空,代码大概是这个样子:

if (node->rchild != NULL) //沿着右孩子找
{
	successor_node = node->rchild;
	while (successor_node->lchild != NULL)
	{
		successor_node = successor_node->lchild;
	}
}
else if (node->lchild != NULL) //沿着左孩子找
{
	successor_node = node->lchild;
	while (successor_node->rchild != NULL)
	{
		successor_node = successor_node->rchild;
	}
}
else//叶子结点,直接删除即可
{
	successor_node = node;
}

可以看到,后继结点也就是删除的结点最多有一个孩子结点,设u为删除结点,v为u孩子结点,分情况讨论:

  1. u为红色:因为删除的是红色结点,没有破坏红黑树的任何特性,所以不做任何额外处理

  2. u为黑色

    • v为红色:直接将v的颜色涂黑即可,这样就可以再次符合特性5
    • v为黑色: 可以这样考虑,u的删除导致违反特性5,设v的父结点为p(v), v是左孩子,那么p(v)这个子树左边少了一个黑色结点,解决办法就是怎样让左右两边的黑色结点相同,而且数量不能有变化,简单的办法就是把右边的黑色结点移到p(v)的位置,这样两边的黑色结点一致,而且数量没有变化。

    a. v的兄弟结点为红色,我们看下面的图: 输入图片说明

a1图是删除结点之前的图,a2是删除b结点的之后的图(null为红黑树的叶子结点),由于a的左子树少一个黑色结点,为了找回这个少了的黑色结点,考虑让a左旋转,然后把c涂黑,如a3, 这样左子树就多一个黑色结点,但是由于旋转原因,a的有孩子继承了c的黑色结点,导致左子树多了两个黑色结点,简单的办法就是直接将d涂红,如a4。这样又重新满足红黑树的特性了。

b. v的兄弟结点为黑色,如下图:

输入图片说明

如果v结点是有孩子,也可以做同样的分析。

共有 人打赏支持
粉丝 10
博文 15
码字总数 15213
×
frank21
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: