一、紅黑樹(shù)概述
紅黑樹(shù)和我們以前學(xué)過(guò)的AVL樹(shù)類似，都是在進(jìn)行插入和刪除操作時(shí)通過(guò)特定操作保持二叉查找樹(shù)的平衡，從而獲得較高的查找性能。不過(guò)自從紅黑樹(shù)出來(lái)后，AVL樹(shù)就被放到了博物館里，據(jù)說(shuō)是紅黑樹(shù)有更好的效率，更高的統(tǒng)計(jì)性能。這一點(diǎn)在我們了解了紅黑樹(shù)的實(shí)現(xiàn)原理后，就會(huì)有更加深切的體會(huì)。
紅黑樹(shù)和AVL樹(shù)的區(qū)別在于它使用顏色來(lái)標(biāo)識(shí)結(jié)點(diǎn)的高度，它所追求的是局部平衡而不是AVL樹(shù)中的非常嚴(yán)格的平衡。學(xué)過(guò)數(shù)據(jù)結(jié)構(gòu)的人應(yīng)該都已經(jīng)領(lǐng)教過(guò)AVL樹(shù)的復(fù)雜，但AVL樹(shù)的復(fù)雜比起紅黑樹(shù)來(lái)說(shuō)簡(jiǎn)直是小巫見(jiàn)大巫，紅黑樹(shù)才是真正的變態(tài)級(jí)數(shù)據(jù)結(jié)構(gòu)。
由于STL中的關(guān)聯(lián)式容器默認(rèn)的底層實(shí)現(xiàn)都是紅黑樹(shù)，因此紅黑樹(shù)對(duì)于后續(xù)學(xué)習(xí)STL源碼還是很重要的，有必要掌握紅黑樹(shù)的實(shí)現(xiàn)原理和源碼實(shí)現(xiàn)。
紅黑樹(shù)是AVL樹(shù)的變種，紅黑樹(shù)通過(guò)一些著色法則確保沒(méi)有一條路徑會(huì)比其它路徑長(zhǎng)出兩倍，因而達(dá)到接近平衡的目的。所謂紅黑樹(shù)，不僅是一個(gè)二叉搜索樹(shù)，而且必須滿足一下規(guī)則：
1、每個(gè)節(jié)點(diǎn)不是紅色就是黑色。
2、根節(jié)點(diǎn)為黑色。
3、如果節(jié)點(diǎn)為紅色，其子節(jié)點(diǎn)必須為黑色。
4、任意一個(gè)節(jié)點(diǎn)到到NULL（樹(shù)尾端）的任何路徑，所含之黑色節(jié)點(diǎn)數(shù)必須相同。
上面的這些約束保證了這個(gè)樹(shù)大致上是平衡的，這也決定了紅黑樹(shù)的插入、刪除、查詢等操作是比較快速的。 根據(jù)規(guī)則4，新增節(jié)點(diǎn)必須為紅色；根據(jù)規(guī)則3，新增節(jié)點(diǎn)之父節(jié)點(diǎn)必須為黑色。當(dāng)新增節(jié)點(diǎn)根據(jù)二叉搜索樹(shù)的規(guī)則到達(dá)其插入點(diǎn)時(shí)，卻未能符合上述條件時(shí)，就必須調(diào)整顏色并旋轉(zhuǎn)樹(shù)形，如下圖：
假設(shè)我們?yōu)樯蠄D分別插入節(jié)點(diǎn)3、8、35、75，根據(jù)二叉搜索樹(shù)的規(guī)則，插入這四個(gè)節(jié)點(diǎn)后，我們會(huì)發(fā)現(xiàn)它們都破壞了紅黑樹(shù)的規(guī)則，因此我們必須調(diào)整樹(shù)形，也就是旋轉(zhuǎn)樹(shù)形并改變節(jié)點(diǎn)的顏色。
二、紅黑樹(shù)上結(jié)點(diǎn)的插入
在討論紅黑樹(shù)的插入操作之前必須要明白，任何一個(gè)即將插入的新結(jié)點(diǎn)的初始顏色都為紅色。這一點(diǎn)很容易理解，因?yàn)椴迦牒邳c(diǎn)會(huì)增加某條路徑上黑結(jié)點(diǎn)的數(shù)目，從而導(dǎo)致整棵樹(shù)黑高度的不平衡。但如果新結(jié)點(diǎn)的父結(jié)點(diǎn)為紅色時(shí)（如下圖所示），將會(huì)違反紅黑樹(shù)的性質(zhì)：一條路徑上不能出現(xiàn)相鄰的兩個(gè)紅色結(jié)點(diǎn)。這時(shí)就需要通過(guò)一系列操作來(lái)使紅黑樹(shù)保持平衡。
為了清楚地表示插入操作以下在結(jié)點(diǎn)中使用“新”字表示一個(gè)新插入的結(jié)點(diǎn)；使用“父”字表示新插入點(diǎn)的父結(jié)點(diǎn)；使用“叔”字表示“父”結(jié)點(diǎn)的兄弟結(jié)點(diǎn)；使用“祖”字表示“父”結(jié)點(diǎn)的父結(jié)點(diǎn)。插入操作分為以下幾種情況：
1、黑父
如下圖所示，如果新節(jié)點(diǎn)的父結(jié)點(diǎn)為黑色結(jié)點(diǎn)，那么插入一個(gè)紅點(diǎn)將不會(huì)影響紅黑樹(shù)的平衡，此時(shí)插入操作完成。紅黑樹(shù)比AVL樹(shù)優(yōu)秀的地方之一在于黑父的情況比較常見(jiàn)，從而使紅黑樹(shù)需要旋轉(zhuǎn)的幾率相對(duì)AVL樹(shù)來(lái)說(shuō)會(huì)少一些。
2、紅父
如果新節(jié)點(diǎn)的父結(jié)點(diǎn)為紅色，這時(shí)就需要進(jìn)行一系列操作以保證整棵樹(shù)紅黑性質(zhì)。如下圖所示，由于父結(jié)點(diǎn)為紅色，此時(shí)可以判定，祖父結(jié)點(diǎn)必定為黑色。這時(shí)需要根據(jù)叔父結(jié)點(diǎn)的顏色來(lái)決定做什么樣的操作。青色結(jié)點(diǎn)表示顏色未知。由于有可能需要根結(jié)點(diǎn)到新點(diǎn)的路徑上進(jìn)行多次旋轉(zhuǎn)操作，而每次進(jìn)行不平衡判斷的起始點(diǎn)（我們可將其視為新點(diǎn)）都不一樣。所以我們?cè)诖耸褂靡粋€(gè)藍(lán)色箭頭指向這個(gè)起始點(diǎn)，并稱之為判定點(diǎn)。
2.1 紅叔
當(dāng)叔父結(jié)點(diǎn)為紅色時(shí)，如下圖所示，無(wú)需進(jìn)行旋轉(zhuǎn)操作，只要將父和叔結(jié)點(diǎn)變?yōu)楹谏?，將祖父結(jié)點(diǎn)變?yōu)榧t色即可。但由于祖父結(jié)點(diǎn)的父結(jié)點(diǎn)有可能為紅色，從而違反紅黑樹(shù)性質(zhì)。此時(shí)必須將祖父結(jié)點(diǎn)作為新的判定點(diǎn)繼續(xù)向上（迭代）進(jìn)行平衡操作。
需要注意的是，無(wú)論“父節(jié)點(diǎn)”在“叔節(jié)點(diǎn)”的左邊還是右邊，無(wú)論“新節(jié)點(diǎn)”是“父節(jié)點(diǎn)”的左孩子還是右孩子，它們的操作都是完全一樣的（其實(shí)這種情況包括4種，只需調(diào)整顏色，不需要旋轉(zhuǎn)樹(shù)形）。
2.2 黑叔
當(dāng)叔父結(jié)點(diǎn)為黑色時(shí)，需要進(jìn)行旋轉(zhuǎn)，以下圖示了所有的旋轉(zhuǎn)可能：
Case 1:
Case 2:
Case 3:
Case 4:
可以觀察到，當(dāng)旋轉(zhuǎn)完成后，新的旋轉(zhuǎn)根全部為黑色，此時(shí)不需要再向上回溯進(jìn)行平衡操作，插入操作完成。需要注意，上面四張圖的“叔”、“1”、“2”、“3”結(jié)點(diǎn)有可能為黑哨兵結(jié)點(diǎn)。
其實(shí)紅黑樹(shù)的插入操作不是很難，甚至比AVL樹(shù)的插入操作還更簡(jiǎn)單些。紅黑樹(shù)的插入操作源代碼如下：
[cpp]
view plaincopy// 元素插入操作 insert_unique()
// 插入新值：節(jié)點(diǎn)鍵值不允許重復(fù)，若重復(fù)則插入無(wú)效
// 注意，返回值是個(gè)pair，第一個(gè)元素是個(gè)紅黑樹(shù)迭代器，指向新增節(jié)點(diǎn)
// 第二個(gè)元素表示插入成功與否
template<class Key , class Value , class KeyOfValue , class Compare , class Alloc>
pair<typename rb_tree<Key , Value , KeyOfValue , Compare , Alloc>::iterator , bool>
rb_tree<Key , Value , KeyOfValue , Compare , Alloc>::insert_unique(const Value &v)
{
rb_tree_node* y = header; // 根節(jié)點(diǎn)root的父節(jié)點(diǎn)
rb_tree_node* x = root(); // 從根節(jié)點(diǎn)開(kāi)始
bool comp = true;
while(x != 0)
{
y = x;
comp = key_compare(KeyOfValue()(v) , key(x)); // v鍵值小于目前節(jié)點(diǎn)之鍵值？
x = comp ? left(x) : right(x); // 遇“大”則往左，遇“小于或等于”則往右
}
// 離開(kāi)while循環(huán)之后，y所指即插入點(diǎn)之父節(jié)點(diǎn)（此時(shí)的它必為葉節(jié)點(diǎn)）
iterator j = iterator(y); // 令迭代器j指向插入點(diǎn)之父節(jié)點(diǎn)y
if(comp) // 如果離開(kāi)while循環(huán)時(shí)comp為真（表示遇“大”，將插入于左側(cè)）
{
if(j == begin()) // 如果插入點(diǎn)之父節(jié)點(diǎn)為最左節(jié)點(diǎn)
return pair<iterator , bool>(_insert(x , y , z) , true);
else // 否則（插入點(diǎn)之父節(jié)點(diǎn)不為最左節(jié)點(diǎn)）
--j; // 調(diào)整j，回頭準(zhǔn)備測(cè)試
}
if(key_compare(key(j.node) , KeyOfValue()(v) ))
// 新鍵值不與既有節(jié)點(diǎn)之鍵值重復(fù)，于是以下執(zhí)行安插操作
return pair<iterator , bool>(_insert(x , y , z) , true);
// 以上，x為新值插入點(diǎn)，y為插入點(diǎn)之父節(jié)點(diǎn)，v為新值
// 進(jìn)行至此，表示新值一定與樹(shù)中鍵值重復(fù)，那么就不應(yīng)該插入新值
return pair<iterator , bool>(j , false);
}
// 真正地插入執(zhí)行程序 _insert()
template<class Key , class Value , class KeyOfValue , class Compare , class Alloc>
typename<Key , Value , KeyOfValue , Compare , Alloc>::_insert(base_ptr x_ , base_ptr y_ , const Value &v)
{
// 參數(shù)x_ 為新值插入點(diǎn)，參數(shù)y_為插入點(diǎn)之父節(jié)點(diǎn)，參數(shù)v為新值
link_type x = (link_type) x_;
link_type y = (link_type) y_;
link_type z;
// key_compare 是鍵值大小比較準(zhǔn)則。應(yīng)該會(huì)是個(gè)function object
if(y == header || x != 0 || key_compare(KeyOfValue()(v) , key(y) ))
{
z = create_node(v); // 產(chǎn)生一個(gè)新節(jié)點(diǎn)
left(y) = z; // 這使得當(dāng)y即為header時(shí)，leftmost() = z
if(y == header)
{
root() = z;
rightmost() = z;
}
else if(y == leftmost()) // 如果y為最左節(jié)點(diǎn)
leftmost() = z; // 維護(hù)leftmost()，使它永遠(yuǎn)指向最左節(jié)點(diǎn)
}
else
{
z = create_node(v); // 產(chǎn)生一個(gè)新節(jié)點(diǎn)
right(y) = z; // 令新節(jié)點(diǎn)成為插入點(diǎn)之父節(jié)點(diǎn)y的右子節(jié)點(diǎn)
if(y == rightmost())
rightmost() = z; // 維護(hù)rightmost()，使它永遠(yuǎn)指向最右節(jié)點(diǎn)
}
parent(z) = y; // 設(shè)定新節(jié)點(diǎn)的父節(jié)點(diǎn)
left(z) = 0; // 設(shè)定新節(jié)點(diǎn)的左子節(jié)點(diǎn)
right(z) = 0; // 設(shè)定新節(jié)點(diǎn)的右子節(jié)點(diǎn)
// 新節(jié)點(diǎn)的顏色將在_rb_tree_rebalance()設(shè)定（并調(diào)整）
_rb_tree_rebalance(z , header->parent); // 參數(shù)一為新增節(jié)點(diǎn)，參數(shù)二為根節(jié)點(diǎn)root
++node_count; // 節(jié)點(diǎn)數(shù)累加
return iterator(z); // 返回一個(gè)迭代器，指向新增節(jié)點(diǎn)
}
// 全局函數(shù)
// 重新令樹(shù)形平衡（改變顏色及旋轉(zhuǎn)樹(shù)形）
// 參數(shù)一為新增節(jié)點(diǎn)，參數(shù)二為根節(jié)點(diǎn)root
inline void _rb_tree_rebalance(_rb_tree_node_base* x , _rb_tree_node_base*& root)
{
x->color = _rb_tree_red; //新節(jié)點(diǎn)必為紅
while(x != root && x->parent->color == _rb_tree_red) // 父節(jié)點(diǎn)為紅
{
if(x->parent == x->parent->parent->left) // 父節(jié)點(diǎn)為祖父節(jié)點(diǎn)之左子節(jié)點(diǎn)
{
_rb_tree_node_base* y = x->parent->parent->right; // 令y為伯父節(jié)點(diǎn)
if(y && y->color == _rb_tree_red) // 伯父節(jié)點(diǎn)存在，且為紅
{
x->parent->color = _rb_tree_black; // 更改父節(jié)點(diǎn)為黑色
y->color = _rb_tree_black; // 更改伯父節(jié)點(diǎn)為黑色
x->parent->parent->color = _rb_tree_red; // 更改祖父節(jié)點(diǎn)為紅色
x = x->parent->parent;
}
else // 無(wú)伯父節(jié)點(diǎn)，或伯父節(jié)點(diǎn)為黑色
{
if(x == x->parent->right) // 如果新節(jié)點(diǎn)為父節(jié)點(diǎn)之右子節(jié)點(diǎn)
{
x = x->parent;
_rb_tree_rotate_left(x , root); // 第一個(gè)參數(shù)為左旋點(diǎn)
}
x->parent->color = _rb_tree_black; // 改變顏色
x->parent->parent->color = _rb_tree_red;
_rb_tree_rotate_right(x->parent->parent , root); // 第一個(gè)參數(shù)為右旋點(diǎn)
}
}
else // 父節(jié)點(diǎn)為祖父節(jié)點(diǎn)之右子節(jié)點(diǎn)
{
_rb_tree_node_base* y = x->parent->parent->left; // 令y為伯父節(jié)點(diǎn)
if(y && y->color == _rb_tree_red) // 有伯父節(jié)點(diǎn)，且為紅
{
x->parent->color = _rb_tree_black; // 更改父節(jié)點(diǎn)為黑色
y->color = _rb_tree_black; // 更改伯父節(jié)點(diǎn)為黑色
x->parent->parent->color = _rb_tree_red; // 更改祖父節(jié)點(diǎn)為紅色
x = x->parent->parent; // 準(zhǔn)備繼續(xù)往上層檢查
}
else // 無(wú)伯父節(jié)點(diǎn)，或伯父節(jié)點(diǎn)為黑色
{
if(x == x->parent->left) // 如果新節(jié)點(diǎn)為父節(jié)點(diǎn)之左子節(jié)點(diǎn)
{
x = x->parent;
_rb_tree_rotate_right(x , root); // 第一個(gè)參數(shù)為右旋點(diǎn)
}
x->parent->color = _rb_tree_black; // 改變顏色
x->parent->parent->color = _rb_tree_red;
_rb_tree_rotate_left(x->parent->parent , root); // 第一個(gè)參數(shù)為左旋點(diǎn)
}
}
}//while
root->color = _rb_tree_black; // 根節(jié)點(diǎn)永遠(yuǎn)為黑色
}
// 左旋函數(shù)
inline void _rb_tree_rotate_left(_rb_tree_node_base* x , _rb_tree_node_base*& root)
{
// x 為旋轉(zhuǎn)點(diǎn)
_rb_tree_node_base* y = x->right; // 令y為旋轉(zhuǎn)點(diǎn)的右子節(jié)點(diǎn)
x->right = y->left;
if(y->left != 0)
y->left->parent = x; // 別忘了回馬槍設(shè)定父節(jié)點(diǎn)
y->parent = x->parent;
// 令y完全頂替x的地位（必須將x對(duì)其父節(jié)點(diǎn)的關(guān)系完全接收過(guò)來(lái)）
if(x == root) // x為根節(jié)點(diǎn)
root = y;
else if(x == x->parent->left) // x為其父節(jié)點(diǎn)的左子節(jié)點(diǎn)
x->parent->left = y;
else // x為其父節(jié)點(diǎn)的右子節(jié)點(diǎn)
x->parent->right = y;
y->left = x;
x->parent = y;
}
// 右旋函數(shù)
inline void _rb_tree_rotate_right(_rb_tree_node_base* x , _rb_tree_node_base*& root)
{
// x 為旋轉(zhuǎn)點(diǎn)
_rb_tree_node_base* y = x->left; // 令y為旋轉(zhuǎn)點(diǎn)的左子節(jié)點(diǎn)
x->left = y->right;
if(y->right != 0)
y->right->parent = x; // 別忘了回馬槍設(shè)定父節(jié)點(diǎn)
y->parent = x->parent;
// 令y完全頂替x的地位（必須將x對(duì)其父節(jié)點(diǎn)的關(guān)系完全接收過(guò)來(lái)）
if(x == root)
root = y;
else if(x == x->parent->right) // x為其父節(jié)點(diǎn)的右子節(jié)點(diǎn)
x->parent->right = y;
else // x為其父節(jié)點(diǎn)的左子節(jié)點(diǎn)
x->parent->left = y;
y->right = x;
x->parent = y;
}
算法導(dǎo)論書(shū)上給出的紅黑樹(shù)的性質(zhì)如下，跟STL源碼剖析書(shū)上面的4條性質(zhì)大同小異。
1、每個(gè)結(jié)點(diǎn)或是紅色的，或是黑色的
2、根節(jié)點(diǎn)是黑色的
3、每個(gè)葉結(jié)點(diǎn)（NIL）是黑色的
4、如果一個(gè)節(jié)點(diǎn)是紅色的，則它的兩個(gè)兒子都是黑色的。
5、對(duì)于每個(gè)結(jié)點(diǎn)，從該結(jié)點(diǎn)到其子孫結(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑色結(jié)點(diǎn)。
從紅黑樹(shù)上刪除一個(gè)節(jié)點(diǎn)，可以先用普通二叉搜索樹(shù)的方法，將節(jié)點(diǎn)從紅黑樹(shù)上刪除掉，然后再將被破壞的紅黑性質(zhì)進(jìn)行恢復(fù)。
我們回憶一下普通二叉樹(shù)的節(jié)點(diǎn)刪除方法：Z指向需要?jiǎng)h除的節(jié)點(diǎn)，Y指向?qū)嵸|(zhì)結(jié)構(gòu)上被刪除的結(jié)點(diǎn)，如果Z節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn)或沒(méi)有子節(jié)點(diǎn)，那么Y就是指向Z指向的節(jié)點(diǎn)。如果Z節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)，那么Y指向Z節(jié)點(diǎn)的后繼節(jié)點(diǎn)（其實(shí)前趨也是一樣的），而Z的后繼節(jié)點(diǎn)絕對(duì)不可能有左子樹(shù)。因此，僅從結(jié)構(gòu)來(lái)看，二叉樹(shù)上實(shí)質(zhì)被刪除的節(jié)點(diǎn)最多只可能有一個(gè)子樹(shù)。
現(xiàn)在我們來(lái)看紅黑性質(zhì)的恢復(fù)過(guò)程：
如果Y指向的節(jié)點(diǎn)是個(gè)紅色節(jié)點(diǎn)，那么直接刪除掉Y以后，紅黑性質(zhì)不會(huì)被破壞。操作結(jié)束。
如果Y指向的節(jié)點(diǎn)是個(gè)黑色節(jié)點(diǎn)，那么就有幾條紅黑性質(zhì)可能受到破壞了。首先是包含Y節(jié)點(diǎn)的所有路徑，黑高度都減少了一（第５條被破壞）。其次，如果Y的有紅色子節(jié)點(diǎn)，Y又有紅色的父節(jié)點(diǎn)，那么Y被刪除后，就出現(xiàn)了兩個(gè)相鄰的紅色節(jié)點(diǎn)（第４條被破壞）。最后，如果Y指向的是根節(jié)點(diǎn)，而Y的子節(jié)點(diǎn)又是紅色的，那么Y被刪除后，根節(jié)點(diǎn)就變成紅色的了（第２條被破壞）。
其中，第５條被破壞是讓我們比較難受的。因?yàn)檫@影響到了全局。這樣動(dòng)作就太大太復(fù)雜了。而且在這個(gè)條件下，進(jìn)行其它紅黑性質(zhì)的恢復(fù)也很困難。所以我們首先解決這個(gè)問(wèn)題：如果不改變含Y路徑的黑高度，那么樹(shù)的其它部分的黑高度就必須做出相應(yīng)的變化來(lái)適應(yīng)它。所以，我們想辦法恢復(fù)原來(lái)含Y節(jié)點(diǎn)的路徑的黑高度。做法就是：無(wú)條件的把Y節(jié)點(diǎn)的黑色，推到它的子節(jié)點(diǎn)X上去。（X可能是NIL節(jié)點(diǎn)）。這樣，X就可能具有雙重黑色，或同時(shí)具有紅黑兩色，也就是第１條性質(zhì)被破壞了。
但第１條性質(zhì)是比較容易恢復(fù)的：一、如果X是同時(shí)具有紅黑兩色，那么好辦，直接把X涂成黑色，就行了。而且這樣把所有問(wèn)題都解決了。因?yàn)閷變?yōu)楹谏?，２、４兩條如果有問(wèn)題的話也會(huì)得到恢復(fù)，算法結(jié)束。二、如果X是雙黑色，那么我們希望把這種情況向上推一直推到根節(jié)點(diǎn)（調(diào)整樹(shù)結(jié)構(gòu)和顏色，X的指向新的雙黑色節(jié)點(diǎn)，X不斷向上移動(dòng)），讓根節(jié)點(diǎn)具雙黑色，這時(shí)，直接把X的一層黑色去掉就行了（因?yàn)楦?jié)點(diǎn)被包含在所有的路徑上，所以這樣做所有路徑同時(shí)黑高減少一，不會(huì)破壞紅黑特征）。
下面就具體地分析如何恢復(fù)1、２、４三個(gè)可能被破壞的紅黑特性：我們知道，如果X指向的節(jié)點(diǎn)是有紅黑兩色，或是X是根節(jié)點(diǎn)時(shí)，只需要簡(jiǎn)單的對(duì)X進(jìn)行一些改變就行了。要對(duì)除X節(jié)點(diǎn)外的其它節(jié)點(diǎn)進(jìn)行操作時(shí)，必定是這樣的情況：X節(jié)點(diǎn)是雙層黑色，且X有父節(jié)點(diǎn)P。由知可知，X必然有兄弟節(jié)點(diǎn)W，而且這個(gè)W節(jié)點(diǎn)必定有兩個(gè)子節(jié)點(diǎn)。（因?yàn)檫@是原樹(shù)滿足紅黑條件要求而自然具備的。X為雙黑色，那么P的另一個(gè)子節(jié)點(diǎn)以下一定要有至少兩層的節(jié)點(diǎn)，否則黑色高度不可能和X路徑一致）。所以我們就分析這些節(jié)點(diǎn)之間如何變形，把問(wèn)題限制在比較小的范圍內(nèi)解決。另一個(gè)前提是：X在一開(kāi)始，肯定是樹(shù)底的葉節(jié)點(diǎn)或是NIL節(jié)點(diǎn)，所以在遞歸向上的過(guò)程中，每一步都保證下一步進(jìn)行時(shí)，至少 X的子樹(shù)是滿足紅黑特性的。因此子樹(shù)的情況就可以認(rèn)為是已經(jīng)正確的了，這樣，分析就只限制在X節(jié)點(diǎn)，X的父節(jié)點(diǎn)P和X的兄弟節(jié)點(diǎn)W，以及W的兩個(gè)子節(jié)點(diǎn)。這些個(gè)節(jié)點(diǎn)中。
下面僅僅考慮X原本是黑色的情況即可。
在這種情況下，X此時(shí)應(yīng)該具有雙重黑色，算法的過(guò)程就是將這多出的一重黑色向上移動(dòng)，直到遇到紅節(jié)點(diǎn)或者根節(jié)點(diǎn)。
接著往下分析， 會(huì)遇到4種情況，實(shí)際上是8種， 因?yàn)槠渲?種是相互對(duì)稱的，這可以通過(guò)判斷X是其父節(jié)點(diǎn)的右孩子還是左孩子來(lái)區(qū)分。下面我們以X是其父節(jié)點(diǎn)的左孩子的情況來(lái)分析這4種情況，實(shí)際上接下來(lái)的調(diào)整過(guò)程，就是要想方設(shè)法將經(jīng)過(guò)X的所有路徑上的黑色節(jié)點(diǎn)個(gè)數(shù)增加1。
具體分為以下四種情況：（下面針對(duì)x是左兒子的情況討論，右兒子對(duì)稱）
Case1：X的兄弟W是紅色（想辦法將其變?yōu)楹谏?div style="height:15px;">
由于W是紅色的，因此其兒子節(jié)點(diǎn)和父節(jié)點(diǎn)必為黑色，只要將W和其父節(jié)點(diǎn)的顏色對(duì)換，在對(duì)父節(jié)點(diǎn)進(jìn)行一次左旋轉(zhuǎn)，便將W的左子節(jié)點(diǎn)放到了X的兄弟節(jié)點(diǎn)上，X的兄弟節(jié)點(diǎn)變成了黑色，且紅黑性質(zhì)不變。但還不算完，只是暫時(shí)將情況1轉(zhuǎn)變成了下面的情況2或3或4。
Case2：X的兄弟節(jié)點(diǎn)W是黑色的，而且W的兩個(gè)子節(jié)點(diǎn)都是黑色的。此時(shí)可以將X的一重黑色和W的黑色同時(shí)去掉，而轉(zhuǎn)加給他們的父節(jié)點(diǎn)上，這是X就指向它的父節(jié)點(diǎn)了，因此此時(shí)父節(jié)點(diǎn)具有雙重顏色了。這一重黑色節(jié)點(diǎn)上移。
如果父節(jié)點(diǎn)原來(lái)是紅色的，現(xiàn)在又加一層黑色，那么X現(xiàn)在指向的這個(gè)節(jié)點(diǎn)就是紅黑兩色的，直接把X（也就是父節(jié)點(diǎn)）著為黑色。問(wèn)題就已經(jīng)完整解決了。
如果父節(jié)點(diǎn)現(xiàn)在是雙層黑色，那就以父節(jié)點(diǎn)為新的X進(jìn)行向上的下一次的遞歸。
Case3：X的兄弟節(jié)點(diǎn)W是黑色的，而且W的左子節(jié)點(diǎn)是紅色的，右子節(jié)點(diǎn)是黑色的。此時(shí)通過(guò)交換W和其左子節(jié)點(diǎn)的顏色并進(jìn)行一次向右旋轉(zhuǎn)就可轉(zhuǎn)換成下面的第四種情況。注意，原來(lái)L是紅色的，所以L的子節(jié)點(diǎn)一定是黑色的，所以旋轉(zhuǎn)中L節(jié)點(diǎn)的一個(gè)子樹(shù)掛到之后著為紅色的W節(jié)點(diǎn)上不會(huì)破壞紅黑性質(zhì)。變形后黑色高度不變。
Case4：X的兄弟節(jié)點(diǎn)W是黑色的，而且W的右子節(jié)點(diǎn)是紅色的。這種情況下，做一次左旋，W就處于根的位置，將W保持為原來(lái)的根的位置的顏色，同時(shí)將W的兩個(gè)新的兒子節(jié)點(diǎn)的顏色變?yōu)楹谏?，去掉X的一重黑色。這樣整個(gè)問(wèn)題也就得到了解決。遞歸結(jié)束。（在代碼上，為了標(biāo)識(shí)遞歸結(jié)束，我們把X指向根節(jié)點(diǎn)）
因此，只要按上面四種情況一直遞歸處理下去，X最終總會(huì)指向根結(jié)點(diǎn)或一個(gè)紅色結(jié)點(diǎn)，這時(shí)我們就可以結(jié)束遞歸并把問(wèn)題解決了。
以上就是紅黑樹(shù)的節(jié)點(diǎn)刪除全過(guò)程。
總結(jié)：
如果我們通過(guò)上面的情況畫(huà)出所有的分支圖，我們可以得出如下結(jié)論
插入操作：解決的是 紅-紅 問(wèn)題
刪除操作：解決的是 黑-黑 問(wèn)題
即你可以從分支圖中看出，需要往上遍歷的情況為紅紅(插入)，或者為黑黑黑（刪除）的情況，如果你認(rèn)真分析并總結(jié)所有的情況后，并堅(jiān)持下來(lái)，紅黑樹(shù)也就沒(méi)有想象中的那么恐怖了，并且很美妙；
詳細(xì)的紅黑樹(shù)刪除節(jié)點(diǎn)的代碼如下：
[cpp]
view plaincopy#include<iostream>
using namespace std;
// 定義節(jié)點(diǎn)顏色
enum COLOR
{
BLACK = 0,
RED
};
// 紅黑樹(shù)節(jié)點(diǎn)
typedef struct RB_Tree_Node
{
int key;
struct RB_Tree_Node *left;
struct RB_Tree_Node *right;
struct RB_Tree_Node *parent;
unsigned char RB_COLOR;
}RB_Node;
// 紅黑樹(shù)，包含一個(gè)指向根節(jié)點(diǎn)的指針
typedef struct RBTree
{
RB_Node* root;
}*RB_Tree;
// 紅黑樹(shù)的NIL節(jié)點(diǎn)
static RB_Tree_Node NIL = {0, 0, 0, 0, BLACK};
#define PNIL (&NIL) // NIL節(jié)點(diǎn)地址
void Init_RBTree(RB_Tree pTree) // 初始化一棵紅黑樹(shù)
{
pTree->root = PNIL;
}
// 查找最小鍵值節(jié)點(diǎn)
RB_Node* RBTREE_MIN(RB_Node* pRoot)
{
while (PNIL != pRoot->left)
{
pRoot = pRoot->left;
}
return pRoot;
}
/*
15
/ \
/ \
/ \
6 18
/ \ / \
/ \ / \
3 7 17 20
/ \ \
/ \ \
2 4 13
/
/
9
*/
// 查找指定節(jié)點(diǎn)的后繼節(jié)點(diǎn)
RB_Node* RBTREE_SUCCESSOR(RB_Node* pRoot)
{
if (PNIL != pRoot->right) // 查找圖中6的后繼節(jié)點(diǎn)時(shí)就調(diào)用RBTREE_MIN函數(shù)
{
return RBTREE_MIN(pRoot->right);
}
// 節(jié)點(diǎn)沒(méi)有右子樹(shù)的時(shí)候，進(jìn)入下面的while循環(huán)（如查找圖中13的后繼節(jié)點(diǎn)時(shí)，它的后繼節(jié)點(diǎn)是15）
RB_Node* pParent = pRoot->parent;
while((PNIL != pParent) && (pRoot == pParent->right))
{
pRoot = pParent;
pParent = pRoot->parent;
}
return pParent;
}
// 紅黑樹(shù)的節(jié)點(diǎn)刪除
RB_Node* Delete(RB_Tree pTree , RB_Node* pDel)
{
RB_Node* rel_delete_point;
if(pDel->left == PNIL || pDel->right == PNIL)
rel_delete_point = pDel;
else
rel_delete_point = RBTREE_SUCCESSOR(pDel); // 查找后繼節(jié)點(diǎn)
RB_Node* delete_point_child;
if(rel_delete_point->right != PNIL)
{
delete_point_child = rel_delete_point->right;
}
else if(rel_delete_point->left != PNIL)
{
delete_point_child = rel_delete_point->left;
}
else
{
delete_point_child = PNIL;
}
delete_point_child->parent = rel_delete_point->parent;
if(rel_delete_point->parent == PNIL) // 刪除的節(jié)點(diǎn)是根節(jié)點(diǎn)
{
pTree->root = delete_point_child;
}
else if(rel_delete_point == rel_delete_point->parent->right)
{
rel_delete_point->parent->right = delete_point_child;
}
else
{
rel_delete_point->parent->left = delete_point_child;
}
if(pDel != rel_delete_point)
{
pDel->key = rel_delete_point->key;
}
if(rel_delete_point->RB_COLOR == BLACK)
{
DeleteFixUp(pTree , delete_point_child);
}
return rel_delete_point;
}
/*
算法導(dǎo)論上的描述如下：
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
*/
//接下來(lái)的工作，很簡(jiǎn)單，即把上述偽代碼改寫(xiě)成c++代碼即可
void DeleteFixUp(RB_Tree pTree , RB_Node* node)
{
while(node != pTree->root && node->RB_COLOR == BLACK)
{
if(node == node->parent->left)
{
RB_Node* brother = node->parent->right;
if(brother->RB_COLOR==RED) //情況1：x的兄弟w是紅色的。
{
brother->RB_COLOR = BLACK;
node->parent->RB_COLOR = RED;
RotateLeft(node->parent);
}
else //情況2：x的兄弟w是黑色的，
{
if(brother->left->RB_COLOR == BLACK && brother->right->RB_COLOR == BLACK) //w的兩個(gè)孩子都是黑色的
{
brother->RB_COLOR = RED;
node = node->parent;
}
else
{
if(brother->right->RB_COLOR == BLACK) //情況3：x的兄弟w是黑色的，w的右孩子是黑色（w的左孩子是紅色）。
{
brother->RB_COLOR = RED;
brother->left->RB_COLOR = BLACK;
RotateRight(brother);
brother = node->parent->right; //情況3轉(zhuǎn)換為情況4
}
//情況4：x的兄弟w是黑色的，且w的右孩子時(shí)紅色的
brother->RB_COLOR = node->parent->RB_COLOR;
node->parent->RB_COLOR = BLACK;
brother->right->RB_COLOR = BLACK;
RotateLeft(node->parent);
node = pTree->root;
}//else
}//else
}
else //同上，原理一致，只是遇到左旋改為右旋，遇到右旋改為左旋即可。其它代碼不變。
{
RB_Node* brother = node->parent->left;
if(brother->RB_COLOR == RED)
{
brother->RB_COLOR = BLACK;
node->parent->RB_COLOR = RED;
RotateRight(node->parent);
}
else
{
if(brother->left->RB_COLOR==BLACK && brother->right->RB_COLOR == BLACK)
{
brother->RB_COLOR = RED;
node = node->parent;
}
else
{
if(brother->left->RB_COLOR==BLACK)
{
brother->RB_COLOR = RED;
brother->right->RB_COLOR = BLACK;
RotateLeft(brother);
brother = node->parent->left; //情況3轉(zhuǎn)換為情況4
}
brother->RB_COLOR = node->parent->RB_COLOR;
node->parent->RB_COLOR = BLACK;
brother->left->RB_COLOR = BLACK;
RotateRight(node->parent);
node = pTree->root;
}
}
}
}//while
node->RB_COLOR = BLACK; //如果X節(jié)點(diǎn)原來(lái)為紅色，那么直接改為黑色
}
