精华内容
下载资源
问答
  • 算法导论---红黑树删除详解

    千次阅读 2013-01-26 23:27:01
    红黑树删除算法详解 删除算法相较于插入要稍微复杂些。 删除操作,首先与二叉树删除一致,找到删除的节点,若是只有左节点或者只有右节点或者没有左右子树,那么删除的节点就是原来的节点,只要将删除节点的父节点...

    红黑树删除算法详解

    删除算法相较于插入要稍微复杂些。

    删除操作,首先与二叉树删除一致,找到删除的节点,若是只有左节点或者只有右节点或者没有左右子树,那么删除的节点就是原来的节点,只要将删除节点的父节点指针指向子节点。

    2)若是同时有左右子树,利用查找后继,就是找到右子树中最小的元素,然后将找到节点与这个节点的值进行交换,那么删除的就是这个后继节点,这个后继节点是基于中序遍历找出来的。

    3)我们找到可以交换的节点,现在只要删除这个节点就好了,现在要判断这个新的删除节点的颜色。(1)如果这个节点是红的,那么很好,经过它的节点黑色并没有改变,红黑树的几个性质也没有受到变化。(2)、找到待删除节点的孩子节点x,很肯定的是待删除节点只有一个子树。也就是说这个x是确定的,那么现在又要分情况来讲。

    4)如果待删除节点是黑色的,x是红色的,很好,只要将x的颜色属性置为黑色就好。现在通过x节点的子树上黑色节点又增加了,回到原来的数目。现在还有一种很糟糕的情况是待删除与x节点的颜色属性都是黑色。问题出现了。通过前面的删除操作,通过x节点路径的黑色节点数目减少一个,现在就要对这棵树进行重新的构造。(记住,这个x节点可能下面还有子树)。现在我们针对这种情况分为4种情形来讨论(总的是根据兄弟节点的颜色)

    template<class KEY,class VAL>
    bool RB_Tree<KEY,VAL>::Delete(KEY key,VAL val)
    {
    	RB_Node<KEY,VAL> *deleteNode=nullNode;//要删除的节点
    	RB_Node<KEY,VAL>*delNodeChild=nullNode;//要删除节点的孩子节点
    	RB_Node<KEY,VAL> *index=root;//index为找到的节点
    	while(index!=nullNode)
    	{
    		if(*val<*(index->val))
    		{
    			index=index->leftNode;
    		}
    		else if (*val>*(index->val))
    		{
    			index=index->rightNode;
    		}
    		else
    		{
    			break;
    		}
    	}
    	if (index->leftNode==nullNode||index->rightNode==nullNode)//分两种情况,一种是只有左子树或者只有右子树
    	{
    		deleteNode=index;
    	}
    	else
    	{
    		deleteNode=successor(index);//若同时有左右子树,找到后继
    
    //见前面的文章,查找后继节点
         	}
    	if(deleteNode->leftNode!=nullNode)
    	{
    		delNodeChild=deleteNode->leftNode;
    	}
    	else
    	{
    		delNodeChild=deleteNode->rightNode;//获知孩子为左子树还是右子树
    	}
    	delNodeChild->parentNode=deleteNode->parentNode;//将父节点孩子指针指向这个节点的孩子节点
    	if (delNodeChild->parentNode==nullNode)
    	{
    		root=delNodeChild;
    	}
    	else
    	{
    		if (deleteNode==deleteNode->parentNode->leftNode)//获取当前节点为父节点的哪个节点
    		{
    			deleteNode->parentNode->leftNode=delNodeChild;
    		}
    		else
    		{
    			deleteNode->parentNode->rightNode=delNodeChild;
    		}
    	}
    	if (deleteNode!=index)
    	{
    		index->key=deleteNode->key;//交换值
    	}
    	if (deleteNode->color==BLACK)//若删除的节点为黑色
    	{
    		DeleteFixup(delNodeChild);//进行树的重新构造
    	}
    }
    
    template<class KEY,class VAL>
    bool RB_Tree<KEY,VAL>::DeleteFixup(RB_Node<KEY,VAL>* delNode)
    {
    	RB_Node<KEY,VAL>*w;
    	while(delNode!=root&&delNode->color==BLACK)
    	{
    		if (delNode==delNode->parentNode->leftNode)//当前节点为父节点的左子树
    		{
    			/*1、若兄弟节点为红色。将兄弟节点颜色置为黑色,
    				x节点的父节点置为红色,然后将父节点进行左旋。
    				此时所做的操作并没有改变什么。通过每个节点的黑色数目依旧没有改变,
    				我们只是为了进入下面的3种情况。开始的时候我在想为什么不采用与情形2一样的操作,
    				将兄弟节点也置为红色,那么此时每课树的黑色节点数目都减少一个,然后继续回溯。
    				但是这个时候我们发现,这样的操作,会使得通过x的黑色节点数目也减少1个,很傻逼的行为*/
    			w=delNode->parentNode->rightNode;
    			if (w->color==RED)//1.兄弟节点为红色
    			{
    				delNode->parentNode->color==RED;//将父节点置为红色
    				w->color==BLACK;//兄弟节点为黑色
    				RotateLeft(delNode->parentNode);
    				w=delNode->parentNode->rightNode;//旋转
    			}
    			else if (w->color==BLACK)
    			{
    				if(w->leftNode->color==BLACK&&w->rightNode->color==BLACK)//2.兄弟节点极其孩子节点均为黑色
    				{
    					/*2、若兄弟节点为黑色。将兄弟节点颜色置为红色,
    						那么此时通过每个叶子节点的黑色数目是一致的,
    						不过未通过x父节点的叶子节点数目反而会比通过的多一个。
    						于是我们回溯,继续构造。记住,这个时候如果是从1过来的,
    						也就是说父节点是红色的,此时只要将父节点的颜色置为黑色就ok啦。*/
    					w->color==RED;
    					delNode=delNode->parentNode;
    				}
    
    				if (w->color==BLACK&&w->leftNode->color==RED)//3.兄弟节点为黑色,w的左子树为红色
    				{
    					/*3、若兄弟节点为黑色,且其左子树的颜色为红色,
    						将这个左子树颜色置为黑色,w的颜色置为红色,
    						进行右旋。为什么这么做呢,只是为了进入4的情况。*/
    					w->color==RED;
    					w->leftNode->color=BLACK;
    					RotateRight(w);
    					w=delNode->parentNode->rightNode;
    				}
    				if(w->leftNode->color==RED&&w->rightNode->color==RED)//4.兄弟节点为黑色,孩子节点均为红色
    				{
    					/*4、若兄弟节点的左右子树都为红色,且兄弟节点为黑色,
    						将w的右子树置为黑色,w的颜色置为x的父节点一样的颜色,
    						这个时候父节点的颜色可以为红色也可以为黑色。然后左旋。*/
    					w->color==delNode->parentNode->color;
    					delNode->parentNode->color=BLACK;
    					w->rightNode->color=BLACK;
    					RotateLeft(delNode->parentNode);
    					delNode=root;//
    				}		 
    			}
    		}
    		else if (delNode==delNode->parentNode->rightNode)
    		{
    			w=delNode->parentNode->leftNode;
    			if (w->color==RED)
    			{
    				delNode->parentNode->color=RED;
    				w->color=BLACK;
    				RotateRight(delNode->parentNode);
    			}
    			else if (w->color==BLACK)
    			{
    				if (w->leftNode->color==BLACK&&w->rightNode->color==BLACK)
    				{
    					w->color=RED;
    					delNode=delNode->parentNode;
    				}
    				else if (w->rightNode->color==RED&&w->leftNode->color==BLACK)
    				{
    					w->rightNode->color=BLACK;
    					w->color=RED;
    					RotateLeft(w);
    				}
    			    if (w->rightNode==RED&&w->leftNode==RED)
    				{
    					w->leftNode=BLACK;
    					w->color=delNode->color;
    					delNode->parentNode=BLACK;
    					RotateRight(delNode->parentNode);
    				}
    			}
    		}
    	}
    	delNode->color=BLACK;
    	return true;
    }


     

    最后我们将x的颜色置为黑色

    从上面可以知道我们有两种情况会出循环,一种是兄弟节点与父节点都是红色,只要将父节点的颜色置为黑色。

    一种是4的情况,左旋使得通过x的节点黑色节点数目增加一个,达到平衡。

     

    展开全文
  • 红黑树插入删除详解

    万次阅读 多人点赞 2018-07-11 15:54:05
    红黑树插入删除操作的介绍转载自:红黑树 练习题转载自:红黑树练习 R-B Tree简介  R-B Tree,全称是Red-Black Tree,又称为“红黑树”,它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色,...

    红黑树插入删除操作的介绍转载自:红黑树

    练习题转载自:红黑树练习

    R-B Tree简介

        R-B Tree,全称是Red-Black Tree,又称为“红黑树”,它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色,可以是红(Red)或黑(Black)。

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

    注意
    (01) 特性(3)中的叶子节点,是只为空(NIL或null)的节点。
    (02) 特性(5),确保没有一条路径会比其他路径长出俩倍。因而,红黑树是相对是接近平衡的二叉树。

    红黑树示意图如下:

     

    红黑树的应用

    红黑树的应用比较广泛,主要是用它来存储有序的数据,它的时间复杂度是O(lgn),效率非常之高。
    例如,Java集合中的TreeSetTreeMap,C++ STL中的set、map,以及Linux虚拟内存的管理,都是通过红黑树去实现的。

     

    红黑树的时间复杂度和相关证明

    红黑树的时间复杂度为: O(logn)
    下面通过“数学归纳法”对红黑树的时间复杂度进行证明。

    定理:一棵含有n个节点的红黑树的高度至多为2log(n+1).

    证明:
        "一棵含有n个节点的红黑树的高度至多为2log(n+1)" 转换一下就是 "高度为h的红黑树,它的包含的内节点个数至少为 2^(h/2)-1个"。
        我们只需要证明后面那个命题,即可证明原命题为真;即只需证明 "高度为h的红黑树,它的包含的内节点个数至少为 2^(h/2)-1个"

        从某个节点x出发(不包括该节点)到达一个它子孙外部节点的任意一条路径上,黑色节点的个数称为该节点的黑高度(x's black height),记为bh(x)。关于bh(x)有两点需要说明: 
        第1点:根据红黑树的"特性(5) ,即从一个节点到该节点的子孙外部节点的所有路径上包含相同数目的黑节点"可知,从节点x出发到达的所有的叶节点具有相同数目的黑节点。这也就意味着,bh(x)的值是唯一的
        第2点:根据红黑色的"特性(4),即如果一个节点是红色的,则它的子节点必须是黑色的"可知,从节点x出发达到叶节点"所经历的黑节点数目">= "所经历的红节点的数目"。假设x是根节点,则可以得出结论"bh(x) >= h/2"。进而,我们只需证明 "高度为h的红黑树,它的包含的内节点个数至少为 2^bh(x)-1个"即可。

        到这里,我们将需要证明的定理已经由
    "一棵含有n个节点的红黑树的高度至多为2log(n+1)"
        转变成只需要证明
    "高度为h以x为根的红黑树,它的包含的内节点个数至少为 2^bh(x)-1个"。


    下面通过"数学归纳法"开始论证高度为h以x为根的红黑树,它的包含的内节点个数至少为 2^bh(x)-1个"。

    (01) 当树的高度h=0时,
        内节点个数是0,bh(x) 为0,2^bh(x)-1 也为 0。显然,原命题成立。

    (02) 考虑x的左右子节点,它们包含的节点个数至少为 2^(bh(x)-1)-1。推导理由如下:
        
    对于节点x(x为根节点),其黑高度为bh(x)。
        对于节点x的左右子树,当它们为红色时,黑高度为 bh(x);当它们为黑色时,黑高度为bh(x)-1。
        因此,x的左右子节点所包含的节点个数至少为2^(bh(x)-1)-1(因为黑高度最少为bh(x)-1)

    (03) 根据(02),我们已知 "x的左右子树,即高度为 h-1 的节点,它包含的节点至少为 2^(bh(x)-1)-1 个";

        所以,节点x所包含的节点至少为 (2^(bh(x)-1)-1 ) + (2^(bh(x)-1)-1) + 1 = 2^bh(x)-1。即节点x所包含的节点至少为 2^bh(x)-1。
        因此,原命题成立。

        由(01)、(02)得出,"高度为h的红黑树,它的包含的内节点个数至少为 2^bh(x)-1个"。
        因此,“一棵含有n个节点的红黑树的高度至多为2log(n+1)”。

    红黑树与AVL树的差别

    AVL是严格平衡树,因此在增加或者删除节点的时候,根据不同情况,旋转的次数比红黑树要多;
    红黑是弱平衡的,用非严格的平衡来换取增删节点时候旋转次数的降低;
    所以简单说,搜索的次数远远大于插入和删除,那么选择AVL树,如果搜索,插入删除次数几乎差不多,应该选择RB树。

    比如,下图是一个红黑树,但不是AVL树。

    红黑树的基本操作(一) 左旋和右旋

    红黑树的基本操作是添加删除。在对红黑树进行添加或删除之后,都会用到旋转方法。为什么呢?道理很简单,添加或删除红黑树中的节点之后,红黑树就发生了变化,可能不满足红黑树的5条性质,也就不再是一颗红黑树了,而是一颗普通的树。而通过旋转,可以使这颗树重新成为红黑树。简单点说,旋转的目的是让树保持红黑树的特性。
    旋转包括两种:左旋右旋。下面分别对它们进行介绍。

     

    1. 左旋

    对x进行左旋,意味着"将x变成一个左节点"。


    左旋的伪代码《算法导论》:参考上面的示意图和下面的伪代码,理解“红黑树T的节点x进行左旋”是如何进行的。

    LEFT-ROTATE(T, x)  
    01  y ← right[x]            // 前提:这里假设x的右孩子为y。下面开始正式操作
    02  right[x] ← left[y]      // 将 “y的左孩子” 设为 “x的右孩子”,即 将β设为x的右孩子
    03  p[left[y]] ← x          // 将 “x” 设为 “y的左孩子的父亲”,即 将β的父亲设为x
    04  p[y] ← p[x]             // 将 “x的父亲” 设为 “y的父亲”
    05  if p[x] = nil[T]       
    06  then root[T] ← y                 // 情况1:如果 “x的父亲” 是空节点,则将y设为根节点
    07  else if x = left[p[x]]  
    08            then left[p[x]] ← y    // 情况2:如果 x是它父节点的左孩子,则将y设为“x的父节点的左孩子”
    09            else right[p[x]] ← y   // 情况3:(x是它父节点的右孩子) 将y设为“x的父节点的右孩子”
    10  left[y] ← x             // 将 “x” 设为 “y的左孩子”
    11  p[x] ← y                // 将 “x的父节点” 设为 “y”

     

    理解左旋之后,看看下面一个更鲜明的例子。你可以先不看右边的结果,自己尝试一下。

     

    2. 右旋

    对x进行左旋,意味着"将x变成一个左节点"。


    右旋的伪代码《算法导论》:参考上面的示意图和下面的伪代码,理解“红黑树T的节点y进行右旋”是如何进行的。 

    RIGHT-ROTATE(T, y)  
    01  x ← left[y]             // 前提:这里假设y的左孩子为x。下面开始正式操作
    02  left[y] ← right[x]      // 将 “x的右孩子” 设为 “y的左孩子”,即 将β设为y的左孩子
    03  p[right[x]] ← y         // 将 “y” 设为 “x的右孩子的父亲”,即 将β的父亲设为y
    04  p[x] ← p[y]             // 将 “y的父亲” 设为 “x的父亲”
    05  if p[y] = nil[T]       
    06  then root[T] ← x                 // 情况1:如果 “y的父亲” 是空节点,则将x设为根节点
    07  else if y = right[p[y]]  
    08            then right[p[y]] ← x   // 情况2:如果 y是它父节点的右孩子,则将x设为“y的父节点的左孩子”
    09            else left[p[y]] ← x    // 情况3:(y是它父节点的左孩子) 将x设为“y的父节点的左孩子”
    10  right[x] ← y            // 将 “y” 设为 “x的右孩子”
    11  p[y] ← x                // 将 “y的父节点” 设为 “x”

     

    理解右旋之后,看看下面一个更鲜明的例子。你可以先不看右边的结果,自己尝试一下。


    旋转总结

    (01) 左旋 和 右旋 是相对的两个概念,原理类似。理解一个也就理解了另一个。

    (02) 下面谈谈如何区分 左旋 和 右旋。
    在实际应用中,若没有彻底理解 左旋 和 右旋,可能会将它们混淆。下面谈谈我对如何区分 左旋 和 右旋 的理解。

     

    3. 区分 左旋 和 右旋

    仔细观察上面"左旋"和"右旋"的示意图。我们能清晰的发现,它们是对称的。无论是左旋还是右旋,被旋转的树,在旋转前是二叉查找树,并且旋转之后仍然是一颗二叉查找树。

     

     

    左旋示例图(以x为节点进行左旋):

                                   z
       x                          /                  
      / \      --(左旋)-->       x
     y   z                      /
                               y

    对x进行左旋,意味着,将“x的右孩子”设为“x的父亲节点”;即,将 x变成了一个左节点(x成了为z的左孩子)!。 因此,左旋中的“左”,意味着“被旋转的节点将变成一个左节点”


    右旋示例图(以x为节点进行右旋):

                                   y
       x                            \                 
      / \      --(右旋)-->           x
     y   z                            \
                                       z

    对x进行右旋,意味着,将“x的左孩子”设为“x的父亲节点”;即,将 x变成了一个右节点(x成了为y的右孩子)! 因此,右旋中的“右”,意味着“被旋转的节点将变成一个右节点”

     

    红黑树的基本操作(二) 添加

    将一个节点插入到红黑树中,需要执行哪些步骤呢?首先,将红黑树当作一颗二叉查找树,将节点插入;然后,将节点着色为红色;最后,通过旋转和重新着色等方法来修正该树,使之重新成为一颗红黑树。详细描述如下:

    第一步: 将红黑树当作一颗二叉查找树,将节点插入。
           红黑树本身就是一颗二叉查找树,将节点插入后,该树仍然是一颗二叉查找树。也就意味着,树的键值仍然是有序的。此外,无论是左旋还是右旋,若旋转之前这棵树是二叉查找树,旋转之后它一定还是二叉查找树。这也就意味着,任何的旋转和重新着色操作,都不会改变它仍然是一颗二叉查找树的事实。
           好吧?那接下来,我们就来想方设法的旋转以及重新着色,使这颗树重新成为红黑树!

    第二步:将插入的节点着色为"红色"。
           为什么着色成红色,而不是黑色呢?为什么呢?在回答之前,我们需要重新温习一下红黑树的特性:
    (1) 每个节点或者是黑色,或者是红色。
    (2) 根节点是黑色。
    (3) 每个叶子节点是黑色。 [注意:这里叶子节点,是指为空的叶子节点!]
    (4) 如果一个节点是红色的,则它的子节点必须是黑色的。
    (5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
           将插入的节点着色为红色,不会违背"特性(5)"!少违背一条特性,就意味着我们需要处理的情况越少。接下来,就要努力的让这棵树满足其它性质即可;满足了的话,它就又是一颗红黑树了。o(∩∩)o...哈哈

    第三步: 通过一系列的旋转或着色等操作,使之重新成为一颗红黑树。
           第二步中,将插入节点着色为"红色"之后,不会违背"特性(5)"。那它到底会违背哪些特性呢?
           对于"特性(1)",显然不会违背了。因为我们已经将它涂成红色了。
           对于"特性(2)",显然也不会违背。在第一步中,我们是将红黑树当作二叉查找树,然后执行的插入操作。而根据二叉查找数的特点,插入操作不会改变根节点。所以,根节点仍然是黑色。
           对于"特性(3)",显然不会违背了。这里的叶子节点是指的空叶子节点,插入非空节点并不会对它们造成影响。
           对于"特性(4)",是有可能违背的!
           那接下来,想办法使之"满足特性(4)",就可以将树重新构造成红黑树了。

    下面看看代码到底是怎样实现这三步的。

     

    添加操作的伪代码《算法导论》

    RB-INSERT(T, z)  
    01  y ← nil[T]                        // 新建节点“y”,将y设为空节点。
    02  x ← root[T]                       // 设“红黑树T”的根节点为“x”
    03  while x ≠ nil[T]                  // 找出要插入的节点“z”在二叉树T中的位置“y”
    04      do y ← x                      
    05         if key[z] < key[x]  
    06            then x ← left[x]  
    07            else x ← right[x]  
    08  p[z] ← y                          // 设置 “z的父亲” 为 “y”
    09  if y = nil[T]                     
    10     then root[T] ← z               // 情况1:若y是空节点,则将z设为根
    11     else if key[z] < key[y]        
    12             then left[y] ← z       // 情况2:若“z所包含的值” < “y所包含的值”,则将z设为“y的左孩子”
    13             else right[y] ← z      // 情况3:(“z所包含的值” >= “y所包含的值”)将z设为“y的右孩子” 
    14  left[z] ← nil[T]                  // z的左孩子设为空
    15  right[z] ← nil[T]                 // z的右孩子设为空。至此,已经完成将“节点z插入到二叉树”中了。
    16  color[z] ← RED                    // 将z着色为“红色”
    17  RB-INSERT-FIXUP(T, z)             // 通过RB-INSERT-FIXUP对红黑树的节点进行颜色修改以及旋转,让树T仍然是一颗红黑树

     

    结合伪代码以及为代码上面的说明,先理解RB-INSERT。理解了RB-INSERT之后,我们接着对 RB-INSERT-FIXUP的伪代码进行说明。

    添加修正操作的伪代码《算法导论》

    RB-INSERT-FIXUP(T, z)
    01 while color[p[z]] = RED                                                  // 若“当前节点(z)的父节点是红色”,则进行以下处理。
    02     do if p[z] = left[p[p[z]]]                                           // 若“z的父节点”是“z的祖父节点的左孩子”,则进行以下处理。
    03           then y ← right[p[p[z]]]                                        // 将y设置为“z的叔叔节点(z的祖父节点的右孩子)”
    04                if color[y] = RED                                         // Case 1条件:叔叔是红色
    05                   then color[p[z]] ← BLACK                    ▹ Case 1   //  (01) 将“父节点”设为黑色。
    06                        color[y] ← BLACK                       ▹ Case 1   //  (02) 将“叔叔节点”设为黑色。
    07                        color[p[p[z]]] ← RED                   ▹ Case 1   //  (03) 将“祖父节点”设为“红色”。
    08                        z ← p[p[z]]                            ▹ Case 1   //  (04) 将“祖父节点”设为“当前节点”(红色节点)
    09                   else if z = right[p[z]]                                // Case 2条件:叔叔是黑色,且当前节点是右孩子
    10                           then z ← p[z]                       ▹ Case 2   //  (01) 将“父节点”作为“新的当前节点”。
    11                                LEFT-ROTATE(T, z)              ▹ Case 2   //  (02) 以“新的当前节点”为支点进行左旋。
    12                           color[p[z]] ← BLACK                 ▹ Case 3   // Case 3条件:叔叔是黑色,且当前节点是左孩子。(01) 将“父节点”设为“黑色”。
    13                           color[p[p[z]]] ← RED                ▹ Case 3   //  (02) 将“祖父节点”设为“红色”。
    14                           RIGHT-ROTATE(T, p[p[z]])            ▹ Case 3   //  (03) 以“祖父节点”为支点进行右旋。
    15        else (same as then clause with "right" and "left" exchanged)      // 若“z的父节点”是“z的祖父节点的右孩子”,将上面的操作中“right”和“left”交换位置,然后依次执行。
    16 color[root[T]] ← BLACK 

     

    根据被插入节点的父节点的情况,可以将"当节点z被着色为红色节点,并插入二叉树"划分为三种情况来处理。
    ① 情况说明:被插入的节点是根节点。
        处理方法:直接把此节点涂为黑色。
    ② 情况说明:被插入的节点的父节点是黑色。
        处理方法:什么也不需要做。节点被插入后,仍然是红黑树。
    ③ 情况说明:被插入的节点的父节点是红色。
        处理方法:那么,该情况与红黑树的“特性(5)”相冲突。这种情况下,被插入节点是一定存在非空祖父节点的;进一步的讲,被插入节点也一定存在叔叔节点(即使叔叔节点为空,我们也视之为存在,空节点本身就是黑色节点)。理解这点之后,我们依据"叔叔节点的情况",将这种情况进一步划分为3种情况(Case)。

     现象说明处理策略
    Case 1当前节点的父节点是红色,且当前节点的祖父节点的另一个子节点(叔叔节点)也是红色。

    (01) 将“父节点”设为黑色。
    (02) 将“叔叔节点”设为黑色。
    (03) 将“祖父节点”设为“红色”。
    (04) 将“祖父节点”设为“当前节点”(红色节点);即,之后继续对“当前节点”进行操作。

    Case 2当前节点的父节点是红色,叔叔节点是黑色,且当前节点是其父节点的右孩子

    (01) 将“父节点”作为“新的当前节点”。
    (02) 以“新的当前节点”为支点进行左旋。

    Case 3当前节点的父节点是红色,叔叔节点是黑色,且当前节点是其父节点的左孩子

    (01) 将“父节点”设为“黑色”。
    (02) 将“祖父节点”设为“红色”。
    (03) 以“祖父节点”为支点进行右旋。

    上面三种情况(Case)处理问题的核心思路都是:将红色的节点移到根节点;然后,将根节点设为黑色。下面对它们详细进行介绍。

     

    1. (Case 1)叔叔是红色

    1.1 现象说明
    当前节点(即,被插入节点)的父节点是红色,且当前节点的祖父节点的另一个子节点(叔叔节点)也是红色。

    1.2 处理策略
    (01) 将“父节点”设为黑色。
    (02) 将“叔叔节点”设为黑色。
    (03) 将“祖父节点”设为“红色”。
    (04) 将“祖父节点”设为“当前节点”(红色节点);即,之后继续对“当前节点”进行操作。

        下面谈谈为什么要这样处理。(建议理解的时候,通过下面的图进行对比)
        “当前节点”和“父节点”都是红色,违背“特性(4)”。所以,将“父节点”设置“黑色”以解决这个问题。
        但是,将“父节点”由“红色”变成“黑色”之后,违背了“特性(5)”:因为,包含“父节点”的分支的黑色节点的总数增加了1。  解决这个问题的办法是:将“祖父节点”由“黑色”变成红色,同时,将“叔叔节点”由“红色”变成“黑色”。关于这里,说明几点:第一,为什么“祖父节点”之前是黑色?这个应该很容易想明白,因为在变换操作之前,该树是红黑树,“父节点”是红色,那么“祖父节点”一定是黑色。 第二,为什么将“祖父节点”由“黑色”变成红色,同时,将“叔叔节点”由“红色”变成“黑色”;能解决“包含‘父节点’的分支的黑色节点的总数增加了1”的问题。这个道理也很简单。“包含‘父节点’的分支的黑色节点的总数增加了1” 同时也意味着 “包含‘祖父节点’的分支的黑色节点的总数增加了1”,既然这样,我们通过将“祖父节点”由“黑色”变成“红色”以解决“包含‘祖父节点’的分支的黑色节点的总数增加了1”的问题; 但是,这样处理之后又会引起另一个问题“包含‘叔叔’节点的分支的黑色节点的总数减少了1”,现在我们已知“叔叔节点”是“红色”,将“叔叔节点”设为“黑色”就能解决这个问题。 所以,将“祖父节点”由“黑色”变成红色,同时,将“叔叔节点”由“红色”变成“黑色”;就解决了该问题。
        按照上面的步骤处理之后:当前节点、父节点、叔叔节点之间都不会违背红黑树特性,但祖父节点却不一定。若此时,祖父节点是根节点,直接将祖父节点设为“黑色”,那就完全解决这个问题了;若祖父节点不是根节点,那我们需要将“祖父节点”设为“新的当前节点”,接着对“新的当前节点”进行分析。

    1.3 示意图(图120节点应该为黑色,140为红色。但是不影响这种情况。c表示当前节点)

     

    2. (Case 2)叔叔是黑色,且当前节点是右孩子

    2.1 现象说明
    当前节点(即,被插入节点)的父节点是红色,叔叔节点是黑色,且当前节点是其父节点的右孩子

    2.2 处理策略
    (01) 将“父节点”作为“新的当前节点”。
    (02) 以“新的当前节点”为支点进行左旋。

          下面谈谈为什么要这样处理。(建议理解的时候,通过下面的图进行对比)
          首先,将“父节点”作为“新的当前节点”;接着,以“新的当前节点”为支点进行左旋。 为了便于理解,我们先说明第(02)步,再说明第(01)步;为了便于说明,我们设置“父节点”的代号为F(Father),“当前节点”的代号为S(Son)。
    为什么要“以F为支点进行左旋”呢?根据已知条件可知:S是F的右孩子。而之前我们说过,我们处理红黑树的核心思想:将红色的节点移到根节点;然后,将根节点设为黑色。既然是“将红色的节点移到根节点”,那就是说要不断的将破坏红黑树特性的红色节点上移(即向根方向移动)。 而S又是一个右孩子,因此,我们可以通过“左旋”来将S上移!
          按照上面的步骤(以F为支点进行左旋)处理之后:若S变成了根节点,那么直接将其设为“黑色”,就完全解决问题了;若S不是根节点,那我们需要执行步骤(01),即“将F设为‘新的当前节点’”。那为什么不继续以S为新的当前节点继续处理,而需要以F为新的当前节点来进行处理呢?这是因为“左旋”之后,F变成了S的“子节点”,即S变成了F的父节点;而我们处理问题的时候,需要从下至上(由叶到根)方向进行处理;也就是说,必须先解决“孩子”的问题,再解决“父亲”的问题;所以,我们执行步骤(01):将“父节点”作为“新的当前节点”。

    2.2 示意图(图有错,120为黑色,140为红色,c为当前节点)

     

    3. (Case 3)叔叔是黑色,且当前节点是左孩子

    3.1 现象说明
    当前节点(即,被插入节点)的父节点是红色,叔叔节点是黑色,且当前节点是其父节点的左孩子

    3.2 处理策略
    (01) 将“父节点”设为“黑色”。
    (02) 将“祖父节点”设为“红色”。
    (03) 以“祖父节点”为支点进行右旋。

          下面谈谈为什么要这样处理。(建议理解的时候,通过下面的图进行对比)
          为了便于说明,我们设置“当前节点”为S(Original Son),“兄弟节点”为B(Brother),“叔叔节点”为U(Uncle),“父节点”为F(Father),祖父节点为G(Grand-Father)。
          S和F都是红色,违背了红黑树的“特性(4)”,我们可以将F由“红色”变为“黑色”,就解决了“违背‘特性(4)’”的问题;但却引起了其它问题:违背特性(5),因为将F由红色改为黑色之后,所有经过F的分支的黑色节点的个数增加了1。那我们如何解决“所有经过F的分支的黑色节点的个数增加了1”的问题呢? 我们可以通过“将G由黑色变成红色”,同时“以G为支点进行右旋”来解决。

    2.3 示意图(图有错,120为黑色,140为红色,c为当前节点)

    原文的评论区有一个关于红黑树插入很精辟的总结:

    case1
    是为了一层一层向上递归 递归到根节点 直接黑掉根节点的红色

    case2
    这种情况不好处理,或者说仅仅为了从左到右的习惯,把这个棘手的右孩 子转为左孩子处理(可以这么理解、虽然这样不对)这样的结果就是变成了case3

    case3
    默认添加之前该树就是红黑树,这么一处理就对了,不需要再处理。循环到此结束!

    综上所述针对添加操作怎么复原红黑树?
    第一种情况:递归到根节点、直接黑掉根节点
    第二种情况:这种情况不处理,直接转成第三种情况
    第三种情况:一次到位。

    红黑树的基本操作(三) 删除

    将红黑树内的某一个节点删除。需要执行的操作依次是:首先,将红黑树当作一颗二叉查找树,将该节点从二叉查找树中删除;然后,通过"旋转和重新着色"等一系列来修正该树,使之重新成为一棵红黑树。详细描述如下:

    第一步:将红黑树当作一颗二叉查找树,将节点删除。
           这和"删除常规二叉查找树中删除节点的方法是一样的"。分3种情况:
           ① 被删除节点没有儿子,即为叶节点。那么,直接将该节点删除就OK了。
           ② 被删除节点只有一个儿子。那么,直接删除该节点,并用该节点的唯一子节点顶替它的位置。
           ③ 被删除节点有两个儿子。那么,先找出它的后继节点;然后把“它的后继节点的内容”复制给“该节点的内容”;之后,删除“它的后继节点”。在这里,后继节点相当于替身,在将后继节点的内容复制给"被删除节点"之后,再将后继节点删除。这样就巧妙的将问题转换为"删除后继节点"的情况了,下面就考虑后继节点。 在"被删除节点"有两个非空子节点的情况下,它的后继节点不可能是双子非空。既然"的后继节点"不可能双子都非空,就意味着"该节点的后继节点"要么没有儿子,要么只有一个儿子。若没有儿子,则按"情况① "进行处理;若只有一个儿子,则按"情况② "进行处理。

    第二步:通过"旋转和重新着色"等一系列来修正该树,使之重新成为一棵红黑树。
           因为"第一步"中删除节点之后,可能会违背红黑树的特性。所以需要通过"旋转和重新着色"来修正该树,使之重新成为一棵红黑树。

     

    删除操作的伪代码《算法导论》

    RB-DELETE(T, z)
    01 if left[z] = nil[T] or right[z] = nil[T]         
    02    then y ← z                                  // 若“z的左孩子” 或 “z的右孩子”为空,则将“z”赋值给 “y”;
    03    else y ← TREE-SUCCESSOR(z)                  // 否则,将“z的后继节点”赋值给 “y”。
    04 if left[y] ≠ nil[T]
    05    then x ← left[y]                            // 若“y的左孩子” 不为空,则将“y的左孩子” 赋值给 “x”;
    06    else x ← right[y]                           // 否则,“y的右孩子” 赋值给 “x”。
    07 p[x] ← p[y]                                    // 将“y的父节点” 设置为 “x的父节点”
    08 if p[y] = nil[T]                               
    09    then root[T] ← x                            // 情况1:若“y的父节点” 为空,则设置“x” 为 “根节点”。
    10    else if y = left[p[y]]                    
    11            then left[p[y]] ← x                 // 情况2:若“y是它父节点的左孩子”,则设置“x” 为 “y的父节点的左孩子”
    12            else right[p[y]] ← x                // 情况3:若“y是它父节点的右孩子”,则设置“x” 为 “y的父节点的右孩子”
    13 if y ≠ z                                    
    14    then key[z] ← key[y]                        // 若“y的值” 赋值给 “z”。注意:这里只拷贝z的值给y,而没有拷贝z的颜色!!!
    15         copy y's satellite data into z         
    16 if color[y] = BLACK                            
    17    then RB-DELETE-FIXUP(T, x)                  // 若“y为黑节点”,则调用
    18 return y 

     

    结合伪代码以及为代码上面的说明,先理解RB-DELETE,y是被删除的节点,x是替代y的节点。理解了RB-DELETE之后,接着对 RB-DELETE-FIXUP的伪代码进行说明

    RB-DELETE-FIXUP(T, x)
    01 while x ≠ root[T] and color[x] = BLACK  
    02     do if x = left[p[x]]      
    03           then w ← right[p[x]]                                             // 若 “x”是“它父节点的左孩子”,则设置 “w”为“x的叔叔”(即x为它父节点的右孩子)                                          
    04                if color[w] = RED                                           // Case 1: x是“黑+黑”节点,x的兄弟节点是红色。(此时x的父节点和x的兄弟节点的子节点都是黑节点)。
    05                   then color[w] ← BLACK                        ▹  Case 1   //   (01) 将x的兄弟节点设为“黑色”。
    06                        color[p[x]] ← RED                       ▹  Case 1   //   (02) 将x的父节点设为“红色”。
    07                        LEFT-ROTATE(T, p[x])                    ▹  Case 1   //   (03) 对x的父节点进行左旋。
    08                        w ← right[p[x]]                         ▹  Case 1   //   (04) 左旋后,重新设置x的兄弟节点。
    09                if color[left[w]] = BLACK and color[right[w]] = BLACK       // Case 2: x是“黑+黑”节点,x的兄弟节点是黑色,x的兄弟节点的两个孩子都是黑色。
    10                   then color[w] ← RED                          ▹  Case 2   //   (01) 将x的兄弟节点设为“红色”。
    11                        x ←  p[x]                               ▹  Case 2   //   (02) 设置“x的父节点”为“新的x节点”。
    12                   else if color[right[w]] = BLACK                          // Case 3: x是“黑+黑”节点,x的兄弟节点是黑色;x的兄弟节点的左孩子是红色,右孩子是黑色的。
    13                           then color[left[w]] ← BLACK          ▹  Case 3   //   (01) 将x兄弟节点的左孩子设为“黑色”。
    14                                color[w] ← RED                  ▹  Case 3   //   (02) 将x兄弟节点设为“红色”。
    15                                RIGHT-ROTATE(T, w)              ▹  Case 3   //   (03) 对x的兄弟节点进行右旋。
    16                                w ← right[p[x]]                 ▹  Case 3   //   (04) 右旋后,重新设置x的兄弟节点。
    17                         color[w] ← color[p[x]]                 ▹  Case 4   // Case 4: x是“黑+黑”节点,x的兄弟节点是黑色;x的兄弟节点的右孩子是红色的。(01) 将x父节点颜色 赋值给 x的兄弟节点。
    18                         color[p[x]] ← BLACK                    ▹  Case 4   //   (02) 将x父节点设为“黑色”。
    19                         color[right[w]] ← BLACK                ▹  Case 4   //   (03) 将x兄弟节点的右子节设为“黑色”。
    20                         LEFT-ROTATE(T, p[x])                   ▹  Case 4   //   (04) 对x的父节点进行左旋。
    21                         x ← root[T]                            ▹  Case 4   //   (05) 设置“x”为“根节点”。
    22        else (same as then clause with "right" and "left" exchanged)        // 若 “x”是“它父节点的右孩子”,将上面的操作中“right”和“left”交换位置,然后依次执行。
    23 color[x] ← BLACK   

     

    下面对删除函数进行分析。在分析之前,我们再次温习一下红黑树的几个特性:
    (1) 每个节点或者是黑色,或者是红色。
    (2) 根节点是黑色。
    (3) 每个外部叶子节点是黑色。 [注意:这里叶子节点,是指为空的叶子节点!]
    (4) 如果一个节点是红色的,则它的子节点必须是黑色的。
    (5) 从一个节点到该节点的子孙外部节点的所有路径上包含相同数目的黑节点。


          前面我们将"删除红黑树中的节点"大致分为两步,在第一步中"将红黑树当作一颗二叉查找树,将节点删除"后,可能违反"特性(2)、(4)、(5)"三个特性。第二步需要解决上面的三个问题,进而保持红黑树的全部特性。
          为了便于分析,我们假设"x包含一个额外的黑色"(x原本的颜色还存在),这样就不会违反"特性(5)"。为什么呢?
          通过RB-DELETE算法,我们知道:删除节点y之后,x占据了原来节点y的位置。 既然删除y(y是黑色),意味着减少一个黑色节点;那么,再在该位置上增加一个黑色即可。这样,当我们假设"x包含一个额外的黑色",就正好弥补了"删除y所丢失的黑色节点",也就不会违反"特性(5)"。 因此,假设"x包含一个额外的黑色"(x原本的颜色还存在),这样就不会违反"特性(5)"。
          现在,x不仅包含它原本的颜色属性,x还包含一个额外的黑色。即x的颜色属性是"红+黑"或"黑+黑",它违反了"特性(1)"。

          现在,我们面临的问题,由解决"违反了特性(2)、(4)、(5)三个特性"转换成了"解决违反特性(1)、(2)、(4)三个特性"。RB-DELETE-FIXUP需要做的就是通过算法恢复红黑树的特性(1)、(2)、(4)。RB-DELETE-FIXUP的思想是:将x所包含的额外的黑色不断沿树上移(向根方向移动),直到出现下面的姿态:
    a) x指向一个"红+黑"节点。此时,将x设为一个"黑"节点即可。
    b) x指向根。此时,将x设为一个"黑"节点即可。
    c) 非前面两种姿态。

    将上面的姿态,可以概括为3种情况。
    ① 情况说明:x是“红+黑”节点。
        处理方法:直接把x设为黑色,结束。此时红黑树性质全部恢复。
    ② 情况说明:x是“黑+黑”节点,且x是根。
        处理方法:什么都不做,结束。此时红黑树性质全部恢复。
    ③ 情况说明:x是“黑+黑”节点,且x不是根。
        处理方法:这种情况又可以划分为4种子情况。这4种子情况如下表所示:

     现象说明处理策略
    Case 1x是"黑+黑"节点,x的兄弟节点是红色。(此时x的父节点和x的兄弟节点的子节点都是黑节点)。

    (01) 将x的兄弟节点设为“黑色”。
    (02) 将x的父节点设为“红色”。
    (03) 对x的父节点进行左旋。
    (04) 左旋后,重新设置x的兄弟节点。

    Case 2x是“黑+黑”节点,x的兄弟节点是黑色,x的兄弟节点的两个孩子都是黑色。

    (01) 将x的兄弟节点设为“红色”。
    (02) 设置“x的父节点”为“新的x节点”。

    Case 3x是“黑+黑”节点,x的兄弟节点是黑色;x的兄弟节点的左孩子是红色,右孩子是黑色的。(其实这里要区分,x是父节点的左子树还是右子树,x是左子树则按这里的规则处理;若x是右子树,则左变右,右变左)

    (01) 将x兄弟节点的左孩子设为“黑色”。
    (02) 将x兄弟节点设为“红色”。
    (03) 对x的兄弟节点进行右旋。
    (04) 右旋后,重新设置x的兄弟节点。

    Case 4x是“黑+黑”节点,x的兄弟节点是黑色;x的兄弟节点的右孩子是红色的,x的兄弟节点的左孩子任意颜色。(同上)

    (01) 将x父节点颜色 赋值给 x的兄弟节点。
    (02) 将x父节点设为“黑色”。
    (03) 将x兄弟节点的右子节设为“黑色”。
    (04) 对x的父节点进行左旋。
    (05) 设置“x”为“根节点”。

     

    1. (Case 1)x是"黑+黑"节点,x的兄弟节点是红色

    1.1 现象说明
    x是"黑+黑"节点,x的兄弟节点是红色。(此时x的父节点和x的兄弟节点的子节点都是黑节点)。

    1.2 处理策略
    (01) 将x的兄弟节点设为“黑色”。
    (02) 将x的父节点设为“红色”。
    (03) 对x的父节点进行左旋。
    (04) 左旋后,重新设置x的兄弟节点。

          下面谈谈为什么要这样处理。(建议理解的时候,通过下面的图进行对比)
          这样做的目的是将“Case 1”转换为“Case 2”、“Case 3”或“Case 4”,从而进行进一步的处理。对x的父节点进行左旋;左旋后,为了保持红黑树特性,就需要在左旋前“将x的兄弟节点设为黑色”,同时“将x的父节点设为红色”;左旋后,由于x的兄弟节点发生了变化,需要更新x的兄弟节点,从而进行后续处理。

    1.3 示意图(图有错,右边D是黑色,B是红色)

     

    2. (Case 2) x是"黑+黑"节点,x的兄弟节点是黑色,x的兄弟节点的两个孩子都是黑色

    2.1 现象说明
    x是“黑+黑”节点,x的兄弟节点是黑色,x的兄弟节点的两个孩子都是黑色。

    2.2 处理策略
    (01) 将x的兄弟节点设为“红色”。
    (02) 设置“x的父节点”为“新的x节点”。

          下面谈谈为什么要这样处理。(建议理解的时候,通过下面的图进行对比)
          这个情况的处理思想:是将“x中多余的一个黑色属性上移(往根方向移动)”。 x是“黑+黑”节点,我们将x由“黑+黑”节点 变成 “黑”节点,多余的一个“黑”属性移到x的父节点中,即x的父节点多出了一个黑属性(若x的父节点原先是“黑”,则此时变成了“黑+黑”;若x的父节点原先时“红”,则此时变成了“红+黑”)。 此时,需要注意的是:所有经过x的分支中黑节点个数没变化;但是,所有经过x的兄弟节点的分支中黑色节点的个数增加了1(因为x的父节点多了一个黑色属性)!为了解决这个问题,我们需要将“所有经过x的兄弟节点的分支中黑色节点的个数减1”即可,那么就可以通过“将x的兄弟节点由黑色变成红色”来实现。
          经过上面的步骤(将x的兄弟节点设为红色),多余的一个颜色属性(黑色)已经跑到x的父节点中。我们需要将x的父节点设为“新的x节点”进行处理。若“新的x节点”是“黑+红”,直接将“新的x节点”设为黑色,即可完全解决该问题;若“新的x节点”是“黑+黑”,则需要对“新的x节点”进行进一步处理。

    2.3 示意图(B的颜色可以是红+黑,也可以是黑+黑)

     

    3. (Case 3)x是“黑+黑”节点,x的兄弟节点是黑色;x的兄弟节点的左孩子是红色,右孩子是黑色的

    3.1 现象说明
    x是“黑+黑”节点,x的兄弟节点是黑色;x的兄弟节点的左孩子是红色,右孩子是黑色的。

    3.2 处理策略
    (01) 将x兄弟节点的左孩子设为“黑色”。
    (02) 将x兄弟节点设为“红色”。
    (03) 对x的兄弟节点进行右旋。
    (04) 右旋后,重新设置x的兄弟节点。

           下面谈谈为什么要这样处理。(建议理解的时候,通过下面的图进行对比)
           我们处理“Case 3”的目的是为了将“Case 3”进行转换,转换成“Case 4”,从而进行进一步的处理。转换的方式是对x的兄弟节点进行右旋;为了保证右旋后,它仍然是红黑树,就需要在右旋前“将x的兄弟节点的左孩子设为黑色”,同时“将x的兄弟节点设为红色”;右旋后,由于x的兄弟节点发生了变化,需要更新x的兄弟节点,从而进行后续处理。

    3.3 示意图

     

    4. (Case 4)x是“黑+黑”节点,x的兄弟节点是黑色;x的兄弟节点的右孩子是红色的,x的兄弟节点的左孩子任意颜色

    4.1 现象说明
    x是“黑+黑”节点,x的兄弟节点是黑色;x的兄弟节点的右孩子是红色的,x的兄弟节点的左孩子任意颜色。

    4.2 处理策略
    (01) 将x父节点颜色 赋值给 x的兄弟节点。
    (02) 将x父节点设为“黑色”。
    (03) 将x兄弟节点的右子节设为“黑色”。
    (04) 对x的父节点进行左旋。
    (05) 设置“x”为“根节点”。

          下面谈谈为什么要这样处理。(建议理解的时候,通过下面的图进行对比)
          我们处理“Case 4”的目的是:去掉x中额外的黑色,将x变成单独的黑色。处理的方式是“:进行颜色修改,然后对x的父节点进行左旋。下面,我们来分析是如何实现的。
          为了便于说明,我们设置“当前节点”为S(Original Son),“兄弟节点”为B(Brother),“兄弟节点的左孩子”为BLS(Brother's Left Son),“兄弟节点的右孩子”为BRS(Brother's Right Son),“父节点”为F(Father)。
          我们要对F进行左旋。但在左旋前,我们需要调换F和B的颜色,并设置BRS为黑色。为什么需要这里处理呢?因为左旋后,F和BLS是父子关系,而我们已知BL是红色,如果F是红色,则违背了“特性(4)”;为了解决这一问题,我们将“F设置为黑色”。 但是,F设置为黑色之后,为了保证满足“特性(5)”,即为了保证左旋之后:
          第一,“同时经过根节点和S的分支的黑色节点个数不变”。
                 若满足“第一”,只需要S丢弃它多余的颜色即可。因为S的颜色是“黑+黑”,而左旋后“同时经过根节点和S的分支的黑色节点个数”增加了1;现在,只需将S由“黑+黑”变成单独的“黑”节点,即可满足“第一”。
          第二,“同时经过根节点和BLS的分支的黑色节点数不变”。
                 若满足“第二”,只需要将“F的原始颜色”赋值给B即可。之前,我们已经将“F设置为黑色”(即,将B的颜色"黑色",赋值给了F)。至此,我们算是调换了F和B的颜色。
          第三,“同时经过根节点和BRS的分支的黑色节点数不变”。
                 在“第二”已经满足的情况下,若要满足“第三”,只需要将BRS设置为“黑色”即可。
    经过,上面的处理之后。红黑树的特性全部得到的满足!接着,我们将x设为根节点,就可以跳出while循环(参考伪代码);即完成了全部处理。

    至此,我们就完成了Case 4的处理。理解Case 4的核心,是了解如何“去掉当前节点额外的黑色”。

    4.3 示意图

    ============================================================================

    1、红黑树插入的例子

     

    情况1

    如果叔叔结点为红色。

    下图为插入N节点的情况。

    转换前:

     

    \

    转换后:

     

    \

    上图中将情况1转换为了情况2.

    情况2:

    叔叔节点为黑色:插入节点是父结点的右孩子。

    继续上图的转换,转换后:

    \

    这时情况2转换为了情况3:

    情况3

    叔叔节点为黑色:插入节点为左孩子。

    \

     

     

     

    2、红黑树删除的例子

     

    有一棵红黑树12 1 9 2 0 11 7 19 4 15 18 5 14 13 10 16 6 3 8 17,如图10

     

    \

    图10

    1.删除结点12

    结点12有两个非空子结点,首先调整为叶结点,与其后继结点13进行值交换,然后删除12;由于后继结点为黑色,删除后出现“双黑”,

    如图11

     

    \

    图11

    此时,属于第一种情况的A种,处理后结果如图12

     

    \

    图12

    2.删除1结点

    1结点有两个非空子结点,调整为叶子结点,与其后继结点2进行值 交换;此时,1结点只有一个非空子结点,则删除1结点后,将其子结点着为黑色,处理结果如图13

     

    \

    图13

    3.删除9

    9结点为根结点,调整为叶结点,与后继结点10值交换,由于后继结点为黑色,删除后9后,出现双黑,如图14

     

     

    \

    图14

    此时为双黑处理第二种情况,处理后,如图15

    \

    图15

    4.删除结点2

    结点2有两个非空子结点,与后继结点3值交换;后继结点为黑色,删除2后,出现双黑;如图16

    \

    图16

    此时,为双黑处理第二种情况,处理后,如图17

     

    \

    图17

    5.删除结点0

    结点0为红色结点,直接删除即可

    6.删除结点11

    结点11有一个非空子结点,为第二种情况,删除11 后,将其非空子结点着为黑色,如图18

     

    \

    图18

     

    7.删除结点7

    结点7有一个非空子结点,也为第二种情况,删除7后,将其非空子结点着为黑色;

    8.删除结点19

    结点19为叶子结点,且为黑色,删除后出现“双黑”,属于双黑处理的第一种情况,处理后如图19

     

    \

    图19

    9.删除结点4

    结点4有两个非空子树,与其后继结点5交换;后继结点为黑色,删除4后,出现双黑,此时为双黑处理第二种情况,处理后如图20

    \

    图20

    10.删除结点15

    结点15为叶子结点,删除后出现“双黑”,此时属于双黑处理第一种情况的B种,处理后如图21

    \

    图21

    11.删除结点18

    结点18为叶子结点,且为黑色,删除后出现双黑,属于双黑处理的第二种情况,处理后,如图22

     

    \

    图22

    12.删除结点5

    结点5有两个子结点,与其后继结点6交换;交换后,结点5只有一个非空子结点,属于第二种情况,直接删除,将非空子结点着黑色,如图23

    \

    图23

    13.删除结点14

    结点14有两个子树,与其后继结点16交换;后继结点为红色,交换后14 为红色,直接删除。

    14.删除结点13

    结点13为叶子结点,且为黑色,删除后出现“双黑”,属于双黑处理的第二种情况,处理后如图24

    \

    图24

    15.删除结点10

    结点10为根结点,与其后继16值交换;交换后10只有一个非空子结点,直接将10删除,将非空子结点着为黑色

    16.删除结点16

    结点16为根结点,与后继结点17值交换;交换后16为叶子结点,且为黑色,删除后出现双黑,属于双黑处理的第三种情况,处理后如图25

    \

    图25

    17.删除结点6

    结点6为根结点,与后继结点8值交换;交换后,结点6为红色,直接删除

    \

    18.删除结点3

    结点3为叶子结点,且为黑色,删除后出现“双黑”,属于双黑处理的第二种情况

    \

    删除8:

    \

    删除17:

    \

     

    展开全文
  • 红黑树详解

    2021-08-21 10:31:46
    1. 红黑树的提出 既然平衡树家族中已经有了AVL树这种成员,并且其时间复杂度已经达到了 O(logh)O(logh)O(logh) 的要求,那么为啥要提出红黑树呢? 我们来回顾一下AVL树的操作: 插入操作:在AVL树中插入一个数,...

    1. 红黑树的提出

    友情提示:本文需要在了解平衡二叉树、AVL树和B-树的背景下阅读,如果对这三个数据结构还不了解的小伙伴可以读一下我的另外三篇文章:【数组模拟二叉搜索树(二叉排序树)】【数组模拟AVL树(平衡二叉树)】【B-树的详解】

    既然平衡树家族中已经有了AVL树这种成员,并且其时间复杂度已经达到了 O ( l o g h ) O(logh) O(logh) 的要求,那么为啥要提出红黑树呢?

    我们来回顾一下AVL树的操作:

    1. 插入操作:在AVL树中插入一个数,只要经过一次 O ( 1 ) O(1) O(1) 的旋转操作,AVL树局部乃至整个树的高度都能够复原。
    2. 删除操作:在AVL树中删除一个数,有可能自底而上逐层引发 l o g h logh logh 次的 O ( 1 ) O(1) O(1) 旋转,导致树型拓扑结构的剧烈变化

    因此,在涉及到大量的动态操作时,我们希望其引发的结构变化量不超过 O ( 1 ) O(1) O(1),对树型拓扑结构的影响都能控制在常数的范围之内。而红黑树,就是这样的一种树型结构。

    2. 红黑树的定义

    红黑树是由红、黑两类结点组成的二叉搜索树,和B-树类似,红黑树将所有的内部结点都增设了外部结点NULL,如下图。
    在这里插入图片描述
    定义规则可以总结为如下几点:

    1. 树根:必须为黑色(只针对非空红黑树)
    2. 外部结点:均为黑色(实际上外部结点根本不必存在,引入外部结点只是便于红黑树的分析)
    3. 内部结点:若为红,则结点的孩子、父亲必为黑
    4. 外部结点到根:途中经过的黑结点数目相等,又称为黑深度(这就是红黑书的“平衡”)

    如果将红黑树比作人,可以将树根看成人的帽子,外部结点看做人的靴子,下图是一棵红黑树。
    在这里插入图片描述
    细心的同学可以发现,图中并没有所谓的“外部结点”,其实外部结点本质不存在,其定义只是便于我们分析红黑树,下图中手工标注了三个外部结点(外部结点颜色是黑)。
    在这里插入图片描述
    在红黑树中任意两个不同的外部结点到达根结点的路径中经过的黑结点数量一定相同,如下图,都是三个。
    在这里插入图片描述
    上面大致介绍了一下红黑树的定义和相关规则,但是相信各位同学还是一头雾水,这个红黑树为啥要这么玩?

    那么,有没有什么更为直观的解释呢?这里,为了更好的理解红黑树,我们要先介绍一种树型结构的另一种等价拓扑变换—提升变换

    提升变换:将每一个红色结点从视觉上提升到其黑色的父亲结点一侧,如下图:

    经过红色结点上升操作之后,绝对不会出现两个红色结点紧挨着的情况,即便并列,中间也必然夹有一个黑色结点,也就是他们的父亲结点。
    在这里插入图片描述

    下图是变换之前的某棵红黑树:
    在这里插入图片描述
    所有的红色结点提升到父亲结点旁边之后,如下图(蓝色圈圈只是圈出了部分):
    在这里插入图片描述
    看到现在,相信你已经有点“感觉”了。别急,我们再继续看一个更大的实例,请特别注意底层的叶子结点,目前都是高低错落此起彼伏的:
    在这里插入图片描述
    经过红色结点提升变换后,所有底层的叶子结点都变成了沿统一水平高度平齐的高度:
    在这里插入图片描述
    尽管红黑树的规则看起来“高深莫测”,但是经过红色结点提升变换之后,他的结构就更加清晰明了。

    提升各个红色结点,使之与其父亲黑色结点等高,从这个角度来看,每一棵红黑树就是4阶的B-树,也就是(2, 4)-树,如果你对B-树不熟悉,可以看我的另一篇博客:【B-树的详解】

    因此我们只需要将红黑树中的黑色结点与其上提的红色孩子(关键字合并)视作4阶B-树中的一个结点 ,根据黑色根结点左右孩子的颜色分为四种组合,每种组合分别对应于4阶B-树的一类内部结点:
    在这里插入图片描述
    上面的图中,我们特别用虚线标出黑色结点指向红色结点的原因是:因为红黑树平衡的关键在于黑高度的统一,红色结点的存在其实对黑高度的计算没有贡献。

    3. 红黑树的查找

    红黑树的查找操作和传统的二叉搜索树一致,这里不再赘述。

    4. 红黑树的插入

    与了解红黑树的定义一样,我们会发现红黑树和与其对应的“影子B-树”之间的关系非常好理解,而且反过来也是如此,这样理解红黑树的原理表面看来有点迂回,但我们很快就会感受到,这种间接的理解方式学习红黑树反而是效率最高的

    在这里插入图片描述

    4.1 插入操作的算法框架

    1. 首先,传入待插入的关键字 e e e (不妨假设树中原来不存在 e e e

    2. 按照二叉搜索树的常规插入算法,插入关键字, x = i n s e r t ( e ) x = insert(e) x=insert(e) x x x 必为末端结点,不妨假设 x x x 的父亲 p = x → p a r e n t p=x→parent p=xparent 存在;如果不存在,就是简单的首次插入

    3. x x x 染红(除非它是根),如下图:
      【解释】因为这样做的话,现在可以保证树根结点还是黑色、外部结点依然是黑的、根结点通往外部结点的路径上黑结点的数目依然不变,但是这一步有可能导致两个红色结点成为父子,因为其父结点 p p p 颜色不确定。
      在这里插入图片描述
      如果此时父亲结点 p p p 为黑色,则插入成功,函数结束。否则两个红色结点连在了一起,称之为双红缺陷,需要调整。

    4. 如果出现了双红缺陷,需要通过后续介绍的调整处理,如下图:
      在这里插入图片描述
      【解释】:之所以把连接到红色结点的边标记为虚线,是因为后面需要将红色结点提升。

    5. 插入操作完成

    在这里插入图片描述

    下面,重点介绍插入中双红缺陷的处理办法:

    先分析一波:

    先考察 x x x 的祖父结点 g = p → p a r e n t g = p→parent g=pparent ,注意这里的祖父结点 g g g 一定是存在的,否则 p p p 不会为红色,并且祖父结点 g g g 一定为黑色。

    然后,我们还要考察 g g g 的另外一个孩子 u u u,相对于 x x x 而言。结点 u u u x x x 的叔父,当然,结点 u u u 的颜色也是不定的,我们要根据结点 u u u 的颜色分别处理。

    4.2 调整:双红缺陷

    4.2.1 双红缺陷1:叔父结点 u 是黑色

    此时, x x x, p p p, g g g 的四个子树的根(可能是外部结点)必定全部为黑,且黑高度相同,依据 x x x p p p 的左右关系,可以分为下面两种情况。
    在这里插入图片描述
    当然,依据 p p p g g g 的左右关系会产生和上图中对称的另外两种情况,但是原理是一样的,这里不再赘述。

    为了更好的研究这两种红色缺陷,我们将红色结点提升:
    在这里插入图片描述
    可以看到,我们结点“合并”之后,其所有的孩子,并没有出现超过4阶B-树上界的情况,唯一的缺点是“合并”以后的结点根结点是红色而不是黑色的,造成了两个红色相邻的违规现象。因此,从B-树的角度看,这种调整非常简明,我们并不需要调整B-树的拓扑结构,而仅仅需要对违规的关键字进行重新染色即可。

    对于处理 ( a ′ ) (a') (a) 中的情况,只需要交换 p p p g g g 的颜色即可。同理, ( b ′ ) (b') (b) 中的情况,只需要交换 x x x g g g 的颜色即可。

    我们刚刚这种角度实际上是将其用B-树的角度来处理双红缺陷,如果用这种方式处理的话,还要分情况讨论是 p p p 还是 x x x 去与 g g g 交换颜色,再结合尚未列出的两个镜像的情况,共4种不同的交换颜色的处理方式,分类讨论很麻烦。

    实际中真正处理叔父结点是黑色情况下的双红缺陷的办法

    在实际操作中,只要是出现了双红缺陷,并且 x x x 的叔父 u u u 是黑色,统一采用下面步骤处理双红缺陷

    (1)参考AVL树算法,做局部的重构,将结点 x x x p p p g g g 这三个结点以及它们下属的四棵子树找出来,这里可以结合图 ( a ) (a) (a),然后从 g g g 对这一局部开始中序遍历,获得一个中序遍历的有序序列: [ T 0 < a < T 1 < b < T 2 < c < T 3 ] [T_0<a<T_1<b<T_2<c<T_3] [T0<a<T1<b<T2<c<T3],从新构建排布方式:

    (2)直接将中间结点 b b b 染黑, a a a c c c 染红,如下图。
    在这里插入图片描述
    那么上面这个骚操作为什么行得通呢?如果放在B-树中又如何解释呢?

    首先,调整之前之所以非法,是因为在(2,4)-树中某个三叉结点中插入了红色的关键字形成了四叉结点,使得原来黑色的关键字不再居中,形成了RRBBRR,出现了相邻的红色关键字,也就是双红缺陷。

    而调整之后的效果相当于B-树的拓扑结构不变,但是在新的四叉结点中,三个关键字的颜色改为RBR
    在这里插入图片描述
    这个操作的时间复杂度是常数的。

    4.2.2 双红缺陷2:叔父结点 u 是红色

    在这里插入图片描述
    还是老方法,想要分析清楚红黑树,先转换为B-树,让所有红色结点提升,如下图:
    在这里插入图片描述
    可以看出,提升之后一个4阶B-树结点中出现了4个关键字,对应于5个分支,这种情况下红黑树的双红缺陷等价于B-树中的结点发生了上溢

    因此,与其说我们是在红黑树中修复双红缺陷,不如说我们在4阶B-树中修复上溢缺陷,这二者完全是一回事,见下图。
    在这里插入图片描述
    我们结合上图具体介绍一下叔父为红色的双红缺陷处理办法:

    (1)先将红色结点上升,得到如 ( b ′ ) (b') (b) 所示的效果

    (2)计算 s = ⌈ 4 2 ⌉ = 2 s = \lceil \frac{4}{2} \rceil = 2 s=24=2,我们将 [ k 0 , k 1 , k 2 , k 3 ] [k_0,k_1,k_2,k_3] [k0,k1,k2,k3] 中的 k s = k 2 k_s=k_2 ks=k2 上提到该上溢结点的父结点中,将 [ k 2 ] [k_2] [k2] 由黑色染成红色(相当于对上溢结点的父结点插入一个新的结点,所以要染成红色) ,同时将其原来的左右孩子染成黑色(因为红色结点的孩子都是黑色)即可。

    (3)我们说将 k 2 k_2 k2 染红并且上提看做作为新结点插入到上溢结点的父结点,因此上溢的结点的父结点有可能因为这个插入也发生双红缺陷。那么我们递归地再对该结点判断其叔父颜色,递归地执行对应颜色的双红结点的处理。最坏的情况下也只是会递归的处理到根结点,因此整个双红缺陷蔓延的过程迟早会终止。

    需要强调的一点是:尽管这一个调整过程,从B-树的角度来看,的确发生了拓扑结构的变化 。但是从红黑树的角度来看,除了相关结点的颜色发生了变化红黑树的拓扑连接关系并没有发生变化。因此,红黑树的重染色操作的次数可能会高达 O ( l o g h ) O(logh) O(logh),但是拓扑结构的变化依然控制在 O ( 1 ) O(1) O(1) 的范围内。

    5. 红黑树的删除

    相对于插入,红黑树的删除情况更多,也更为复杂一些。因此,我们更需要通过提升变换,将红黑树映射为B-树,并站在B-树的角度,翻过来理解红黑树的过程及原理。
    在这里插入图片描述

    1. 首先按照二叉搜索树的常规删除算法,删除指定的关键字 x x x r = r e o m v e A t ( x ) r=reomveAt(x) r=reomveAt(x)
      【解释】:这里指的是待删除结点 x x x 将由其孩子结点 r r r 替代(替代者 r r r 有可能就是一个实际不存在的外部结点),如下图(删除的结点 x x x 不一定必须是红色,下图只是举例)
      在这里插入图片描述
    2. 删除之后,红黑树的拓扑结构依然保持完整,但是红黑树的性质未必能继续满足,需要进行调整(非常类似AVL)。

    【解释】我们可以针对删除后红黑树的性质逐条分析:
    (1)首先红黑树的根和外部结点为黑色,这个性质并没有收到影响;

    (2)删除后在此局部有可能会出现两个红色结点相连的双红缺陷情况(假设之前 x x x 为黑, p 、 r p、r pr 为红),当然这种情况可以通过之前在插入里学的解决办法处理。

    (3)删除后在被删除结点 x x x 所在的通路上黑结点的数目(黑深度)却有可能发生变化

    下面,我们重点讲解如何对黑深度进行调整。

    5.1 调整:x 与 r 存在红结点

    对于(3)中有一种情况比较好处理,也就是被删结点 x x x 与其替代者 r r r 两者中有一个是红色的,如下图
    在这里插入图片描述
    对于这一类情况,直接将替代者 r r r 在替代完成后染为黑色即可,如下图。
    在这里插入图片描述
    为什么这么做可行呢?因为我们讲过,黑色指向红色的虚边,可以通过红结点提升来“合并”,对于红黑树的黑高度是没有影响的。因此删除后将 r r r 置为黑色,可以等价在原树中删除了一条虚边,所以所有外部结点的黑高度将依然保持原状。

    5.2 调整:双黑缺陷

    然而,遗憾的是有可能被删除的结点 x x x 以及他的替代者 r r r 在删除前都是黑色结点,这种情况我们也称为双黑缺陷
    在这里插入图片描述
    如上图,如果真的删除了 x x x,用黑色的 r r r 代替,则必然会丢失一个黑深度,全树的黑深度不再统一,破坏了红黑树的规则。我们不妨换一个角度,用B-树的视角看看,问题究竟出在哪?

    因为 x x x r r r 都是黑色的,那么对应的4阶B-树中 x x x 将独立的成为一个结点,在唯一的这个关键字被删除之后,该结点也就自然发生了下溢。因此我们后面的调整算法与其说是修复“双黑缺陷”,不如说是修复B-树的下溢。

    因此,只需借助B-树的下溢修复算法,即可得到对应的红黑树双黑修复算法。

    5.2.1 双黑缺陷-1

    我们知道,发生了下溢时,第一件事情就是下溢结点左顾右盼,看看兄弟结点能否借一个结点过来。

    因此,对应双黑缺陷-1的情况就是: x x x 相邻的左右兄弟结点 s s s 为黑,且至少拥有一个红孩子 t t t(这里很好理解,有了红孩子就可以上提和 s s s 合并,那么 x x x 的左兄弟就相当于能借一个盈余结点出来,如果遗忘的话请回顾B-树的操作)

    经过旋转之后,红黑树调整的结果如右图,现在将右图中的 t , s , p t,s,p t,s,p 分别重命名为 a , b , c a,b,c a,b,c r r r 保持黑色, a , c a,c a,c 染黑, b b b 继承 p p p 的颜色,因为 s s s 继承了原来 p p p 的颜色,因此新的局部结构也不会对红黑树的其他部分造成影响。
    在这里插入图片描述
    现在回过头来,我们发现这种情况还是比较简单的,因为 s s s 作为兄弟结点起码还有一个红孩子,足够富有,能够提供旋转解决下溢的条件。那么可想而知,后面更困难的情况就是 p p p 的左右孩子都是黑色,我们将继续讨论。

    5.2.2 双黑缺陷-2R

    双黑缺陷-2的情况就是: x x x 相邻的左右兄弟结点 s s s 为黑,且两个孩子均为黑。但是这里还需要根据 s s s x x x 的父结点 p p p 的颜色进行分类讨论,而双黑缺陷-2R就是双黑缺陷-2中, p p p 为红色的情况
    在这里插入图片描述
    老规矩,先将红色结点 p p p 上提,转换为B-树,然后因为被删除的结点左子树不够借,无法进行旋转修复,因此通过让 p p p 下来合并,注意这里 s s s p p p 要交换颜色,最后恢复成变换后的红黑树。

    那么这里有的小伙伴就会问了,因为原来B-树中 p p p 结点所在的结点因为下层合并借走了一个关键字,是否会因此造成原结点下溢呢?事实上是不会的,因为既然 p p p 是红色的,那么 p p p 的父结点一定是黑色的,故即使 p p p 被下面合并借走了以后也不会发生下溢。

    这也是为什么我们要把 p p p 的颜色单独拎出来分类的原因。

    5.2.3 双黑缺陷-2B

    双黑缺陷-2R就是双黑缺陷-2中, x x x 相邻的左右兄弟结点 s s s 为黑,且两个孩子均为黑 p p p 为黑色的情况
    在这里插入图片描述
    整个流程和双黑缺陷-2R处理过程非常类似,只是当 p p p 因为要解决下层下溢问题,被从原结点借出之后,原结点一定会下溢。故下层的下溢会引发上层的下溢。这种传播最多可以达到 l o g h log h logh 次。但是,我们可以惊奇的发现,即使传播了 l o g h log h logh 次,每一次从红黑树的角度仅仅变换了 s s s 结点的颜色。

    因此,双黑缺陷-2B的解决策略在拓扑结构的改变上依然是 O ( 1 ) O(1) O(1) 的,是非常高效的。

    那么,之前我们讨论的双黑缺陷问题时,都是讨论在 s s s 为黑色结点的前提下的调整办法,那么当 s s s 为红色将如何处理呢?

    5.2.4 双黑缺陷-3

    双黑缺陷-3是指: x , r x,r x,r 为黑 s s s 为红的情况
    在这里插入图片描述

    实际上,对于这种情况我们并不需要做什么实质性的处理,而只需要将其转化为此前我们所介绍的某两种子情况,为此,我们必须还要站在对应B-树的角度分析问题,如下图。
    在这里插入图片描述

    首先,依然是红色结点上提,转换为B-树视角。因为是同一个结点之内,我们不妨直接上 s s s p p p 互换颜色,而堆B-树无需做任何的结构调整。当然,当恢复到对应的红黑树之后,却需要做一次拓扑结构的调整,因为原来 s s s 的父亲指向 p p p,现在 p p p 的父亲指向 s s s,也就是相当于在红黑树中围绕着结点 p p p做一次AVL树中的右旋操作同时互换 s s s p p p 的颜色

    即使经过了上述处理,你可能有些失望,因为现在仍然没有解决黑高度变化问题。但是,我们可以发现,现在待删除结点 x x x 的兄弟 s ′ s' s 已经变为了黑色, x x x 的父结点已经变为了红色,于是我们就可以跳出双黑缺陷-3这种情况,而转入之前所讨论的情况。更具体一点,只会转入时间复杂度相对更小的双黑缺陷-1双黑缺陷-2R这两种情况。

    因此,我们可以断定,经过如此调整之后,红黑树的性质必然全局恢复。

    展开全文
  • 红黑树原理详解

    2020-08-04 17:19:58
    STL源码剖析—红黑树原理详解上 https://blog.csdn.net/Hackbuteer1/article/details/7740956 1、黑父 如下图所示,如果新节点的父结点为黑色结点,那么插入一个红点将不会影响红黑树的平衡,此时插入操作完成。红黑...

    参考:
    教你初步了解红黑树
    红黑树(一)之 原理和算法详细介绍

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

    如下图,是一颗简单的红黑树。其中Nil为叶子结点,并且它是黑色的
    在这里插入图片描述

    黑高度
    从某个节点x出发(不包含该该节点)到达一个叶子节点的任意一条路径上,黑色节点的个数称为该节点x的黑高度,用bh(x)表示。从该结点出发的所有下降路径都具有相同的黑节点个数。
    红黑树黑高度的定义为其根节点的黑高度。

    性质
    一棵含有n个内节点的红黑树的高度至多为2log(n+1).
    即,包含n内结点的红黑树是高度为O(lgn)的查找树,简单操作的运行时间为O(lgn)。

    证明
    首先定义一个节点x的黑高为 b h ( x ) bh(x) bh(x),表示从x到任意一个叶子节点路径上黑色节点的个数(不包括x)。

    1.第一步,先证明以某一节点x为根的子树中至少包含 2 b h ( x ) − 1 2^{bh(x)}−1 2bh(x)1个内节点(不是叶子的都是内节点)。用数学归纳法证明。
    如果x的高度为0,那么x是叶节点,包含0个内节点,满足该式子。
    对于高度为正值的x,其两个孩子至少包含 2 b h ( x ) − 1 − 1 2^{bh(x)−1}−1 2bh(x)11个内节点,
    所以以x为根的子树至少包含 ( 2 b h ( x ) − 1 − 1 ) + ( 2 b h ( x ) − 1 − 1 ) + 1 = 2 b h ( x ) − 1 (2^{bh(x)−1}−1)+(2^{bh(x)−1}−1)+1=2^{bh(x)}−1 (2bh(x)11)+(2bh(x)11)+1=2bh(x)1个内节点。

    2.第二步,对于一棵高度为h的树,任意一条从根到叶节点(不包括根)的路径上至少有一半黑色节点,从而 b h ( x ) ≥ h / 2 bh(x)≥h/2 bh(x)h/2,所以 n ≥ 2 b h ( x ) − 1 ≥ 2 h / 2 − 1 n≥2^{bh(x)}−1≥2^{h/2}−1 n2bh(x)12h/21,即 h ≤ 2 l o g ( n + 1 ) h≤2log(n+1) h2log(n+1)

    红黑树的旋转

    直接看这里
    https://www.cnblogs.com/skywang12345/p/3245399.html

    红黑树上结点的插入

    STL源码剖析—红黑树原理详解上

    1、黑父
    如下图所示,如果新节点的父结点为黑色结点,那么插入一个红点将不会影响红黑树的平衡,此时插入操作完成。红黑树比AVL树优秀的地方之一在于黑父的情况比较常见,从而使红黑树需要旋转的几率相对AVL树来说会少一些。
    在这里插入图片描述

    2、红父
    如果新节点的父结点为红色,这时就需要进行一系列操作以保证整棵树红黑性质。如下图所示,由于父结点为红色,此时可以判定,祖父结点必定为黑色。这时需要根据叔父结点的颜色来决定做什么样的操作。青色结点表示颜色未知。由于有可能需要根结点到新点的路径上进行多次旋转操作,而每次进行不平衡判断的起始点(我们可将其视为新点)都不一样。所以我们在此使用一个蓝色箭头指向这个起始点,并称之为判定点。
    在这里插入图片描述

    2.1 红叔
    当叔父结点为红色时,如下图所示,无需进行旋转操作,只要将父和叔结点变为黑色,将祖父结点变为红色即可。但由于祖父结点的父结点有可能为红色,从而违反红黑树性质。此时必须将祖父结点作为新的判定点继续向上(迭代)进行平衡操作

    这种称为LLr型,(表示祖父的左孩子L的左孩子L,同时叔叔是红色r),下面名称可以类比。
    在这里插入图片描述
    需要注意的是,无论“父节点”在“叔节点”的左边还是右边,无论“新节点”是“父节点”的左孩子还是右孩子,它们的操作都是完全一样的(其实这种情况包括4种,只需调整颜色,不需要旋转树形)。

    其实还有LRr型(在父节点处左旋则可得到LLr型),不要讨论了。
    RLr型(与LRr型对称),RRr型(与LLr对称),这两种对称情况也不用讨论了。

    2.2 黑叔
    当叔父结点为黑色时,需要进行旋转,以下图示了所有的旋转可能:
    Case 1: LLb型
    在这里插入图片描述

    Case 2: LRb型
    在这里插入图片描述

    Case 3: RLb型(与LRb型对称)
    在这里插入图片描述

    Case 4: RRb型与LLb型对称)
    在这里插入图片描述

    可以观察到,当旋转完成后,新的旋转根全部为黑色,此时不需要再向上回溯进行平衡操作,插入操作完成。需要注意,上面四张图的“叔”、“1”、“2”、“3”结点有可能为黑哨兵结点。

    红黑树上结点的删除

    STL源码剖析—红黑树原理详解下

    第一步:将红黑树当作一颗二叉查找树,将节点删除。

    我们先回忆一下前驱节点和后继节点的定义

    前驱节点:二叉树中序遍历完成后和这个节点相邻的前面的节点为该节点的前驱节点
    后继节点:二叉树中序遍历完成后和这个节点相邻的后面的节点为该节点的后继节点

    再看看普通二叉树的节点删除方法:

    Z指向需要删除的节点,Y指向实质结构上被删除的结点,

    ① 被删除节点没有儿子,即为叶节点。那么,直接将该节点删除就OK了。即Y指向Z。

    ② 被删除节点只有一个儿子。那么,直接删除该节点,并用该节点的唯一子节点顶替它的位置。即Y指向Z。

    ③ 被删除节点有两个儿子。那么,先找出它的后继节点;然后把“它的后继节点的内容”复制给“该节点的内容”;之后,删除“它的后继节点”。即Y指向Z的后继节点。

    在这里,后继节点相当于替身,在将后继节点的内容复制给"被删除节点"之后,再将后继节点删除。这样就巧妙的将问题转换为"删除后继节点"的情况了,下面就考虑后继节点。 在"被删除节点"有两个非空子节点的情况下,它的后继节点不可能是双子非空。既然"的后继节点"不可能双子都非空,就意味着"该节点的后继节点"要么没有儿子,要么只有一个儿子。若没有儿子,则按"情况① "进行处理;若只有一个儿子,则按"情况② "进行处理。

    下面是一份在二叉搜索树中删除一个节点的代码示例

    /***************************************
    * 在BST中删除一个节点
    * 先找到要删除的结点,假设为A,A要分三种情况
    *  1.A两个子结点为NULL,则直接删除A
    *  2.A只有一个非空子结点,
    *  3.A有两个子非空结点,
    *****************************************/
    Node* getMaxOfLeftTree(Node* leftRoot) {
    	if (leftRoot == NULL)
    		return NULL;
    	while (leftRoot->right)
    		leftRoot = leftRoot->right;
    	return leftRoot;
    }
    Node* getMinOfRightTree(Node* rightRoot) {
    	while (rightRoot->left != NULL)
    		rightRoot = rightRoot->left;
    	return rightRoot;
    }
    
    Node* deleteNode(Node* root, int key) {
    	if (root == NULL)
    		return NULL;//
    
    	if (root->data == key)//左子树的最大结点或右子树的最小结点
    	{
    		//情况1
    		if (root->left == NULL && root->right == NULL) {
    			delete root;
    			return NULL;
    		}			
    		//排除情况1后,情况2
    		//只有右结点
    		if (root->left == NULL) {
    			Node* temp = root->right;
    			delete root;
    			return temp;
    		}	
    		//只有左结点
    		if(root->right==NULL) {
    			Node* temp = root->left;
    			delete root;
    			return temp;
    		}
    		//情况3
    		Node* minNode = getMinOfRightTree(root->right);
    		root->data = minNode->data;
    		//很重要,这里是递归删除,为什么不能直接删除这个右子树的最小/左结点
    		//因为这个右子树的最小/左节点可能有一个右结点,所以不能直接删除
    		root->right = deleteNode(root->right, minNode->data);
    	}
    	else if (root->data < key)
    		root->right=deleteNode(root->right, key);
    	else if (root->data > key)
    		root->left=deleteNode(root->left, key);
    
    	return root;
    }
    
    

    第二步:通过"旋转和重新着色"等一系列来修正该树,使之重新成为一棵红黑树。

    因为"第一步"中删除节点之后,可能会违背红黑树的特性。所以需要通过"旋转和重新着色"来修正该树,使之重新成为一棵红黑树。

    再看一下红黑树的几个特性:

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

    1.如果Y指向的节点是个红色节点,那么直接删除掉Y以后,红黑性质不会被破坏。操作结束。

    2.如果Y指向的节点是个黑色节点,那么就有几条红黑性质可能受到破坏了。
    首先是包含Y节点的所有路径,黑高度都减少了一(第5条被破坏)。

    其次,如果Y有红色子节点,Y又有红色的父节点,那么Y被删除后,就出现了两个相邻的红色节点(第4条被破坏)。

    最后,如果Y指向的是根节点,而Y的子节点又是红色的,那么Y被删除后,根节点就变成红色的了(第2条被破坏)。

    其中,第5条被破坏是让我们比较难受的。因为这影响到了全局。这样动作就太大太复杂了。而且在这个条件下,进行其它红黑性质的恢复也很困难。

    所以我们首先解决这个问题:如果不改变含Y路径的黑高度,那么树的其它部分的黑高度就必须做出相应的变化来适应它。所以,我们想办法恢复原来含Y节点的路径的黑高度。做法就是:无条件的把Y节点的黑色,推到它的子节点X上去。(X可能是NIL节点)。这样,X就可能具有双重黑色,或同时具有红黑两色,也就是第1条性质被破坏了

    但第1条性质是比较容易恢复的:
    一、如果X是同时具有红黑两色,那么好办,直接把X涂成黑色,就行了。而且这样把所有问题都解决了。因为将X变为黑色,2、4两条如果有问题的话也会得到恢复,算法结束。

    二、如果X是双黑色,那么我们希望把这种情况向上推一直推到根节点(调整树结构和颜色,X的指向新的双黑色节点,X不断向上移动),让根节点具双黑色,这时,直接把X的一层黑色去掉就行了(因为根节点被包含在所有的路径上,所以这样做所有路径同时黑高减少一,不会破坏红黑特征)。
    具体可以概括为3种情况。
    ① 情况说明:x是“红+黑”节点。
    处理方法:直接把x设为黑色,结束。此时红黑树性质全部恢复。

    ② 情况说明:x是“黑+黑”节点,且x是根。
    处理方法:什么都不做,结束。此时红黑树性质全部恢复。

    ③ 情况说明:x是“黑+黑”节点,且x不是根。

    在③的情况下,X节点是双层黑色,且X有父节点P(X不是根,所以必定有父亲)。同时,X必然有兄弟节点W,而且这个W节点必定有两个子节点。(因为这是原树满足红黑条件要求而自然具备的。X为双黑色,那么P的另一个子节点以下一定要有至少两层的节点,否则黑色高度不可能和X路径一致)
    所以我们就分析这些节点之间如何变形,把问题限制在比较小的范围内解决。

    另一个前提是:X在一开始,肯定是树底的叶节点或是NIL节点,所以在递归向上的过程中,每一步都保证下一步进行时,至少 X的子树是满足红黑特性的。
    因此子树的情况就可以认为是已经正确的了,

    这样,分析就只限制在X节点,X的父节点P和X的兄弟节点W,以及W的两个子节点。这些个节点中

    在X具有双重黑色的情况下,算法的过程就是将这多出的一重黑色向上移动,直到遇到红节点或者根节点。

    接着往下分析, 会遇到4种情况,实际上是8种, 因为其中4种是相互对称的,这可以通过判断X是其父节点的右孩子还是左孩子来区分。

    下面我们以X是其父节点的左孩子的情况来分析这4种情况,实际上接下来的调整过程,就是要想方设法将经过X的所有路径上的黑色节点个数增加1

    具体分为以下四种情况:(下面针对x是左儿子的情况讨论,右儿子对称)

    Case1:X的兄弟W是红色(想办法将其变为黑色)
    由于W是红色的,因此其儿子节点和父节点必为黑色,只要将W和其父节点的颜色对换,在对父节点进行一次左旋转,便将W的左子节点放到了X的兄弟节点上,X的兄弟节点变成了黑色,且红黑性质不变。但还不算完,只是暂时将情况1转变成了下面的情况2或3或4。

    在这里插入图片描述

    Case2:X的兄弟节点W是黑色的,而且W的两个子节点都是黑色的,此时可以将X的一重黑色和W的黑色同时去掉,而转加给他们的父节点上,这时X就指向它的父节点了,因此此时父节点具有双重颜色了。这一重黑色节点上移。
    在这里插入图片描述
    如果父节点原来是红色的,现在又加一层黑色,那么X现在指向的这个节点就是红+黑两色的,直接把X(也就是父节点)着为黑色。问题就已经完整解决了。

    如果父节点现在是双层黑色,那就以父节点为新的X进行向上的下一次的递归。

    Case3:X的兄弟节点W是黑色的,而且W的左子节点是红色的,右子节点是黑色的
    此时通过交换W和其左子节点的颜色并进行一次向右旋转就可转换成下面的第四种情况。注意,原来L是红色的,所以L的子节点一定是黑色的,所以旋转中L节点的一个子树挂到之后着色为红色的W节点上不会破坏红黑性质。变形后黑色高度不变。

    在这里插入图片描述
    Case4:X的兄弟节点W是黑色的,而且W的右子节点是红色的。
    这种情况下,做一次左旋,W就处于X父亲A的位置,将W保持为原来的A的位置的颜色,同时将W的两个新的儿子节点的颜色变为黑色,去掉X的一重黑色。这样整个问题也就得到了解决。递归结束。(在代码上,为了标识递归结束,我们把X指向根节点)

    在这里插入图片描述
    因此,只要按上面四种情况一直递归处理下去,X最终总会指向根结点或一个红色结点,这时我们就可以结束递归并把问题解决了。

    4种情况总结如下表

    现象说明处理策略
    Case 1X是"黑+黑"节点,X的兄弟节点W是红色。(01) 将X的兄弟节点W设为“黑色”。
    (此时X的父节点和X的兄弟节点W的子节点都是黑节点)(02) 将X的父节点设为“红色”。
    (03) 对X的父节点进行左旋
    (04) 左旋后,重新设置X的兄弟节点W
    Case 2x是“黑+黑”节点,x的兄弟节点是黑色,x的兄弟节点的两个孩子都是黑色(01) 将X的一重黑色和其兄弟节点W的黑色同时去掉,而转加给他们的父节点上,此时父节点具有双重颜色了
    (02) 设置“X的父节点”为“新的X节点”。
    Case 3X是“黑+黑”节点,X的兄弟节点W是黑色;X的兄弟节点W的左孩子是红色,右孩子是黑色的。(01) 将X兄弟节点W的左孩子设为“黑色”。
    (02) 将X兄弟节点W设为“红色”。
    (03) 对X的兄弟节点W进行右旋。
    (04) 右旋后,重新设置X的兄弟节点W。
    Case 4X是“黑+黑”节点,x的兄弟节点W是黑色;X的兄弟节点W的右孩子是红色的,X的兄弟节点W的左孩子任意颜色。(01) 将X父节点颜色赋值给X的兄弟节点W(即,将W保持为原来X的父亲的颜色)。
    (02) 将X父节点设为“黑色”。
    (03) 将X兄弟节点W的右子节设为“黑色”。
    (04) 对X的父节点进行左旋。
    (05) 设置“X”为“根节点”(这里是为了标识递归结束)。

    代码就不贴了,具体的可以看看上面的几篇参考博文。

    展开全文
  • 红黑树原理详解及golang实现 文章目录红黑树原理详解及golang实现二叉查找树性质红黑树性质operation红黑树的插入`情形1`:空树`情形2`:插入节点父节为黑色,`情形3` 插入节点的父节点为红色,父节点为父父节点的...
  • 今天我们要说的红黑树就是就是一棵非严格均衡的二叉树,均衡二叉树又是在二叉搜索树的基础上增加了自动维持平衡的性质,插入、搜索、删除的效率都比较高。红黑树也是实现 TreeMap 存储结构的基石。 文章相关视频...
  • 红黑树图文详解

    多人点赞 2019-05-05 21:35:49
    什么是红黑树? ———————————— 二叉查找树(BST)具备什么特性呢? 1.左子树上所有结点的值均小于或等于它的根结点的值。 2.右子树上所有结点的值均大于或等于它的根...
  • 红黑树 删除调整步骤终极详解

    千次阅读 2019-01-14 17:16:46
    红黑树删除无疑是最难的,抛开调整,红黑树的插入删除都跟选择二叉树一样,所以前面的步骤网上很多了,在这里只讲如何调整,以满足红黑树性质。  还是从头到尾理一下吧...  先定义一下,删除节点为d,真实删除...
  • 前面我们讨论了红黑树的插入的实现,基本思想是分类讨论;然后分情况讨论以后我们发现插入操作调整函数只需要处理三种情况,并不是太复杂。但是删除操作会更复杂一点...下面先放出红黑树删除函数的代码://红黑树删除
  • 算法导论红黑树删除详解

    千次阅读 2012-08-29 18:51:07
    红黑树删除代码就不写了,细节太多了,说说自己对删除的了解算了。 这里不贴代码了,跟着算法导论的伪代码基本写的出来,唯一一点不好的就是,这里要考虑很多细节,叶子节点,根节点的父节点。 我们假设是在红黑...
  • 红黑树详解

    2015-11-01 02:08:29
    1.红黑树的由来 2.红黑树的性质 3.红黑树的插入和修复 4.红黑树删除和修复
  • 一,红黑树的性质 红黑树也是一种自平衡的二叉搜索树 红黑树必须满足如下五条性质 (1)节点是 RED 或者 BLACk (2)根节点是 BLACK (3)叶子节点都是 BLACK (4)RED 节点的子节点是 BLACK (5)从任一节点到叶子...
  • 文章目录红黑树删除平衡说明删除结点删除后平衡 红黑树删除平衡说明 在描述之前先做一些定义:待删除结点是x,父节点是p,兄弟结点是s,兄弟结点左子节点是sl,兄弟结点右子节点是sr。 先说结论,待删除结点最后只会...
  • 红黑树操作详解

    2014-04-14 15:45:53
    红黑树插入和删除结点的全程演示 作者:July、saturnman。 时间:二零一一年三月二十八日。 出处:http://blog.csdn.net/v_JULY_v。 声明:版权所有,侵权必究。 ----------------------------------- 引言...
  • 找了很多其他人的,红黑树的插入大部分都能理解,在删除部分有些博客很难理解进行,就自己写了一篇详细的,有问题欢迎请指出。 作为一种广泛应用的平衡二叉搜索树之一,需要我们有些清晰的了解 红黑树的结点增删改查...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,944
精华内容 3,177
关键字:

红黑树删除详解