C#與數據結構--樹論--紅黑樹（Red Black Tree）(下)

下面把代碼貼出來，如果理解了上面所講內容是很容易讀懂這些代碼的。

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後再全面修改這個動畫。