红黑树<三>

　　前面两部分终于把基础概念和插入学习完了，下面就是红黑树里最复杂的结点删除了。难啃的骨头慢慢啃，我们开始吧！


　　一提到删除，再结合前面我们对红黑树和搜索二叉树的基本了解，我们马上可以想到这几种情况：

１.没有子结点，即左右子结点均为空结点（NIL）。
２.只有一个子结点，即另一个子结点为空结点（NIL）。
３.两个子结点均不为空结点（NIL）。

　　有了插入结点的经验，我们可以类比，也就是说我们应该先考虑恢复搜索二叉树的性质。情况1，很简单，只要把该结点删除，并将其父结点指向它的指针置空即可。情况2也不复杂，删除该结点，把该结点父结点指向其的指针指向其唯一儿子即可。情况3是其中较为复杂的情况，因为我们需要先找到该结点的前驱（比其小的最大结点）/后继（比其大的最小结点），然后让它来代替被删除的结点。其实，寻找前驱/后继结点非常简单，前驱就是该结点左子中一直沿右子下降的最后一个非空结点，同理，后继是该结点右子一直沿左子下降的最后一个非空结点。
　　仅仅完成删除和保持搜索二叉树的性质对于红黑树明显是不够的，我们还必须强调红黑树的五个特性（这是红黑树的根本）：

1）每个结点要么是红的，要么是黑的。
2）根结点是黑的。
3）每个叶结点，即空结点（NIL）是黑的。
4）如果一个结点是红的，那么它的俩个儿子都是黑的。
5）对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。

　　其中的每个特性都提到结点的颜色，连名字里也有“红黑”二字，可见结点颜色对于该数据结构的重要性，所以我们肯定要记下删除结点的颜色并对症下药。
　　首先，我们考虑删去的是红色结点，对于情况1和2肯定不会破坏任何一个性质。针对情况2简单解释一下，1、2、3，4由于该结点是红，那么它的子结点和父结点肯定都不是红色，否则一开始就违背4，所以删去该结点并用其孩子代替肯定也不会违背。关于5，由于删去的红色结点对于该分支上的黑色结点没有影响，所以也不会违背5。情况3就要稍微复杂一些了，因为我们需要删去该结点并用其前驱/后继代替。我们可以这样来考虑：把该结点替换成其前驱/后继的时候不改变其颜色，则最终失去的结点颜色就是前驱/后继结点原来的颜色。现在考虑它是红色，然后根据前驱/后继结点的定义，可以看到这和情况1是一样的，所以也是不会破坏性质的。综上就是，删去一个红色的结点是不会影响红黑树的性质的。
　　考虑完了红色，剩下的就是黑色了。情况1删去黑色结点，很明显会影响性质5；情况2同样影响性质5，如果代替本身的子结点和其父结点都为红色还会影响性质4，在本身是根结点和子结点是红色的情况下还会影响性质2；情况3同样像上面那样考虑失去的结点的话，很明显也是会影响性质5的。可见我们在删除黑色结点的时候就需要维护该数据结构的性质了。下面给出删除操作的伪代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
RB-DELETE(T,z)
	y = z                                    //y指示失去结点（包括直接删去，或者被移动来填补空缺）
	y-original-color = y.color               //y-original-color用来记录失去的结点颜色
	if z.left == T.NIL                       //处理z的一侧孩子为空或者均为空的情况
		x = z.right
		RB-TRANSPLANT(T,z,z.right)
	elseif z.right == T.NIL
		x = z.left
		RB-TRANSPLANT(T,z,z.left)
	else y = TREE-MINIMUM(Z.right)           //若z的两侧孩子均不为空，就需要用前驱/后继替换，此处用的是后继  
		y-original-color = y.color
		x = y.right
		if y.p != z                          //y不为z的孩子，则需要用右子替换y（y为后继则y无左孩子），并设置y.right
			RB-TRANSPLANT(T,y,y.right)
			y.right = z.right
			z.right.p = y
		RB-TRANSPLANT(T,z,y)                 //y在通用情况下，替换z并设置左侧孩子。y总没有左孩子，可统一设置
		y.left = z.left
		y.left.p = y
		y.color = z.color
	if y-original-color == BLACK
		RB-DELETE-FIXUP(T,x)
1
2
3
4
5
6
7
RB-TRANSPLANT(T,u,v)
	if u.p = T.NIl
		T.root = v
	elseif u == u.p.left
		u.p.left = v
	else u.p.right = v
		v.p = u.p

　　第一段伪代码类似红黑树的插入伪代码，基础的都是搜索二叉树的相关代码，只是在最后加入一段修复代码，而且根据我们的分析也很好理解，是在判断到删去黑色结点之后再调用修复函数。这里需要注意的是，我们使用后继来代替被删除的结点，寻找后继的方法是：在右孩子里，一直沿左子树向下找，直到结点的子结点都为空；前驱也提一下，在左孩子里，一直沿右子树向下找，直到结点的子结点都为空。第二段短小的代码就更好理解了，就是将原本的u结点替换为v结点，但是只是对删去结点的父结点进行了相关设置，并没有修改被移动节点的父子结点，这都需要我们自己来考虑。
　　最后，最困难的问题出现了，如何修复？在上文已经分析了各种情况出现的性质破坏，我们可以看到，每一种情况都破坏了性质5，并且y（失去的结点）的任何先祖都会不满足性质5。我们的想法是，将出现在原来y结点位置的x结点视为还有一重黑色，在这样的假设下，y的先祖就都恢复了性质5。现在x结点就是黑黑色或红黑色，但是这并不写在x结点的color属性里，我们只是这样来理解x结点，并不实质反应到属性上。
　　还是从简单的开始，如果x结点是红黑色的，也就是说x结点以前是红色的。以前是红色的，现在变成红黑色，破坏了性质1，现在我们单纯的把它变为黑色，修复了性质1，而且也没有多的性质被破坏，因为黑色不会出现性质4的冲突，而5也不会因为去掉红色被破坏，就是这么简单。剩下的黑黑色就没这么简单了，我们逐一来研究。

　　情况1：x的兄弟结点w是红色的
　　注：下面图片中x结点左侧会标注N
　　　　　　　　　　情况1变换前
　　上图就是符合我们情况1的。此时，我们只需要以x.p为pivot左旋，然后交换x.p和w的颜色即可。下面是处理后的图：
　　　　　　　　　　情况1变换后
　　上图是变换后的情况，可见该局部的性质都没有破坏，同时需要注意的是，x结点的兄弟结点变了。

　　情况2：x的兄弟结点w是黑色的，而且w的两个子结点都是黑色的
　　　　　　　　　　情况2变换前
　　上图就是符合我们情况2的。此时，我们只需要将x的兄弟改为红色，然后把x的黑黑色去掉一个黑色，将此黑色转移到x.p上，同时把x.p设置为新的x结点。这样的话，应该根据新的x的color属性继续调整。
　　　　　　　　　　情况2变换后
　　上图是变换后的情况，新的x结点是原结点上爬一层的结果，而且重新进入循环处理。

　　情况3：x的兄弟结点w是黑色的，而且w的左孩子是红色的，w的右孩子是黑色的
　　　　　　　　　　情况3变换前
　　上图就是符合我们情况3的。我们先交换x的兄弟和其左孩子的颜色，然后以x的兄弟为pivot右旋。此时，该局部的特性没有被破环，而且情况3经过处理后就变成了情况4。下面就是转换后的示意图：
　　　　　　　　　　情况3变换后

　　情况4：x的兄弟结点w是黑色的，而且w的右孩子是红色的
　　　　　　　　　　情况4变换前
　　上图就是符合我们情况4的。我们首先交换x.p和x的兄弟的颜色，接着把x的兄弟的右子涂黑，再以x.p为pivot左旋，这样就可以去掉x的另一重黑色，并且没有改变该局部的特性。下面调整后的图案：
　　　　　　　　　　情况4变换后
　　此情况中，我们需要注意的是，变化前的x.p结点其实可以是任意的颜色，同时对于x的兄弟结点我们也不限制其色彩，而无论它们是什么颜色在执行了上述的变化之后，都符合红黑树的特性。此情况修复结束后，x应被设置为T.root。

　　通过上面细致的分析，伪代码相信一定没有难度了，下面就是上述论述的伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
RB-DELETE-FIXUP(T, x) 
	while x != T.root and x.color = BLACK               //只在黑黑色和不为根节点时进入循环  
	    if x == x.p.left   
	        w = x.p.right    
	        if w.color = RED                            //兄弟结点为红色，情况1
	            w.color = BLACK                             
	            x.p.color = RED                             
	            LEFT-ROTATE(T, x.p)                         
	            w = x.p.right                             
	        if w.left.color == BLACK and w.right.color == BLACK    //兄弟结点的两个儿子都是黑色的
	            w.color = RED                              
	            x = x.p                                 
	        elseif w.right.color == BLACK    
	            w.left.color = BLACK            //Case 3    
	            w.color = RED                    //Case 3    
	            RIGHT-ROTATE(T, w)               // Case 3    
	            w = x.p.right                   //Case 3    
	            w.color = x.p.color                  //Case 4    
	            x.p.color = BLACK                    //Case 4    
	            w.right.color = BLACK                //Case 4    
	            LEFT-ROTATE(T, x.p)                  //Case 4    
	            x = T.root                           //Case 4    
	    else (此时x=x.p.right，和上面情况类似)    
	x.color = BLACK  //此时循环终止，x为T.root或者x.color=RED（红黑色），都应该将其设置为黑色保持性质

　　RB-DELETE的运算时间如何？首先，不调用修正函数时，最复杂的就是寻找后继，逐层下降也就是O（lgn）的时间复杂度。调用FIXUP时，情况1变换为后三种，情况2会向上爬升，而情况3变为4，4就终结了，而且每一种情况进行的颜色交换和旋转都是有限次数，所以肯定也不会超过O（lgn）。综上，DELETE函数运行总时间为O（lgn）。可见，红黑树的插入和删除操作都是O（lgn）的复杂度，很好的解释了其优良的性质。

上述的内容参考了http://blog.csdn.net/v_JULY_v/article/details/6105630

版权：本文采用以下协议进行授权，自由转载 - 非商用 - 非衍生 - 保持署名 | Creative Commons BY-NC-ND 3.0，转载请注明作者及出处。