红黑树之个人见解

在第一部分我主要向大家阐述了自己对红黑树基本性质的理解和红黑树插入结点算法的解释，都是很表面，并没有深入探究。我必须要承认的是，对于此，只是遵从于拿来主义，并不在其上做什么深入发展，所以，本着这个原则，我将继续向大家说下红黑树删除结点的具体操作过程和伪代码解析。

先看下结点删除的伪代码吧

//RB-DELETE(T, z)
1 if left[z] = nil[T] or right[z] = nil[T]
2 then y ← z
3 else y ← TREE-SUCCESSOR(z)
4 if left[y] ≠ nil[T]
5 then x ← left[y]
6 else x ← right[y]
7 p[x] ← p[y]
8 if p[y] = nil[T]
9 then root[T] ← x
10 else if y = left[p[y]]
11 then left[p[y]] ← x
12 else right[p[y]] ← x
13 if y 3≠ z
14 then key[z] ← key[y]
15 copy y's satellite data into z
16 if color[y] = BLACK
17 then RB-DELETE-FIXUP(T, x)
18 return y

结合下图，我们来看看这段代码它想干啥

在上图中我要删除结点12，先不看代码，我们能想出来大概应该怎么做吗。我是这么想的，肯定不能14直接替换12，因为14的右孩子是13，它比14还小，这不符合二叉排序树的规定。11没准可以替换12的位置，然后把10作为11的左孩子，13作为11的右孩子，看起来二叉排序树符合了，但是如果简单地这么做，红黑树的性质肯定无法满足了，至少性质5被破坏。那么，我们就会想到在插入结点这部分中有FIXUP，在删除结点中也应当有FXIUP。正如我们期望的那样，伪代码中确实存在FIXUP。经过充分地意淫之后，我们就来仔细看看伪代码是如何把梦想转变为现实的吧

我要删除[12],代码开始第1~3行，是说，如果[12]有一个孩子是NIL，那么y也指向[12]。否则，如果z的两个孩子都是内结点（非NIL结点），那么y就指向z的后继结点，这里y指向[13]。然后，又出现了一个新变量x，它指向y的非NIL孩子结点，如果y的两个孩子都是NIL，那么x指向right[y]。在这里，x指向right[13]也就是NIL。接着，代码第7行，无条件地使x的父结点指向y的父结点，所以，现在x就不认[13]是他爹了，而是认[12]为父，但是，[13]依然视x为自己的孩子，纠结....

8~12代码，如果y的父结点是NIL，那么根结点就指向x。这是什么情况呢。假设，我们现在这个红黑树只有一个结点[9]，那么这个结点肯定是根结点，y和z都指向这个根结点，x指向根结点右孩子NIL，我如果想删除根结点，只需要是根结点指向NIL，再释放[9]的内存空间，那么就可以了。这就是8~9行代码所做的。如果不是这样，那么如果y是其父结点的左孩子，那么现在它的父结点就不认它这个儿子，而认x为儿子，如果y是右孩子，那么就其父结点就认x为右孩子，总之，就是抛弃y接受x。而之前，我们已经使x的父结点指向了y的父结点，所以，现在x与p[y]正式建立了父子关系，而y作为弃儿，是否应该立马斩草除根，free()掉呢。不行，因为我们要删除的结点的key依然存在，所以，如果y和z不相等，我们就要把z的key改为y。最后，还要判断，如果color[y] == Black，那么我们还要FIXUP。原因很简单，如果y是Black，那么我们现在相当于抛弃了y，那么红黑树的第5条性质已然改变，所以，就需要对红黑树进行修正，好了，现在是时候看一看RB-DELETE-FIXUP了。

//RB-DELETE-FIXUP(T, x)
1 while x ≠ root[T] and color[x] = BLACK
2 do if x = left[p[x]]
3 then w ← right[p[x]]
4 if color[w] = RED
5 then color[w] ← BLACK ▹ Case 1
6 color[p[x]] ← RED ▹ Case 1
7 LEFT-ROTATE(T, p[x]) ▹ Case 1
8 w ← right[p[x]] ▹ Case 1
9 if color[left[w]] = BLACK and color[right[w]] = BLACK
10 then color[w] ← RED ▹ Case 2
11 x p[x] ▹ Case 2
12 else if color[right[w]] = BLACK
13 then color[left[w]] ← BLACK ▹ Case 3
14 color[w] ← RED ▹ Case 3
15 RIGHT-ROTATE(T, w) ▹ Case 3
16 w ← right[p[x]] ▹ Case 3
17 color[w] ← color[p[x]] ▹ Case 4
18 color[p[x]] ← BLACK ▹ Case 4
19 color[right[w]] ← BLACK ▹ Case 4
20 LEFT-ROTATE(T, p[x]) ▹ Case 4
21 x ← root[T] ▹ Case 4
22 else (same as then clause with "right" and "left" exchanged)
23 color[x] ← BLACK	

第2行，由于x是父结点的右孩子，因此属于else (same as then clause with "right" and "left" exchanged)的内容。把所有的left和right互换。这时，x是右孩子，w就是左孩子[11]。第4行，color[w] == Black，因此不属于case1。接着往下去case2:w的两个孩子都是黑色，也不符合，再往下去，w的左孩子黑色，右孩子红色也不符合，所以是case4:w的左孩子是红色，正好color[10] == Red。代码第17行，w的颜色改为x的父结点的颜色，所以color[11] == Red，color[13] == Black，color[10] == Black，再以x的父结点13为支点右旋就得到了下图

红黑树的性质得以保存，我们就可以进行下一次结点的插入删除等操作了。

从以后操作可以看出，删除结点操作也是很简便的。case1,2,3的样图我就不再说了，大家可以参考我第一部分提的那个博客，上面说的非常详细。

最后，有一个问题还是需要注意的。如果插入两个相同key值的结点，比如插入两个key值都为1的结点，那么后插入的1就会变为之前插入的1的右孩子，那么如果再插入一个2,就会在后插入的1的右孩子上再接一个2，如果再插入一个2呢。所以，问题就来了，如果我们插入{1, 1, 2, 2, 3, 3...}甚至，如果我们只插入{1, 1, 1, 1, 1, 1...}，那么此时构造的红黑树就会没有左子树（NIL不计）。红黑树就会变得畸形地高。因此，我们需要根据个人口味的不同调制配方，使红黑树健康地成长为我们想要的样子。正如Mahatma Gandhi所说：Be the change you want to see in the world! 

好了，以上就是我对红黑树的一点点个人见解，如果朋友们有什么好的意见和建议，一定要给我留言哦。