红黑树的性质

满足以下特性的二叉查找树树是红黑树

每个节点不是黑色就是红色。根节点是黑色的。每个叶节点都是黑色的。如果一个节点是红色的，它的两个子节点都是黑色的。对于每个节点，从该节点到其所有后代叶节点的简单路径包含相同数量的黑色节点。属性1和属性2无需过多解释。

在属性3中，每个叶节点(NIL)都是黑色的。这里的叶节点不是指上图中的节点1、5、8、15，而是指下图中的空值节点，颜色为黑色，是其父节点的子节点。

属性4:如果一个节点是红色的(图中用白色代替红色)，那么它的两个子节点是黑色的，比如节点2、5、8和15。但是，如果一个节点的两个子节点是黑色的，则该节点可能不是红色的，例如节点1。

属性5，对于每个节点，从该节点到其所有后代叶节点的简单路径包含相同数量的黑色节点。例如，在从节点2到其所有后代叶节点的简单路径上，黑色节点的数量是2；在从根节点11到其所有后代叶节点的简单路径上，黑色节点的数量是3。

这样的树有什么特点？

通过约束从根节点到叶节点的任何简单路径中每个节点的颜色，红黑树确保没有路径会比其他路径长两倍，因为它是近似平衡的。—— 《算法导论》

由于属性4，红黑树中的两个红色节点彼此不相邻。树中最短的可能路径是黑色节点的路径，树中最长的可能路径是红色节点和黑色节点交替的路径。结合属性5，每个路径包含相同数量的黑色节点，因此红黑树确保没有路径比其他路径长两倍。

插入红黑树

首先，在二叉查找树插入节点，并用红色标记。如果是黑色，会违反属性5，不方便调整；如果是红色，可能会违反属性2或者属性4，通过比较简单的操作就可以恢复到红黑树的属性。

在二叉查找树中插入节点后，可能会出现以下情况：

情景1

插入节点后，没有父节点，节点作为根节点插入。违反属性2，将节点调整为黑色以完成插入。

场景2

插入节点后，它的父节点是黑色的，不违反任何属性，所以插入不需要调整就完成了。例如下图中插入节点13。

情景3

插入节点后，其父节点为红色，这违反了属性4，需要进行一系列调整。例如下图中插入节点4。

那么什么是一系列的调整呢？

如果插入节点的父节点父亲是红色的，那么父节点祖父一定是黑色的，因为如果没有父节点，就是根节点，根节点是黑色的。那么节点祖父的另一个子节点可以称为节点叔，即节点父的兄弟节点。节点叔叔可能是黑色或红色。

首先从最简单的情况来分析，因为复杂的情况可以转化为简单的情况，简单的情况就是节点大叔黑的情况。

情况3.1

上图(a)中，情况如下：节点为红色，父亲为红色，祖父和叔叔为黑色，、、、和都是节点对应的子树。假设整个二叉查找树只有node和父亲不能成为正常的红黑树，因为侵犯了属性4。此时，如果将图(a)调整为图(b)，就可以恢复到正常的红黑树。整个调整过程其实分为两个步骤，旋转和变色。

什么是旋转？

上图(c)是二叉查找树的一部分，其中x和y是节点，、和是对应节点的子树。从图中可以看出， x y ，即子树中的所有节点都小于x，节点x小于子树中的所有节点。在二叉查找树中，如果节点Y的值大于节点X的值，那么节点X在节点Y的左子树中，如图(c)所示；或者节点y在节点x的右子树中，如图(d)所示。因此， x y 也可以用图(d)的结构来表示。这是旋转，不会破坏二叉查找树的属性。

具体案例1节点为红色，父亲为红色，祖父和叔叔为黑色

在图(a)中，节点是父亲的左子节点，父亲是格兰的左子节点，节点父亲是格兰叔叔。在这种情况下，grand神父可以表示为父亲是grand的左子树或者grand是父亲的右子树。所以图(a)中的旋转父和grand不会破坏二叉查找树的属性，但是旋转后会破坏红黑树的属性，所以需要调整节点的颜色。

变色

因此，图形(a)旋转后，需要将grand变为红色，将父项变为黑色，并成为图形(b)以完成插入。

具体案例二：节点红，爸爸红，爷爷和叔叔黑

节点是父亲的右子节点，父亲是grand的右子节点，如下图(e)，是具体案例1的翻转。

即grand叔父节点旋转图(e)中的父和grand，改变颜色，变成图(f)，完成插入。

具体案例三：节点红，爸爸红，爷爷和叔叔黑

节点是父亲的右子节点，父亲是格兰的左子节点，如下图(m)。

旋转图(m)中的节点和父亲后，变成图(n)，父亲被视为新节点，成为第一个具体案例。再次旋转并改变颜色后，插入完成。

具体案例四：节点红，爸爸红，爷爷和叔叔黑

节点是父亲的右子节点，父亲是grand的左子节点，如下图(I)所示，是具体案例3的翻转。

旋转图(I)中的节点和父亲后，变成图(J)，以父亲为新节点成为第二种具体情况。再次旋转并改变颜色后，插入完成。

情况3.2

节点，爸爸和叔叔是红色，爷爷是黑色。

如上图(k)所示，不是旋转，是盛大为红色，父亲和叔叔为黑色，以盛大为新节点判断情况。如果grand成为新节点Case 2，则插入完成。如果变成情况3.1，调整后插入完成；如果还是3.2的情况，继续改变grand，父，叔的颜色，上移节点节点。如果新的节点没有父节点，它将变成案例1，并且根结被点亮为黑色，则插入完成。

概括起来

节点1节点为红色，无父将重新着色节点2节点为红色，父为黑色3.1节点，父为红色，盛大，叔叔为黑色旋转一两次，而重新着色情况3.2节点，父，叔叔为红色，盛大为黑色将重新着色父，叔叔，盛大为新节点

密码

//结点函数节点(值){ this。value=值这个。color=' red '//结点的颜色默认为红色这个。parent=null this。left=空。right=null }函数RedBlackTree(){这个。root=null } RedBlackTree。原型。插入=函数（节点){ //以二叉搜索树的方式插入结点//如果根结点不存在，则结点作为根结点//如果结点的值小于节点，且结点的右子结点不存在，跳出循环//如果结点的值大于等于节点，且结点的左子结点不存在，跳出循环if(！这个。根){这个。root=node } else { let current=this。root while(当前[节点。值=当前。价值？left ' : ' right ']){ current=current[node。值=当前。价值？left ' : ' right ']}当前[节点。值=当前。价值？left ' : ' right ']=节点节点。父级=当前}//判断情形这个_fixTree(节点)返回此} RedBlackTree。原型。_ FixTree=函数（节点){ //当node.parent不存在时，即为情形1,跳出循环//当node.parent.color==='black '时，即为情形2,跳出循环while(节点。父节点。父母。颜色！=='black') { //情形3让父亲=节点. parent让grand=父亲。父母让叔叔=grand[grand.left===父亲？right' : 'left'] if(！叔叔||叔叔。color==='black') { //叶结点也是黑色的//情形3.1让directionFromFatherToNode=父。左===节点？左' : '右'让爷爷的方向=大。左===父亲？left ' : ' right ' if(directionfromtaftertonode===directionfromtafterfault){//具体情形一或二//旋转这个_旋转(父亲)//变色父亲。color=' black ' grand。color=' red ' else {//具体情形三或四//旋转这个。_旋转（节点)此。_旋转（节点)//变色节点。color=' black ' grand。color=' red ' } break//完成插入，跳出循环} else { //情形3.2 //变色grand.color='red '父亲。颜色='黑色'叔叔。color='black' //将宏伟的设为新的node node=grand } } if(！node.parent) { //如果是情形1个节点。color=' black '这个。root=node } } redblacktree。原型。_ rotate=函数(节点){//旋转结节和节点。父字母y=节点。父if(y . right===节点){ if(y . parent){ y . parent[y . parent。左===y？left ' : ' right ']=node } node。parent=y . parent if(节点。左){ node。向左。parent=y } y . right=node。左节点。left=y . parent=node } else { if(y . parent){ y . parent[y . parent。左===y？左' : '右']=节点}节点。父项=y .父项if(节点。右){ Node。没错。父节点=y } y .左侧=节点。右节点。right=y . parent=Node } } let arr=[11，2，14，1，7，15，5，8，4，16]let tree=new RedBlackTree()arr。每棵树。插入(新节点(一))调试器总结

以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，如果有疑问大家可以留言交流，谢谢大家对我们的支持。