作者：July 二零一一年一月九日
-----------------------------
本文參考：
I、 The Art of Computer Programming Volume I
II、 Introduction to Algorithms, Second Edition
III、The Annotated STL Sources
IV、 Wikipedia
V、 Algorithms In C Third Edition
VI、 本人寫的關於紅黑樹的前三篇文章：
第一篇：教你透徹了解紅黑樹：
http://www.BkJia.com/kf/201104/87322.html
第二篇：紅黑樹算法的層層剖析與逐步實現
http://www.BkJia.com/kf/201104/87321.html
第三篇：教你徹底實現紅黑樹：紅黑樹的c源碼實現與剖析
html">http://www.BkJia.com/kf/201104/87323.html
---------------------------------------------
前言：
1、有讀者反應，說看了我的前幾篇文章，對紅黑樹的了解還是不夠透徹。
2、我個人覺得，如果我一步一步，用圖+代碼來闡述各種插入、刪除情況，可能會更直觀易懂。
3、既然寫了紅黑樹，那麼我就一定要把它真正寫好，讓讀者真正徹底明白紅黑樹。
本文相對我前面紅黑樹相關的3篇文章，主要有以下幾點改進：
1.圖、文字敘述、代碼編寫，彼此對應，明朗而清晰。
2.宏觀總結，紅黑樹的性質與插入、刪除情況的認識。
3.代碼來的更直接，結合圖，給你最直觀的感受，徹底明白紅黑樹。
ok，首先，以下幾點，你現在應該是要清楚明白了的：
I、紅黑樹的五個性質：
1）每個結點要麼是紅的，要麼是黑的。
2）根結點是黑的。
3）每個葉結點，即空結點（NIL）是黑的。
4）如果一個結點是紅的，那麼它的倆個兒子都是黑的。
5）對每個結點，從該結點到其子孫結點的所有路徑上包含相同數目的黑結點。
II、紅黑樹插入的幾種情況：
情況1，z的叔叔y是紅色的。
情況2：z的叔叔y是黑色的，且z是右孩子
情況3：z的叔叔y是黑色的，且z是左孩子
III、紅黑樹刪除的幾種情況。
情況1：x的兄弟w是紅色的。
情況2：x的兄弟w是黑色的，且w的倆個孩子都是黑色的。
情況3：x的兄弟w是黑色的，且w的左孩子是紅色，w的右孩子是黑色。
情況4：x的兄弟w是黑色的，且w的右孩子是紅色的。
除此之外，還得明確一點：
IV、我們知道，紅黑樹插入、或刪除結點後，
可能會違背、或破壞紅黑樹的原有的性質，
所以為了使插入、或刪除結點後的樹依然維持為一棵新的紅黑樹，
那就要做倆方面的工作：
1、部分結點顏色，重新著色
2、調整部分指針的指向，即左旋、右旋。
V、並區別以下倆種操作：
1)紅黑樹插入、刪除結點的操作，RB-INSERT(T, z)，RB-DELETE(T, z)
2).紅黑樹已經插入、刪除結點之後，
為了保持紅黑樹原有的紅黑性質而做的恢復與保持紅黑性質的操作。
如RB-INSERT-FIXUP(T, z)，RB-DELETE-FIXUP(T, x)
以上這5點，我已經在我前面的2篇文章，都已闡述過不少次了，希望，你現在已經透徹明了。
---------------------------------------------------------------------
本文，著重圖解分析紅黑樹插入、刪除結點後為了維持紅黑性質而做修復工作的各種情況。
[下文各種插入、刪除的情況，與我的第二篇文章，紅黑樹算法的實現與剖析相對應]
ok，開始。
一、在下面的分析中，我們約定：
要插入的節點為，N
父親節點，P
祖父節點，G
叔叔節點，U
兄弟節點，S
如下圖所示，找一個節點的祖父和叔叔節點:
node grandparent(node n) //祖父
{
return n->parent->parent;
}
node uncle(node n) //叔叔
{
if (n->parent == grandparent(n)->left)
return grandparent(n)->right;
else
return grandparent(n)->left;
}
二、紅黑樹插入的幾種情況
情形1: 新節點N位於樹的根上，沒有父節點
void insert_case1(node n) {
if (n->parent == NULL)
n->color = BLACK;
else
insert_case2(n);
}
情形2: 新節點的父節點P是黑色
void insert_case2(node n) {
if (n->parent->color == BLACK)
return; /* 樹仍舊有效 */
else
insert_case3(n);
}
情形3:父節點P、叔叔節點U，都為紅色，
[對應第二篇文章中，的情況1：z的叔叔是紅色的。]
void insert_case3(node n) {
if (uncle(n) != NULL && uncle(n)->color == RED) {
n->parent->color = BLACK;
uncle(n)->color = BLACK;
grandparent(n)->color = RED;
insert_case1(grandparent(n)); //因為祖父節點可能是紅色的，違反性質4，遞歸情形1.
}
else
insert_case4(n); //否則，叔叔是黑色的，轉到下述情形4處理。
此時新插入節點N做為P的左子節點或右子節點都屬於上述情形3,上圖僅顯示N做為P左子的情形。
情形4: 父節點P是紅色，叔叔節點U是黑色或NIL;
插入節點N是其父節點P的右孩子，而父節點P又是其父節點的左孩子。
[對應我第二篇文章中，的情況2：z的叔叔是黑色的，且z是右孩子]
void insert_case4(node n) {
if (n == n->parent->right && n->parent == grandparent(n)->left) {
rotate_left(n->parent);
n = n->left;
} else if (n == n->parent->left && n->parent == grandparent(n)->right) {
rotate_right(n->parent);
n = n->right;
}
insert_case5(n); //轉到下述情形5處理。
情形5: 父節點P是紅色，而叔父節點U 是黑色或NIL，
要插入的節點N 是其父節點的左孩子，而父節點P又是其父G的左孩子。
[對應我第二篇文章中，情況3：z的叔叔是黑色的，且z是左孩子。]
void insert_case5(node n) {
n->parent->color = BLACK;
grandparent(n)->color = RED;
if (n == n->parent->left && n->parent == grandparent(n)->left) {
rotate_right(grandparent(n));
} else {
/* 反情況，N 是其父節點的右孩子，而父節點P又是其父G的右孩子 */
rotate_left(grandparent(n));
}
}
三、紅黑樹刪除的幾種情況
上文我們約定，兄弟節點設為S，我們使用下述函數找到兄弟節點:
struct node * sibling(struct node *n) //找兄弟節點
{
&nbs
