红黑树<二>

　　在<一>中，我们已经阐释了红黑树的基本概念和特性，明白了其在基本操作上能始终保持O(lgn)的复杂度，都归功于在操作的同时能维持其红黑树的特性。我们还提到了红黑树的旋转，它是在对红黑树进行了修改之后进行特性维持的关键步骤。那么下面我们就要来看看对红黑树进行了插入与删除之后，具体如何维持红黑树的特性。

红黑树的插入

　　从<一>中我们可以看到，红黑树是在查找二叉树的基础上改进来的，所以红黑树的插入操作也应该可以从查找二叉树相应的操作上获取灵感。那么，我们下面就先来看看查找二叉树如何来插入结点。
　　查找二叉树不是本文的重点，其特性在<一>中有提及，在此恕不赘述。我们先贴出其插入操作的伪代码，然后再来详细解释。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
TREE-INSERT(T, z)  
	y ← NIL  
	x ← T.root               
	while x ≠ NIL           
    	y ←  x   
    	if z.key < x.key  
        	x ← x.left  
    	else x ← x.right  
	z.p ← y  
	if y == NIL  
    	T.root ← z         
	elseif z.key < y.key  
    	y.left ← z  
	else y.right ← z

　　该方法的核心是，利用x记录现在操作的结点，y记录上一步的结点。循环中是不断在树形结构中步进寻找合适插入结点的叶结点位置，具体的要求就是大于该结点沿着右向下，小于该结点就沿左向下，然后把z结点和其父结点y的指针设置合适的值。
　　通过上面对查找二叉树的插入操作的了解，我们已经有了一个初步的认识，接下来要学习的红黑树的插入操作，只要在上述操作的基础上再加上恢复红黑树的特性的操作。我们来看伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
RB-INSERT(T, z)  
	y ← NIL  
	x ← T.root  
	while x ≠ T.NIL  
    	y ← x  
    	if z.key < x.key  
        	x ← x.left  
    	else x ← x.right  
	z.p ← y  
	if y == nil[T]  
    	T.root ← z  
	elseif z.key < y.key  
    	y.left ← z  
	else y.right ← z  
	z.left ← T.NIL  
	z.right ← T.NIL  
	z.color ← RED  
	RB-INSERT-FIXUP(T, z)

　　在这段代码的尾部，我们将插入结点的左右孩子都设置为空，并把结点颜色设置为红色。最后添加一个修复函数，但是，我们从上面这段代码里是看不出做了哪些修复操作的。我们在写这个函数之前，先来看看我们插入的这个结点会对该树造成哪些影响。首先，我们分析一下为什么要把新插入的结点设置为红色。
　　在此之前，我们还是要强调一下红黑树的特性：

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

然后，我们看到，当我们插入红色结点时，可能受影响的是（2）、（4）。性质（2）比较好处理，只要判断插入结点的父节点是否为空即可；性质（4）就需要作出局部的调整了。然而，当我们插入黑色结点的时候，虽然只会影响性质（5），但是该性质关系到整棵树中从根到叶的每一条路径，为了插入一个结点调整整棵树结构，是否有点得不偿失。
　　我们下面就要考虑如何在插入红色结点的情况下，如何使性质（4）得以保持。性质（4）关系到一个结点和它的两个子节点，当我们插入位置的父结点是黑色的，这时五条性质都将保持，无需考虑了；如果插入位置的父结点是红色的，此时性质（4）将被破坏，我们当然不能简单的把父结点改成黑色，因为这样性质（5）又会被破坏，所以我们还需要结合插入结点的祖父结点来考虑如何恢复。我们首先应该认识到，如果父结点是红色的，那么它就不是根节点，那么祖父结点一定存在，并且是黑色结点。接下来，我们从易到难一一考虑。

情况1：当前操作结点（z）的叔结点（祖父结点的另一个子节点）是红色结点。
　　我们有性质（1）、（3）作为保证，则叔结点颜色肯定是存在的，哪怕是空结点（NIL）。此时，我们从祖父结点->父节点->操作结点->叶结点（空结点），一共有2+n个黑结点（n个出现在操作结点到叶结点之间，若z为插入结点，则n=0），也就是说以祖父结点为根的树从根到叶都是2+n个黑结点。那么，如果我们把父、叔结点涂黑，祖父结点涂红，以祖父结点为根的树仍为2+n个黑结点，性质（5）仍保持；但是于此同时，我们将祖父结点涂红可能造成与其父节点的冲突，所以我们应将祖父结点设置为当前操作结点z，继续修复工作。
情况2：当前操作结点（z）的叔结点（祖父结点的另一个子节点）是黑色结点，并且z为父结点右子。
情况3：当前操作结点（z）的叔结点（祖父结点的另一个子节点）是黑色结点，并且z为父结点左子。
　　情况2、3一看描述就非常的类似，所以我们放在一起来分析。因为叔结点是黑色，而父结点却是红色，所以我们没法像情况1一样通过局部这几个点的换色来修复性质（4），而且从情况1我们也可以看到，我们尽量只破坏性质（2）、（4），也就是我们不新增加黑结点（除了根结点，因为根变黑不影响性质（5）），只在保持性质（5）的前提下交换颜色来修复性质（4）。
　　其实，情况2可以转换成情况3集中处理。我们这样考虑：当前操作结点z是其父结点z.p的右子，我们参考系列<一>中的左旋操作，将z.p作为其中的pivot，进行左旋操作，则z.p将成为z的左子，然后我们交换它们的身份，现在z就是左子了。虽然有点绕，但是是不是就变成了情况3？而且，由于两个被操作的结点都是红色的，所以该变化没有引起多的性质破坏，尤其是性质（5）。
　　现在，我们就只要集中精力来解决情况3了。我们主要关注的结点是：z（当前操作结点）、z.p和z.p.p，现在z是z.p的左子，我们先假设z.p是z.p.p的左子（右子类似）。我们知道，z和z.p是红色的，z.p.p是黑色的，我们只要保持以z.p.p为根的子树在调整之后保持性质（5）即可。我们的策略是把z.p涂为黑色，z.p.p涂为红色，然后以z.p为pivot右旋，完成后z.p成为该子树的根，z为其左子，原来的z.p.p成为其右子。此时，以z.p为根的树仍旧保性质（5）。

　　现在，我们对插入操作的修复就完成了。下面我们来看伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
RB-INSERT-FIXUP(T, z)  
	while z.p.color == RED                           //可能与性质（4）冲突  
    	do if z.p == z.p.p.left  
        	then y ← z.p.p.right  
        	if y.color == RED  
            	then z.p.color ← BLACK               //Case 1  
            	y.color ← BLACK                      //Case 1  
            	z.p.p.color ← RED                    //Case 1  
            	z ← z.p.p                            //Case 1  
        	else if z == z.p.right  
            	then z ← z.p                         //Case 2  
            	LEFT-ROTATE(T, z)                    //Case 2  
        	z.p.color ← BLACK                        //Case 3  
        	z.p.p.color ← RED                        //Case 3  
        	RIGHT-ROTATE(T, z.p.p)                   //Case 3  
    	else (same as then clause with "right" and "left" exchanged)  
	T.root.color ← BLACK                             //保证性质（2）

　
　　上面的代码省略了z.p是z.p.p的右子的情况，但是看明白的同学一定能理解这种情况应该怎么处理。是不是看了上面的分析再看伪代码就一清二楚了！下面还有几张示意图来加深一下大家的印象，我们一起来看一下：
　　　　　　　　插入结点之后
　　　　　　　　情况1修复后
　　　　　　　　从情况2变成情况3
　　　　　　　　情况3修复后
　　上面的图分别展示的是（从上到下）：插入节点后、情况1修复后、从情况2变成情况3和情况3修复后，包含了我们所涉及到的各种情况。
　　最后，我们来看看RB-INSERT-FIXUP的运行时间。通过上面的分析可以看到，这段修复程序只会在情况1才会重复执行，当碰到情况2和3时，执行完之后就结束了，也就是说，我们最多执行2次旋转操作（情况2向情况3转变一次，情况3修复一次）。而情况1每次会沿着树爬升2层，所以修复函数的运行时间为O（lgn）。然后，插入操作在除了修复操作之外，就只涉及到依次向下寻找插入位置，所以运行时间也为O（lgn）。综合上述论述来看，RB-INSERT的运行总时间即为O(lgn)。

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

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