文档章节

红黑树

frank21
 frank21
发布于 2016/12/12 22:27
字数 1898
阅读 13
收藏 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结点是有孩子,也可以做同样的分析。

© 著作权归作者所有

共有 人打赏支持
frank21
粉丝 11
博文 15
码字总数 15213
作品 0
浦东
高级程序员

暂无相关文章

BS与CS的联系与区别【简】

C/S是Client/Server的缩写。服务器通常采用高性能的PC、工作站或小型机,并采用大型数据库系统,如Oracle、Sybase、InFORMix或 SQL Server。客户端需要安装专用的客户端软件。 B/S是Brower/...

anlve ⋅ 33分钟前 ⋅ 0

发生了什么?Linus 又发怒了?

在一个 Linux 内核 4.18-rc1 的 Pull Request 中,开发者 Andy Shevchenko 表示其在对设备属性框架进行更新时,移除了 union 别名,这引发了 Linus 的暴怒。 这一次 Linus Torvalds 发怒的原...

问题终结者 ⋅ 52分钟前 ⋅ 0

在树莓派上搭建一个maven仓库

在树莓派上搭建一个maven仓库 20180618 lambo init 项目说明 家里有台树莓派性能太慢。想搭建一个maven私服, 使用nexus或者 jfrog-artifactory 运行的够呛。怎么办呢,手写一个吧.所在这个...

林小宝 ⋅ 今天 ⋅ 0

Spring发展历程总结

转自与 https://www.cnblogs.com/RunForLove/p/4641672.html 目前很多公司的架构,从Struts2迁移到了SpringMVC。你有想过为什么不使用Servlet+JSP来构建Java web项目,而是采用SpringMVC呢?...

onedotdot ⋅ 今天 ⋅ 0

Python模块/包/库安装(6种方法)

Python模块/包/库安装(6种方法) 冰颖机器人 2016-11-29 21:33:26 一、方法1: 单文件模块 直接把文件拷贝到 $python_dir/Lib 二、方法2: 多文件模块,带setup.py 下载模块包(压缩文件zip...

cswangyx ⋅ 今天 ⋅ 0

零基础学习大数据人工智能,学习路线篇!系统规划大数据之路?

大数据处理技术怎么学习呢?首先我们要学习Python语言和Linux操作系统,这两个是学习大数据的基础,学习的顺序不分前后。 Python:Python 的排名从去年开始就借助人工智能持续上升,现在它已经...

董黎明 ⋅ 今天 ⋅ 0

openJdk和sun jdk的区别

使用过LINUX的人都应该知道,在大多数LINUX发行版本里,内置或者通过软件源安装JDK的话,都是安装的OpenJDK, 那么到底什么是OpenJDK,它与SUN JDK有什么关系和区别呢? 历史上的原因是,Ope...

jason_kiss ⋅ 今天 ⋅ 0

梳理

Redux 是 JavaScript 状态容器,提供可预测化的状态管理。 它是JS的状态容器,是一种解决问题的方式,所以即可以用于 react 也可以用于 vue。 需要理解其思想及实现方式。 应用中所有的 stat...

分秒 ⋅ 今天 ⋅ 0

Java 后台判断是否为ajax请求

/** * 是否是Ajax请求 * @param request * @return */public static boolean isAjax(ServletRequest request){return "XMLHttpRequest".equalsIgnoreCase(((HttpServletReques......

JavaSon712 ⋅ 今天 ⋅ 0

Redis 单线程 为何却需要事务处理并发问题

Redis是单线程处理,也就是命令会顺序执行。那么为什么会存在并发问题呢? 个人理解是,虽然redis是单线程,但是可以同时有多个客户端访问,每个客户端会有 一个线程。客户端访问之间存在竞争...

码代码的小司机 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部