【数据结构】红黑树入门知识

前端之家收集整理的这篇文章主要介绍了【数据结构】红黑树入门知识前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

今天呆在宿舍看了一天的红黑树,算是基本了解了一点关于红黑树的基础知识,写这篇博客意在整理今天所学的内容,先把红黑树的基础知识贴上来。结合之前写过的关于二叉排序树的基础,尝试整理的资料如下:

红黑树是一种二叉排序树,先来回忆一下二叉排序树的基本性质:

若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树
红黑树是每个节点都带有颜色属性的二叉查找树,颜色或红色或黑色。在二叉查找树强制一般要求以外,对于任何有效的红黑树我们增加了如下的额外要求:
性质1. 节点是红色或黑色。
性质2. 根节点是黑色。
性质3 每个叶节点(NIL节点,空节点)是黑色的。
性质4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。 因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例 ,这个在高度上的理论上限允许 红黑树在最坏情况下都是高效的 ,而不同于普通的二叉查找树。
性质4导致了路径不能有两个毗连的红色节点。所以最短的可能路径都是黑色节点。 最长的可能路径有交替的红色和黑色节点。 因为根据性质5所有最长的路径都有相同数目的黑色节点,这就表明了没有路径能多于任何其他路径的两倍长。
下图,就是一个红黑树的例子:
容易看到红黑树的叶子节点都带了1-2个NIL结点,这些结点其实就是实际上的NULL结点,但是我们为了编程需要,增加NIL结点,并对它进行了染(黑)色。
下面再来回顾一下关于二叉排序树的旋转知识:
图片转自http://blog.csdn.net/v_JULY_v/article/details/6109153

如上图所示,左旋右旋我找来找去就这张图最容易理解,但是我们再结合伪代码来看一下具体实现。
LEFT-ROTATE(T,x)
y = x.right
x.right = y.left  //把y的左结点接到x的右结点上
if y.left != T.nil    
	then y.left.p = x //如果y的左结点非空,即不是NIL结点,则把该结点的父指针接到x上
y.p = x.p             //把x的父指针赋给y
if x.p == T.nil			
	then T.root = y		//如果刚刚好X是根节点,则把y结点赋给该树的root值(根节点标记)
else if x == x.p.left 
	then x.p.left = y
else 
	x.parent.right = y //将y接到对应的x的父指针上
y.left = x		//接上x结点             
x.p = y			//把x结点的父指针接到y上

明明用vc编出来是很规则的程序,码上来就变成了这样。
明天在贴红黑树的旋转以及着色的伪代码跟分析,费了我一天的时间去了解,不过总算搞了七七八八。欢迎指正。

本文关键字:二叉树 红黑树 二叉树旋转

本文原创:Cout_Sev
转载注明出处 红黑树入门知识
谢谢!


原文链接:https://www.f2er.com/datastructure/383051.html

猜你在找的数据结构相关文章