在《算法導論 之 紅黑樹 - 插入》中已經對紅黑樹的5個性質做了較詳細的分析，同時也給出了insert操作的C語言實現。首先我們再回顧一下紅黑樹的5個性質：
①、每個節點要麼是紅色的，要麼是黑色的；
②、根結點是黑色的；
③、所有葉子結點（NIL）都是黑色的；
④、如果一個結點是紅色，則它的兩個兒子都是黑色的；
⑤、對任何一個結點，從該結點通過其子孫結點到達葉子結點（NIL）的所有路徑上包含相同數目的黑結點。
和插入操作一樣，結點的刪除操作的時間復雜度也是O（log2@N）[注：以2為底數，N為對數]，但刪除操作的處理更復雜一些。
假如需要刪除結點D，則刪除操作的過程有如下幾種情況：[注：在以下所有繪制的紅黑樹中，均未繪制葉子結點]
情況1：被刪結點D的左孩子為葉子結點，右孩子無限制（可為葉子結點，也可為非葉子結點）
處理過程：刪除結點D，並用右孩子結點替代結點D的位置。如果被刪結點D為紅色，則紅黑樹性質未被破壞，因此無需做其他調整；如果被刪結點D為黑色，則需進一步做調整處理。
圖1 情況1-1：左右孩子均為葉子結點<喎?/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+W9K219O94bXjyKG0+sHLveG140S1xM671sNdPC9wPgoKPGJyPgoKPGltZyBzcmM9"/uploadfile/Collfiles/20140118/20140118090313114.jpg" alt="\">
圖2 情況1-2：左孩子為葉子結點 右孩子不為葉子結點
[結點DR取代了葉子結點的位置]
情況2: 被刪結點D的右孩子為葉子結點，左孩子不為葉子結點
處理過程：刪除結點D，並用左孩子節點替代結點D的位置。如果被刪結點D為紅色，則紅黑樹性質未被破壞，因此不需做其他調整；如果被刪結點D為黑色， 則需進一步做調整處理。
圖3 情況2：右孩子為葉子結點 左孩子不為葉子結點
[結點DL取代結點D的位置]
情況3: 被刪結點D的左右孩子均不為葉子節點
處理過程：找到結點D的後繼結點S，將結點S的key值賦給結點D，再將結點S從樹中刪除，並用結點S的右孩子替代結點S的位置。從前面的描述可以看出，其實被刪的是結點D的後繼結點S。如果被刪結點S為紅色，則紅黑樹性質未被破壞，因此不需做其他調整；如果被刪結點S為黑色，則需進一步做調整處理。
圖4 情況3：左右孩子均不為葉子結點
[後繼結點的右孩子SR取代後繼結點S的位置]
綜合情況1、2、3可知，當實際被刪的結點為黑色時，才需進一步做調整處理 —— 實際被刪的結點為紅色時，並不會破壞紅黑樹的5點性質。
當紅黑樹中實際被刪除的結點為黑色時，則可能破壞紅黑樹的5個性質。經過分析總結，破壞紅黑樹性質的情況有如下幾種：
============================================================================
前提1：參照結點N為父結點P的左孩子
============================================================================
情況1）：參照結點N的兄弟B是紅色的
處理過程：首先，將父結點P的顏色改為紅色，兄弟結點的顏色改為黑色；其次，以父結點P為支點進行左旋處理 ——情況1轉變為情況2或3、4。如下圖所示：[注意：請注意圖中處理前後node、brother指針的變化，這將是後續處理的參照]
圖5 調整情況1
情況2）：參照結點N的兄弟B是黑色的，且B的兩個孩子都是黑色的
處理過程：將兄弟結點B的顏色改為紅色 ——情況2處理完成後，不必再進行情況3、4的判斷，重新判斷前提1、2。如下圖所示：[注意：請注意圖中處理前後node、brother指針的變化，這將是後續處理的參照]
圖6 調整情況2
情況3）：參照結點N的兄弟B是黑色的，且B的左孩子是紅色的，右孩子是黑色的
處理過程：首先，將兄弟結點B的顏色改為紅色，結點B的左孩子改為黑色；其次，以結點B為支點進行右旋處理 ——情況3轉化為情況4，後續必須進行情況4的處理。如下圖所示：[注意：請注意圖中處理前後node、brother指針的變化，這將是後續處理的參照]
圖7 調整情況3
情況4）：參照結點N的兄弟B是黑色的，且B的左孩子是黑色的，右孩子是紅色的
處理過程：首先，將父結點P的顏色拷貝給兄弟結點B，再將父結點P的顏色改為黑色，兄弟結點的顏色改為黑色；其次，以父結點P為支點，進行左旋處理；再次，將node改為樹的根結點，也意味著調整結束。如下圖所示：[注意：請注意圖中處理前後node指針的變化，這將是後續處理的參照]
圖8 調整情況4
[注：藍色表示結點顏色可能為紅，也可能為黑，在此也更能突出復制結點P的顏色給結點B]
============================================================================
前提2：參照結點N為父結點P的右孩子
============================================================================
其處理流程與前提1的四種情況正好相反，後續再補充...
/******************************************************************************
**函數名稱: rbt_delete
**功 能: 刪除操作(外部接口)
**輸入參數:
** tree: 紅黑樹
** key: 關鍵字
**輸出參數: NONE
**返 回: RBT_SUCCESS:成功 RBT_FAILED:失敗
**實現描述:
** 通過key找到需要被刪除的結點，再調用_rbt_delete()執行刪除操作
**注意事項:
**作 者: # Qifeng.zou # 2013.12.27 #
******************************************************************************/
int rbt_delete(rbt_tree_t *tree, int key)
{
rbt_node_t *node = tree->root;
if(tree->sentinel == node)
{
return RBT_SUCCESS;
}
while(tree->sentinel != node)
{
if(key == node->key)
{
return _rb_delete(tree, node); /* 刪除結點 */
}
else if(key < node->key)
{
node = node->lchild;
}
else
{
node = node->rchild;
}
}
return RBT_SUCCESS;
}
代碼1 刪除操作（外部接口）
/******************************************************************************
**函數名稱: rbt_delete
**功 能: 刪除結點(內部接口)
**輸入參數:
** tree: 紅黑樹
** dnode: 將被刪除的結點
**輸出參數: NONE
**返 回: RBT_SUCCESS:成功 RBT_FAILED:失敗
**實現描述:
** 1. 如果將被刪除的結點dnode無後繼結點，則直接被刪除，並被其左孩子或右孩子替代其位置
** 2. 如果將被刪除的結點dnode有後繼結點，則將後繼結點的其賦給dnode，並刪除後繼結點，
** 再將後繼結點的右孩子取代後繼結點的位置
** 3. 完成1、2的處理之後，如果紅黑樹的性質被破壞，則調用rbt_delete_fixup()進行調整
**注意事項:
**作 者: # Qifeng.zou # 2013.12.28 #
******************************************************************************/
int _rb_delete(rbt_tree_t *tree, rbt_node_t *dnode)
{
rbt_node_t *parent = NULL, *next = NULL, *refer = NULL;
/* 查找dnode的後繼結點next */
if((tree->sentinel == dnode->lchild)
|| (tree->sentinel == dnode->rchild))
{
next = dnode;
}
else
{
next = dnode->rchild;
while(tree->sentinel != next->lchild)
{
next = next->lchild;
}
}
/* 設置替代後繼結點的結點refer(參考結點) */
if(tree->sentinel != next->lchild)
{
refer = next->lchild;
}
else
{
refer = next->rchild;
}
refer->parent = next->parent;
if(tree->sentinel == next->parent)
{
tree->root = refer;
}
else
{
if(next == next->parent->lchild)
{
next->parent->lchild = refer;
}
else
{
next->parent->rchild = refer;
}
}
if(next != dnode)
{
dnode->key = next->key;
/* Copy next's satellite data into dnode */
}
if(rbt_is_red(next)) /* Not black */
{
free(next);
return RBT_SUCCESS;
}
free(next);
return rbt_delete_fixup(tree, refer); /* 修復紅黑樹性質 */
}
代碼2 刪除結點（內部接口）
/******************************************************************************
**函數名稱: rbt_delete_fixup
**功 能: 修復刪除操作造成的黑紅樹性質的破壞(內部接口)
**輸入參數:
** tree: 紅黑樹
** node: 實際被刪結點的替代結點(注: node有可能是葉子結點)
**輸出參數: NONE
**返 回: RBT_SUCCESS:成功 RBT_FAILED:失敗
**實現描述:
**注意事項:
** 注意: 被刪結點為黑色結點，才能調用此函數進行性質調整
**作 者: # Qifeng.zou # 2013.12.28 #
******************************************************************************/
int rbt_delete_fixup(rbt_tree_t *tree, rbt_node_t *node)
{
rbt_node_t *parent = NULL, *brother = NULL;
while(rbt_is_black(node) && (tree->root != node))
{
/* Set parent and brother */
parent = node->parent;
if(node == parent->lchild)
{
brother = parent->rchild;
/* Case 1: 兄弟結點為紅色: 以parent為支點, 左旋處理 */
if(rbt_is_red(brother))
{
rbt_set_red(parent);
rbt_set_black(brother);
rbt_left_rotate(tree, parent);
/* 參照結點node不變, 兄弟結點改為parent->rchild */
brother = parent->rchild;
/* 注意: 此時處理還沒有結束，還需要做後續的調整處理 */
}
/* Case 2: 兄弟結點為黑色(默認), 且兄弟結點的2個子結點都為黑色 */
if(rbt_is_black(brother->lchild) && rbt_is_black(brother->rchild))
{
rbt_set_red(brother);
node = parent;
}
else
{
/* Case 3: 兄弟結點為黑色(默認),
兄弟節點的左子結點為紅色, 右子結點為黑色: 以brother為支點, 右旋處理 */
if(rbt_is_black(brother->rchild))
{
rbt_set_black(brother->lchild);
rbt_set_red(brother);
rbt_right_rotate(tree, brother);
/* 參照結點node不變 */
brother = parent->rchild;
}
/* Case 4: 兄弟結點為黑色(默認),
兄弟結點右孩子結點為紅色: 以parent為支點, 左旋處理 */
rbt_copy_color(brother, parent);
rbt_set_black(brother->rchild);
rbt_set_black(parent);
rbt_left_rotate(tree, parent);
node = tree->root;
}
}
else
{
brother = parent->lchild;
/* Case 1: 兄弟結點為紅色: 以parent為支點, 右旋處理 */
if(rbt_is_red(brother))
{
rbt_set_red(parent);
rbt_set_black(brother);
rbt_right_rotate(tree, parent);
/* 參照結點node不變 */
brother = parent->lchild;
/* 注意: 此時處理還沒有結束，還需要做後續的調整處理 */
}
/* Case 2: 兄弟結點為黑色(默認), 且兄弟結點的2個子結點都為黑色 */
if(rbt_is_black(brother->lchild) && rbt_is_black(brother->rchild))
{
rbt_set_red(brother);
node = parent;
}
else
{
/* Case 3: 兄弟結點為黑色(默認),
兄弟節點的右子結點為紅色, 左子結點為黑色: 以brother為支點, 左旋處理 */
if(rbt_is_black(brother->lchild))
{
rbt_set_red(brother);
rbt_set_black(brother->rchild);
rbt_left_rotate(tree, brother);
/* 參照結點node不變 */
brother = parent->lchild;
}
/* Case 4: 兄弟結點為黑色(默認), 兄弟結點左孩子結點為紅色: 以parent為支點, 右旋處理 */
rbt_copy_color(brother, parent);
rbt_set_black(brother->lchild);
rbt_set_black(parent);
rbt_right_rotate(tree, parent);
node = tree->root;
}
}
}
rbt_set_black(node);
return RBT_SUCCESS;
}
代碼3 刪除調整
處理結果：
首先，隨機生成左圖樹，再隨機的任意個結點後，得到右圖樹，經過分析可以發現：右圖也是一個紅黑樹。經過反復驗證後，可以判斷以上代碼的處理是正確的。
—— 鄒祁峰
2014.01.18 01:21
