前面我們學習二叉搜尋樹的時候發現在一些情況下其高度不是很均勻，甚至有時候會退化成一條長鍊,是以我們引用一些”平衡”的二叉搜尋樹。紅黑樹就是一種”平衡”的二叉搜尋樹，它通過在每個結點附加顔色位和路徑上的一些限制條件可以保證在最壞的情況下基本動态集合操作的時間複雜度為O(nlgn).下面會總結紅黑樹的性質，然後分析紅黑樹的插入操作，并給出一份完整代碼。
先給出紅黑樹的結點定義：
#define RED 1
#define BLACK 0
///紅黑樹結點定義,與普通的二叉樹搜尋樹相比多了一個顔色域
typedef struct node
{
int key,color; ///定義1為紅,0為黑
node *p,*left,*right;
node(){
color=BLACK; ///預設結點顔色為黑
}
}*RBTree;
一.從紅黑樹的性質講起
紅黑樹是一棵二叉搜尋樹，它在每個結點上增加了一個存儲位來表示結點的顔色，可以是RED或BLACK。通過堆任何一條從根到葉子結點的簡單路徑上各個結點顔色進行限制，紅黑樹確定沒有一條路徑會比其它路徑要長出兩倍，因而是近似于平衡的。下面給出紅黑樹的五條”紅黑性質”，這幾條性質是後面插入和删除的基礎。
1).每個結點或是紅色或是黑色。
2).根結點是黑色的。
3).每個葉結點是黑色的
4).如果一個結點是紅色的，那麼它的兩個子節點都是黑色的。
5).對于每個結點，從該結點出發到其所有後代葉結點的簡單路徑上均包含相同數目的黑結點。
我們設從某個結點x出發(不含該結點)到達一個葉結點的一條簡單路徑上的黑結點個數為該結點的黑高，記為bh(x)。顯然根據性質5，每個結點的黑高都是唯一的。下面我們來證明：一棵含有n個内部結點的紅黑樹的高度至多為2lg(n+1).
先證明以任一結點x為根的子樹中至少包含2^bh(x)-1個内部結點。我們采用數學歸納法，對x的黑高進行歸納。如果x的黑高高度為0即x為葉子結點，則顯然正确。x的黑高為bh(x),則其兩棵子樹的黑高為bh(x)或bh(x)-1(取決與它們本身的顔色),則可歸納出對應的内部結點至少為2^(bh(x)-1)-1，即x包含的内部結點至少為2^(bh(x)-1)-1+2^(bh(x)-1)-1+1=2^bh(x)-1,是以得證。然後現在我們設含n個結點的樹高為h，然後根據性質4，可以知道從根到葉結點(不包括根結點)的任一條簡單路徑上都至少有一半的結點為黑色。是以樹的黑高至少為h/2；然後有上面的結論得n>=2^(h/2)-1.解得h<=2lg(n+1)。于是我們就證明了動态集合操作Search,Minimum,Successor等都可以在O(lgn)時間複雜度内完成了。
下面給一張紅黑樹的圖檔。
二.旋轉操作
後面的插入和删除過程中都會有破壞紅黑樹性質的情況發送，為了維護這些性質，必須要改變樹中某些結點的顔色和指針結構。指針結構的修改是通過旋轉來完成的，旋轉被分為左旋和右旋；在插入和删除操作中這兩個操作會多次出現，我們先來分析一下這兩個操作。
這兩個操作對應的圖像如下：
從圖像上可以看出，左旋和右旋操作并不是很複雜。下面我們以左旋為例進行解析：如圖我們假設結點x的右兒子為y。左旋的前提是：結點必須要有右兒子。左旋的結果是：y代替x，x成為y的左兒子，x成為y的左兒子，y的左兒子成為x的右兒子。下面是具體的代碼實作：
///左旋:對具有任意具有右孩子的結點可以進行
///傳入要選擇的結點指針的引用
///旋轉以後x的右孩子y取代了x,而x成為y的左孩子,y的左孩子成為x的右孩子
///下面的代碼就是完成這三個部分
void LeftRotate(RBTree x)
{
RBTree y=x->right; ///y表示x的右孩子
x->right=y->left; ///第一步:将x的右孩子設為y的左孩子
if(y->left!=Nul)
y->left->p=x;
y->p=x->p; ///更改y的父結點為x的父結點
if(x->p==Nul) ///第二步:y替代x,需要分情況讨論
rt=y; ///x原來是根結點,則設y為根結點
else if(x==x->p->left)
x->p->left=y; ///更改y為x父結點的左孩子
else
x->p->right=y; ///更改y為x父結點的右孩子
y->left=x; ///第三步:将x設為y的左孩子
x->p=y;
}
右旋與左旋是類似的，代碼如下：
///右旋:對任何具有左孩子的結點可以進行
///傳入要右旋的結點指針的引用
///旋轉以後結點x被左孩子y替換,x成為y的右兒子,y的右孩子成為x的左孩子
void RightRotate(RBTree x)
{
RBTree y=x->left; ///y表示x的左孩子
x->left=y->right; ///第一步:x的左孩子更改為y的右孩子
if(y->right!=Nul)
y->right->p=x;
y->p=x->p; ///更改y的父結點為x的父結點
if(x->p==Nul) ///第二步:y替代x,需要分情況讨論
rt=y; ///x原來為根結點,指定y為新根結點
else if(x==x->p->left)
x->p->left=y; ///更改x父結點的左孩子為y
else
x->p->right=y; ///更改x父結點的右孩子為y
y->right=x; ///第三步:更改y的右結點為x
x->p=y;
}
三. 插入詳解
了解紅黑樹插入和删除操作的難點在于：在我們改變一個結點以後，産生的情況太多。相應的我們也就得到了基本的讨論方法：将所有的情況進行分類讨論，然後就可以了解代碼為什麼要這樣寫了。實際上隻要把《算法導論》上的那些Case了解清楚，紅黑樹的操作也就不難懂了。下面應用分類讨論的思想來了解紅黑樹的插入操作。
首先下面我們先給出插入部分的代碼：
///紅黑樹的插入
///RB插入函數與普通的BST的插入函數隻是稍微有點不同
///我們将原來的null換成了Nul結點,然後對新加入的結點,染成紅色
///然後調用RBInsertFixUp函數進行調整,使得紅黑樹的性質不被破壞
void RBInsert(int key)
{
RBTree z=new node;
z->color=RED;
z->key=key;
z->p=z->left=z->right=Nul;
RBTree y=Nul;
RBTree x=rt;
while(x!=Nul) ///按照二叉搜尋樹的性質尋找z的插入點
{
y=x;
if(z->key<x->key)
x=x->left;
else
x=x->right;
}
z->p=y;
if(y==Nul)///插入的是根節點
rt=z;
else if(z->key<y->key)
y->left=z;
else
y->right=z;
RBInsertFixUp(z); ///插入紅色結點可能違反了紅黑樹的某些性質,調用調整函數進行調整
}
從代碼上看，這裡的插入和二叉搜尋樹的插入并沒有什麼太大的不同。隻是在最後加了一個插入調整函數：RBInsertFixUp()。之是以要加入調整函數是因為我們插入一個結點并将其染成紅色導緻紅黑樹的某條性質被違反了；是以我們需要着重的讨論到底會違反那條性質，然後我們這麼樣在調整函數中就這種情況進行性質的恢複。
首先我們設插入的結點為z，插入以後z會被染成紅色。如果z的父結點是黑色的，則不會違反任何性質，不需要調整。是以我們下面隻需要讨論z的父結點為紅色的情況。然後在這種情況下，隻有性質4是肯定會被違反的，然後我們再按z的父結點是其祖父結點的左兒子還是右兒子分類(這兩種情況沒有本質性的差別，隻是在編碼上稍微有點不同而已)，下面我們隻讨論z的父結點是其祖父結點的左兒子的情況。然後我們設z的叔結點(即z父結點的兄弟結點)結點為y。在這些前提下我們再進行分類讨論：
1)情況1：y的顔色為紅色
這時其祖父結點一定是黑色的(因為在插入這個結點之前紅黑樹沒有性質被違反)。這種情況下，我們可以将z的父結點染成黑色，z的叔結點染成黑色，z的祖父結點染成紅色；這樣染色以後，z的祖父結點以下的子樹肯定是合法的紅黑樹，但是z的祖父結點可能違反性質4了，相當于将z在樹中上升了兩層(z=z->p->p)。這種情況下如果新z的父結點為黑就會退出循環了(如果新z為根節點就一定會退出，這時候根節點有可能會被染成紅色，是以在退出循環後需要再将根節點染成黑色)。
這種情況的示意圖如下：
2)：y的顔色為黑
在y的顔色為黑的情況下我們在按z是其父結點的左孩子還是右孩子進行分類
(1).z是其父結點的左孩子
這時我們可以通過将z的父結點染成黑色，z的祖父結點染成紅色，然後對z的祖父結點進行一次右旋恢複性質4，并且不違反其它的性質(對于這一點我們隻要自己畫一下圖就可以很清楚的看到了)。
(2).z是其父結點的右孩子
這種情況顯然是可以通過将z指向z的父結點，然後對z進行一次左旋就可以變成情況(1)處理了。
這兩種情況的示意圖如下：其中圖檔上的情況二對應我們這裡的(2),情況三即為我們這裡的(1)
總的來講隻要y為黑，我們就可以退出循環了；上面的兩種情況的劃分不過是内部結構的一些小轉變而已。
綜上，其實紅黑樹的插入操作主要是違反了性質4，調整函數的過程就是分了兩類情況對性質4進行調整的過程，并不是很複雜。上面給出的是z的父結點為其祖父結點左兒子的情況，其實對于右兒子的情況基本上是一樣的(具體的見代碼)。
還有一個令人困惑的地方在于紅黑樹的代碼中大量的使用了z->p->p這種形式，但是這真的不會導緻空指針異常嗎？對此算法導論上進行了比較詳細的論證。在這裡我簡單的說一下我的看法：首先，在插入根節點的時候，是不會進入循環中的，是以就不會引用z->p->p。然後在插入根節點以後，除根結點外每個結點的祖父結點都是一定存在的，是以第一次引用不會出問題。問題隻有可能出現在z在樹中上移的情況下（對應情況1），可能會上移到某個位置，而這個位置的父結點不存在父結點，這時就會導緻空指針的危險了；但是我們要注意到，這個位置隻有可能是根結點，而如果z移動到了根節點，那麼就會因為根節點的父結點是黑色而退出循環了！根本就不會再出現z->p->p這種形式的引用。是以不需要擔心z->p->p的引用會出現空指針異常。
下面給出紅黑的的插入調整函數RBInsertFixUp()函數的代碼，其對應我們上面讨論的三種情況：
///紅黑樹插入調整函數
///我們将插入結點染成紅色,可能違反了性質4,是以要進行調整
///調整的過程其實就是根據不同的情況進行分類讨論,不斷轉換的過程
///最後轉成可以通過染色和旋轉恢複性質的情況
void RBInsertFixUp(RBTree z)
{
///在下面的代碼中z結點總是違反性質4的那個結點
while(z->p->color==RED) ///x是紅色,它的父結點也是紅色就說明性質4被違反,要持續調整
{
///下面的過程按x->p是其祖父結點的左孩子還是右兒子進行分類讨論
if(z->p==z->p->p->left) ///父結點是其祖父結點的左孩子
{
RBTree y=z->p->p->right; ///表示z的叔結點
///下面按y的顔色進行分類讨論
if(y->color==RED)
{///如果y是紅色并z的祖父結點一定是黑色的,這時我們通過下面的染色過程
///在保證黑高不變的情況下(性質5),将z在樹中上移兩層,z=z->p->p
z->p->color=BLACK;
y->color=BLACK;
z->p->p->color=RED;
z=z->p->p;///如果上移到根節點或某個父結點不為紅的結點就可以結束循環了
}
else ///叔結點為黑色
{ ///此時要根據z是其父結點的左孩子還是右孩子進行分類讨論
///如果z是左孩子則可以直接可以通過染色和右旋來恢複性質
///如果z是右孩子則可以先左旋來轉成右孩子的情況
if(z==z->p->right)
{
z=z->p;
LeftRotate(z); ///直接左旋
}
///重新染色,再右旋就可以恢複性質
z->p->color=BLACK;
z->p->p->color=RED;
RightRotate(z->p->p);
}
}
else///父結點是祖父結點的右孩子
{
RBTree y=z->p->p->left; ///叔結點
if(y->color==RED)
{
z->p->color=BLACK;
y->color=BLACK;
z->p->p->color=RED;
z=z->p->p;
}
else
{///右兒子的時候可以直接左旋,重新調色恢複性質
///左兒子可以先右旋成右兒子再處理
if(z==z->p->left)
{
z=z->p;
RightRotate(z);
}
z->p->color=BLACK;
z->p->p->color=RED;
LeftRotate(z->p->p);
}
}
}
///将根節點染成黑色，是必要的步驟；處理兩種情況
///1.第一次插入根結點被染成紅色的情況
///2.和在上面的循環中根節點可能被染成紅色的情況
rt->color=BLACK;
}
下一篇：算法導論學習–紅黑樹詳解之删除