C#與資料結構--樹論--紅黑樹（RED BLACK TREE）
介紹
今天我們來介紹另一種平衡二叉樹：紅黑樹（Red Black Tree），紅黑樹由Rudolf Bayer于1972年發明，當時被稱為平衡二叉B樹（symmetric binary B-trees），1978年被Leonidas J. Guibas 和 Robert Sedgewick改成一個比較摩登的名字：紅黑樹。
紅黑樹和之前所講的AVL樹類似，都是在進行插入和删除操作時通過特定操作保持二叉查找樹的平衡，進而獲得較高的查找性能。自從紅黑樹出來後，AVL樹就被放到了博物館裡，據說是紅黑樹有更好的效率，更高的統計性能。不過在我了解了紅黑樹的實作原理後，并不相信這是真的，關于這一點我們會在後面進行讨論。
紅黑樹和AVL樹的差別在于它使用顔色來辨別結點的高度，它所追求的是局部平衡而不是AVL樹中的非常嚴格的平衡。之前我們在講解AVL樹時，已經領教過AVL樹的複雜，但AVL樹的複雜比起紅黑樹來說簡直是小巫見大巫。紅黑樹是真正的變态級資料結構。
首先來一個Silverlight做的紅黑樹的動畫，它有助于幫你了解什麼是紅黑樹。這裡需要注意，必須安裝Silverlight 2.0 RTW 才能正常運作遊戲，下載下傳位址：
http://www.microsoft.com/silverlight/resources/install.aspx?v=2.0
最新發現不登入部落格園的使用者無法直接看到Silverlight，如果是這樣，請移步到以下網址觀看動畫：
http://www.bbniu.com/matrix/ShowApplication.aspx?id=149
使用注意事項：
l 結點隻接收整數，如果在添加和删除操作中輸入非法字串，則會随機添加或删除一個0~99之間的整數。
l 可以不在編輯框中輸入數字，直接單擊添加和删除按鈕進行添加和删除操作。
l 可以拖動拖動條控制動畫速度。
紅黑樹的平衡
紅黑樹首先是一棵二叉查找樹，它每個結點都被标上了顔色（紅色或黑色），紅黑樹滿足以下5個性質：
1、 每個結點的顔色隻能是紅色或黑色。
2、 根結點是黑色的。
3、 每個葉子結點都帶有兩個空的黑色結點（被稱為黑哨兵），如果一個結點n的隻有一個左孩子，那麼n的右孩子是一個黑哨兵；如果結點n隻有一個右孩子，那麼n的左孩子是一個黑哨兵。
4、 如果一個結點是紅的，則它的兩個兒子都是黑的。也就是說在一條路徑上不能出現相鄰的兩個紅色結點。
5、 對于每個結點來說，從該結點到其子孫葉結點的所有路徑上包含相同數目的黑結點。
紅黑樹的這5個性質中，第3點是比較難了解的，但它卻非常有必要。我們看圖1中的左邊這張圖，如果不使用黑哨兵，它完全滿足紅黑樹性質，結點50到兩個葉結點8和葉結點82路徑上的黑色結點數都為2個。但如果加入黑哨兵後（如圖1右圖中的小黑圓點），葉結點的個數變為8個黑哨兵，根結點50到這8個葉結點路徑上的黑高度就不一樣了，是以它并不是一棵紅黑樹。
要看真正的紅黑樹請在以上動畫中添加幾個結點，看看是否滿足以上性質。
紅黑樹的旋轉操作
紅黑樹的旋轉操作和AVL樹一樣，分為LL、RR、LR、RL四種旋轉類型，差别在于旋轉完成後改變的是結點的顔色，而不是平衡因子。旋轉動畫示範請參考AVL這篇文章中的Flash動畫：
http://www.cnblogs.com/abatei/archive/2008/11/17/1335031.html
紅黑樹上結點的插入
在讨論紅黑樹的插入操作之前必須要明白，任何一個即将插入的新結點的初始顔色都為紅色。這一點很容易了解，因為插入黑點會增加某條路徑上黑結點的數目，進而導緻整棵樹黑高度的不平衡。但如果新結點父結點為紅色時（如圖2所示），将會違返紅黑樹性質：一條路徑上不能出現相鄰的兩個紅色結點。這時就需要通過一系列操作來使紅黑樹保持平衡。
為了清楚地表示插入操作以下在結點中使用“新”字表示一個新插入的結點；使用“父”字表示新插入點的父結點；使用“叔”字表示“父”結點的兄弟結點；使用“祖”字表示“父”結點的父結點。插入操作分為以下幾種情況：
1、黑父
如圖3所示，如果新點的父結點為黑色結點，那麼插入一個紅點将不會影響紅黑樹的平衡，此時插入操作完成。紅黑樹比AVL樹優秀的地方之一在于黑父的情況比較常見，進而使紅黑樹需要旋轉的幾率相對AVL樹來說會少一些。
2．紅父
如果新點的父結點為紅色，這時就需要進行一系列操作以保證整棵樹紅黑性質。如圖3所示，由于父結點為紅色，此時可以判定，祖父結點必定為黑色。這時需要根據叔父結點的顔色來決定做什麼樣的操作。青色結點表示顔色未知。由于有可能需要根結點到新點的路徑上進行多次旋轉操作，而每次進行不平衡判斷的起始點（我們可将其視為新點）都不一樣。是以我們在此使用一個藍色箭頭指向這個起始點，并稱之為判定點。
2.1 紅叔
當叔父結點為紅色時，如圖4所示，無需進行旋轉操作，隻要将父和叔結點變為黑色，将祖父結點變為紅色即可。但由于祖父結點的父結點有可能為紅色，進而違反紅黑樹性質。此時必須将祖父結點作為新的判定點繼續向上進行平衡操作。
需要注意，無論“父”在“叔”的左邊還是右邊，無論“新”是“父”的左孩子還是右孩子，它們的操作都完全一樣。
2.2 黑叔
當叔父結點為黑色時，需要進行旋轉，以下圖示了所有的旋轉可能
情形1：
情形2：
情形3：
情形4：
可以觀察到，當旋轉完成後，新的旋轉根全部為黑色，此時不需要再向上回溯進行平衡操作，插入操作完成。需要注意，上面四張圖的“叔”、“1”、“2”、“3”結點有可能為黑哨兵結點。
其實紅黑樹的插入操作不是很難，甚至比AVL樹的插入操作還更簡單些。但删除操作就遠遠比AVL樹複雜得多，下面就介紹紅黑樹的删除操作。
紅黑樹上結點的删除
紅黑樹本身是一棵二叉查找樹，它的删除和二叉查找樹的删除類似。首先要找到真正的删除點，當被删除結點n存在左右孩子時，真正的删除點應該是n的中序遍在前驅，關于這一點請複習二叉查找樹的删除。如圖9所示，當删除結點20時，實際被删除的結點應該為18，結點20的資料變為18。
是以可以推斷出，在進行删除操作時，真正的删除點必定是隻有一個孩子或沒有孩子的結點。而根據紅黑樹的性質可以得出以下兩個結論：
1、 删除操作中真正被删除的必定是隻有一個紅色孩子或沒有孩子的結點。
2、 如果真正的删除點是一個紅色結點，那麼它必定是一個葉子結點。
了解這兩點非常重要，如圖10所示，除了情況(a)外，其他任一種況結點N都無法滿足紅黑樹性質。
在以下讨論中，我們使用藍色箭頭表示真正的删除點，它也是旋轉操作過程中的第一個判定點；真正的删除點使用“舊”标注，舊點所在位置将被它的的孩子結點所取代（最多隻有一個孩子），我們使用“新”表示舊點的孩子結點。删除操作可分為以下幾種情形：
1、舊點為紅色結點
若舊點為紅色結點，則它必定是葉子結點，直接删除即可。如圖11所示
2、一紅一黑
當舊點為黑色結點，新點為紅色結點時，将新點取代舊點位置後，将新點染成黑色即可（如圖12所示）。這裡需要注意：舊點為紅色，新點為黑色的情況不可能存在。
3、雙黑
當舊點和新點都為黑色時（新點為空結點時，亦屬于這種情況），情況比較複雜，需要根據舊點兄弟結點的顔色來決定進行什麼樣的操作。我們使用“兄”來表示舊點的兄弟結點。這裡可分為紅兄和黑兄兩種情況：
3.1 紅兄
由于兄弟結點為紅色，是以父結點必定為黑色，而舊點被删除後，新點取代了它的位置。下圖示範了兩種可能的情況：
紅兄的情況需要進行RR或LL型旋轉，然後将父結點染成紅色，兄結點染成黑色。然後重新以新點為判定點進行平衡操作。我們可以觀察到，旋轉操作完成後，判定點沒有向上回溯，而是降低了一層，此時變成了黑兄的情況。
3.2 黑兄
黑兄的情況最為複雜，需要根據黑兄孩子結點（這裡用“侄”表示）和父親結點的顔色來決定做什麼樣的操作。
3.2.1 黑兄二黑侄紅父
如圖14所示，這種情況比較簡單，隻需将父結點變為黑色，兄結點變為黑色，新結點變為黑色即可，删除操作到此結束。
3.2.2 黑兄二黑侄黑父
如圖15所示，此時将父結點染成新結點的顔色，新結點染成黑色，兄結點染成紅色即可。當新結點為紅色時，父結點被染成紅色，此時需要以父結點為判定點繼續向上進行平衡操作。
（2010-3-25 注意：經網友BourneHan的指正，現已确定3.2.1和3.2.2中的新結點應為黑色，而不是現在的不确定顔色。基于以下2點原因，我并不打算在代碼及博文中更改這個錯誤：
1、這個錯誤對代碼及動畫的正确性沒有影響。
2、之前的代碼及動畫經過了大量測試，需要花很多時間，更改代碼意味着重新測試，現在的确抽不出這麼多時間來做這項工作。
這裡隻能對各位讀者說聲對不起了，最快的補救方法就是在此點出錯誤，讓讀者明了。)
3.2.3 黑兄紅侄
黑兄紅侄有以下四種情形，下面分别進行圖示：
情形1：
情形2：
情形3：
情形4：
由以上圖例所示，看完以上四張圖的兄弟有可能會有一個疑問，如果情形1和情形2中的兩個侄子結點都為紅色時，是該進行LL旋轉還是進行LR旋轉呢？答案是進行LL旋轉。情形3和情形4則是優先進行RR旋轉的判定。
紅黑樹的代碼實作
本以為紅黑樹的代碼非常容易，因為System.Collections.Generic.SortedDictionary類就是使用紅黑樹實作的，把代碼的算法部分摳出來就搞定了。但看了SortedDictionary源碼後有些失望，C#中真正實作紅黑樹的是TreeSet類，SortedDictionary隻是在TreeSet的基礎上進一步抽象，加上了Key/Value泛型對。TreeSet使用了一種新的紅黑樹算法，它在搜尋插入點和删除點時預先進行旋轉和染色操作，進而避免插入和删除後的回溯。這種算法看上去很美，但仔細想想，如果插入的是一個已經存在的結點，删除的結點并不存在，那這些預平衡處理不是白做了嗎？更可怕的是如果在一條路徑上間隔進行一次插入和一次删除，而這些操作沒有命中目标，那麼大家就會看到結點的顔色變來變去，這些都是無用功。來看看在尋找插入和删除點的路徑上TreeSet每前進一步都要做些什麼：給四個變量指派；判斷每個結點的兩個孩子結點的顔色。這種算法在《java資料結構和算法》這本書中有詳細講述，不過隻講解了插入算法。另外國内也專門有一篇論文描述這個算法，他的測試結果是這種算法優于其他算法，估計測試時沒有不命中目标的情況發生。總之我并不相信這是一個好的算法。
為了證明我的想法，我不得不自己實作紅黑樹，實作思路跟AVL樹很類似，也是使用一個數組儲存通路路徑以進行回溯，當然，考慮到紅黑樹不嚴格的平衡，數組的長度設為64，這并不會給性能帶來什麼影響。過程很艱辛，需要做大量測試。很不幸，寫完後繼續做紅黑樹的Silverlight動畫時不小心把原來的代碼給覆寫掉了，結點删除部分的代碼丢失。當時幾乎崩潰，不過重寫并沒有我想象的那麼困難，很快完成，感覺思路清晰了很多，實作比原來也有了改進，感謝上帝！
下面把代碼貼出來，如果了解了上面所講内容是很容易讀懂這些代碼的。
using System;
namespace PaintBST
{
public class RBTree : IBinaryTree //實作畫樹接口
{ //成員變量
private Node _head; //頭指針
private Node[] path = new Node[32]; //記錄通路路徑上的結點
private int p; //表示目前通路到的結點在_path上的索引
INode IBinaryTree.Head //顯式接口實作
{
get { return (INode)_head; }
}
public bool Add(int value) //添加一個元素
{ //如果是空樹，則新結點成為二叉排序樹的根
if (_head == null)
{
_head = new Node(value);
_head.IsRed = false;
return true;
}
p = 0;
//parent為上一次通路的結點，current為目前通路結點
Node parent = null, current = _head;
while (current != null)
{
path[p++] = current; //将路徑上的結點插入數組
//如果插入值已存在，則插入失敗
if (current.Data == value)
{
return false;
}
parent = current;
//當插入值小于目前結點，則繼續通路左子樹，否則通路右子樹
current = (value < parent.Data) ? parent.Left : parent.Right;
}
current = new Node(value); //建立新結點
current.IsRed = true;
if (value < parent.Data) //如果插入值小于雙親結點的值
{
parent.Left = current; //成為左孩子
}
else //如果插入值大于雙親結點的值
{
parent.Right = current; //成為右孩子
}
if (!parent.IsRed)
{
return true;
}
path[p] = current;
//回溯并旋轉
while ((p -= 2) >= 0) //現在p指向插入點的祖父結點
{
Node grandParent = path[p];
parent = path[p + 1];
if (!parent.IsRed)
{
break;
}
Node uncle = grandParent.Left == parent ? grandParent.Right : grandParent.Left;
current = path[p + 2];
if (IsRed(uncle)) //叔父存在并且為紅色的情況
{
parent.IsRed = false;
uncle.IsRed = false;
if (p > 0) //如果祖父不是根結點，則将其染成紅色
{
grandParent.IsRed = true;
}
}
else //叔父不存在或為黑的情況需要旋轉
{
Node newRoot;
if (grandParent.Left == parent) //如果目前結點及父結點同為左孩子或右孩子
{
newRoot = (parent.Left == current) ? LL(grandParent) : LR(grandParent);
}
else
{
newRoot = (parent.Right == current) ? RR(grandParent) : RL(grandParent);
}
grandParent.IsRed = true; //祖父染成紅色
newRoot.IsRed = false; //新根染成黑色
//将新根同曾祖父連接配接
ReplaceChildOfNodeOrRoot((p > 0) ? path[p - 1] : null, grandParent, newRoot);
return true; //旋轉後不需要繼續回溯，添加成功，直接退出
}
}
return true;
}
//旋轉根旋轉後換新根
private void ReplaceChildOfNodeOrRoot(Node parent, Node child, Node newChild)
{
if (parent != null)
{
if (parent.Left == child)
{
parent.Left = newChild;
}
else
{
parent.Right = newChild;
}
}
else
{
_head = newChild;
}
}
private static bool IsBlack(Node node)
{
return ((node != null) && !node.IsRed);
}
private static bool IsNullOrBlack(Node node)
{
if (node != null)
{
return !node.IsRed;
}
return true;
}
private static bool IsRed(Node node)
{
return ((node != null) && node.IsRed);
}
//删除指定值
public bool Remove(int value)
{
p = -1;
//parent表示雙親結點，node表示目前結點
Node node = _head;
//尋找指定值所在的結點
while (node != null)
{
path[++p] = node;
//如果找到，則調用RemoveNode方法删除結點
if (value == node.Data)
{
RemoveNode(node);//現在p指向被删除結點
return true; //傳回true表示删除成功
}
if (value < node.Data)
{ //如果删除值小于目前結點，則向左子樹繼續尋找
node = node.Left;
}
else
{ //如果删除值大于目前結點，則向右子樹繼續尋找
node = node.Right;
}
}
return false; //傳回false表示删除失敗
}
//删除指定結點
private void RemoveNode(Node node)
{
Node tmp = null; //tmp最終指向實際被删除的結點
//當被删除結點存在左右子樹時
if (node.Left != null && node.Right != null)
{
tmp = node.Left; //擷取左子樹
path[++p] = tmp;
while (tmp.Right != null) //擷取node的中序周遊前驅結點，并存放于tmp中
{ //找到左子樹中的最右下結點
tmp = tmp.Right;
path[++p] = tmp;
}
//用中序周遊前驅結點的值代替被删除結點的值
node.Data = tmp.Data;
}
else
{
tmp = node;
}
//當隻有左子樹或右子樹或為葉子結點時
//首先找到惟一的孩子結點
Node newTmp = tmp.Left;
if (newTmp == null) //如果隻有右孩子或沒孩子
{
newTmp = tmp.Right;
}
if (p > 0)
{
Node parent = path[p - 1];
if (parent.Left == tmp)
{ //如果被删結點是左孩子
parent.Left = newTmp;
}
else
{ //如果被删結點是右孩子
parent.Right = newTmp;
}
if (!tmp.IsRed && IsRed(newTmp))
{
newTmp.IsRed = false;
return;
}
}
else //當删除的是根結點時
{
_head = newTmp;
if (_head != null)
{
_head.IsRed = false;
}
return;
}
path[p] = newTmp;
//如果被删除的是紅色結點，則它必定是葉子結點，删除成功，傳回
if (IsRed(tmp))
{
return;
}
//删除完後進行旋轉，現在p指向實際被删除的位置,這個位置可能為空,tmp指向被删除的舊點，
while (p > 0)
{ //剩下的是雙黑的情況
//首先找到兄弟結點
Node current = path[p];
Node parent = path[p - 1];
bool currentIsLeft = (parent.Left == current);
Node sibling = currentIsLeft ? parent.Right : parent.Left;
//紅兄的情況，需要LL旋轉或RR旋轉
if (IsRed(sibling))
{
Node newRoot;
if (currentIsLeft)
{
newRoot = RR(parent);
}
else
{
newRoot = LL(parent);
}
ReplaceChildOfNodeOrRoot(p > 1 ? path[p - 2] : null, parent, newRoot);
sibling.IsRed = false;
parent.IsRed = true;
//回溯點降低
path[p - 1] = newRoot;
path[p] = parent;
path[++p] = current;
}
else //黑兄的情況
{
//黑兄二黑侄
if (IsNullOrBlack(sibling.Left) && IsNullOrBlack(sibling.Right))
{ //紅父的情況
if (parent.IsRed)
{
parent.IsRed = false;
sibling.IsRed = true;
if (current != null)
{
current.IsRed = false;
}
break; //删除成功
}
else //黑父的情況
{
parent.IsRed = IsRed(current);
if (current != null)
{
current.IsRed = false;
}
sibling.IsRed = true;
p--; //需要繼續回溯
}
}
else //黑兄紅侄
{
Node newRoot;
if (currentIsLeft) //兄弟在右邊
{
if (IsRed(sibling.Right)) //紅侄在右邊
{ //RR型旋轉
newRoot = RR(parent);
sibling.Right.IsRed = false;
}
else
{ //RL型旋轉
newRoot = RL(parent);
}
}
else //兄弟在左邊
{
if (IsRed(sibling.Left))
{ //LL型旋轉
newRoot = LL(parent);
sibling.Left.IsRed = false;
}
else
{ //LR型旋轉
newRoot = LR(parent);
}
}
if (current != null)
{
current.IsRed = false;
}
newRoot.IsRed = parent.IsRed;
parent.IsRed = false;
ReplaceChildOfNodeOrRoot(p > 1 ? path[p - 2] : null, parent, newRoot);
break; //不需要回溯，删除成功
}
}
}
}
//root為旋轉根，rootPrev為旋轉根雙親結點
private Node LL(Node root) //LL型旋轉，傳回旋轉後的新子樹根
{
Node left = root.Left;
root.Left = left.Right;
left.Right = root;
return left;
}
private Node LR(Node root) //LR型旋轉，傳回旋轉後的新子樹根
{
Node left = root.Left;
Node right = left.Right;
root.Left = right.Right;
right.Right = root;
left.Right = right.Left;
right.Left = left;
return right;
}
private Node RR(Node root) //RR型旋轉，傳回旋轉後的新子樹根
{
Node right = root.Right;
root.Right = right.Left;
right.Left = root;
return right;
}
private Node RL(Node root) //RL型旋轉，傳回旋轉後的新子樹根
{
Node right = root.Right;
Node left = right.Left;
root.Right = left.Left;
left.Left = root;
right.Left = left.Right;
left.Right = right;
return left;
}
}
}
完成紅黑樹後，做了一個比較粗糙的測試程式，對我自己實作的紅黑樹RBTree，C#類庫中的紅黑樹TreeSet和我自己實作的AVL樹AVLTree進行了簡單的測試，為了公平起見，我把TreeSet改成了整型版，這樣大家都站在了同一起跑線上。考慮到垃圾回收，這樣的測試并不是很精确、科學，但也能說明一些問題。以後我會專門寫程式對各種常見的查找資料結構進行測試
| 測試項目 | RBTree | TreeSet | AVLTree |
| 200000個整數順序插入(全部命中) | 0.4375 | 0.4844 | 0.3437 |
| 200000個整數順序插入後順序删除(全部命中，隻對删除部分計時) | 0.25 | 0.5 | 0.20 |
| 200000個整數随機插入(全部命中) | 0.4375 | 0.5469 | 0.5 |
| 200000個整數随機插入後順序删除(全部命中，隻對删除部分計時) | 0.5 | 0.7343 | 0.4219 |
| 200000個整數順序插入(一半命中) | 0.297 | 0.344 | 0.234 |
| 100000個整數随機插入後順序删除(一半命中，隻對删除部分計時) | 0.094 | 0.203 | 0.109 |
後記
測試結果基本證明了我的想法，惟一意外的是AVL樹有兩個項目輸給了RBTree。在理論上，RBTree在某些方面的确是比AVL樹更為優秀，但從程式員的角度來說，紅黑樹的實作需要調用大量方法，比如結點顔色的判斷，這會抵消紅黑樹的性能優勢。國外網站也有針對紅黑樹和AVL樹的測試，結果基本上是AVL樹勝出。
紅黑樹的動畫還有一些bug，整體效果也不盡如人意，我也懶得再改了，寫它比寫紅黑樹困難些。寫它主要是為了學習Silverlight，這也算是第一個Silverlight動畫作品，東西弄懂了就不想再動了。打算将來更深入地了解Silverlight後再全面修改這個動畫。