下面把代码贴出来，如果理解了上面所讲内容是很容易读懂这些代码的。

usingSystem;
namespacePaintBST
{
　　publicclassRBTree:IBinaryTree//实现画树接口
　　{　　//成员变量
　　　　privateNode_head;//头指针
　　　　privateNode[]path=newNode[32];//记录访问路径上的结点
　　　　privateintp;//表示当前访问到的结点在_path上的索引
　　　　INodeIBinaryTree.Head//显式接口实现
　　　　{
　　　　　　get{return(INode)_head;}
　　　}
　　　　publicboolAdd(intvalue)//添加一个元素
　　　　{　//如果是空树，则新结点成为二叉排序树的根
　　　　　　if(_head==null)
　　　　　　{
　　　　　　　　_head=newNode(value);
　　　　　　　　_head.IsRed=false;
　　　　　　　　returntrue;
　　　　　　}
　　　　　　p=0;
　　　　　　//parent为上一次访问的结点，current为当前访问结点
　　　　　　Nodeparent=null,current=_head;
　　　　　　while(current!=null)
　　　　　　{
　　　　　　　　path[p++]=current;//将路径上的结点插入数组
　　　　　　　　//如果插入值已存在，则插入失败
　　　　　　　　if(current.Data==value)
　　　　　　　　{
　　　　　　　　　　returnfalse;
　　　　　　　　}
　　　　　　　　parent=current;
　　　　　　　　//当插入值小于当前结点，则继续访问左子树，否则访问右子树
　　　　　　　　current=(value<parent.Data)?parent.Left:parent.Right;
　　　　　　}
　　　　　　current=newNode(value);//创建新结点
　　　　　　　current.IsRed=true;
　　　　　　if(value<parent.Data)//如果插入值小于双亲结点的值
　　　　　　　{
　　　　　　　　parent.Left=current;//成为左孩子
　　　　　　　}
　　　　　　else//如果插入值大于双亲结点的值
　　　　　　　{
　　　　　　　　parent.Right=current;//成为右孩子
　　　　　　　}
　　　　　　if(!parent.IsRed)
　　　　　　{
　　　　　　　　returntrue;
　　　　　　}
　　　　　　path[p]=current;
　　　　　　//回溯并旋转
　　　　　　while((p-=2)>=0)//现在p指向插入点的祖父结点
　　　　　　{
　　　　　　　　NodegrandParent=path[p];
　　　　　　　　parent=path[p+1];
　　　　　　　　if(!parent.IsRed)
　　　　　　　　{
　　　　　　　　　　break;
　　　　　　　　}
　　　　　　　　Nodeuncle=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//叔父不存在或为黑的情况需要旋转
　　　　　　　　　{
　　　　　　　　　　NodenewRoot;
　　　　　　　　　　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);
　　　　　　　　　　returntrue;//旋转后不需要继续回溯，添加成功，直接退出
　　　　　　　　　}
　　　　　　}
　　　　　　returntrue;
　　　　}
　　　　//旋转根旋转后换新根
　　　　privatevoidReplaceChildOfNodeOrRoot(Nodeparent,Nodechild,NodenewChild)
　　　　{
　　　　　　if(parent!=null)
　　　　　　{
　　　　　　　　if(parent.Left==child)
　　　　　　　　{
　　　　　　　　　　parent.Left=newChild;
　　　　　　　　}
　　　　　　　　else
　　　　　　　　{
　　　　　　　　　　parent.Right=newChild;
　　　　　　　　}
　　　　　　}
　　　　　　else
　　　　　　{
　　　　　　　　_head=newChild;
　　　　　　}
　　　　}
　　　　privatestaticboolIsBlack(Nodenode)
　　　　{
　　　　　　return((node!=null)&&!node.IsRed);
　　　　}
　　　　privatestaticboolIsNullOrBlack(Nodenode)
　　　　{
　　　　　　if(node!=null)
　　　　　　{
　　　　　　　　return!node.IsRed;
　　　　　　}
　　　　　　returntrue;
　　　　}
　　　　privatestaticboolIsRed(Nodenode)
　　　　{
　　　　　　return((node!=null)&&node.IsRed);
　　　　}
　　　　//删除指定值
　　　　publicboolRemove(intvalue)
　　　　{
　　　　　　p=-1;
　　　　　　//parent表示双亲结点，node表示当前结点
　　　　　　Nodenode=_head;
　　　　　　//寻找指定值所在的结点
　　　　　　while(node!=null)
　　　　　　{
　　　　　　　　path[++p]=node;
　　　　　　　　//如果找到，则调用RemoveNode方法删除结点
　　　　　　　　if(value==node.Data)
　　　　　　　　{
　　　　　　　　　　RemoveNode(node);//现在p指向被删除结点
　　　　　　　　　　returntrue;//返回true表示删除成功
　　　　　　　　}
　　　　　　　　if(value<node.Data)
　　　　　　　　{　//如果删除值小于当前结点，则向左子树继续寻找
　　　　　　　　　　node=node.Left;
　　　　　　　　}
　　　　　　　　else
　　　　　　　　{　//如果删除值大于当前结点，则向右子树继续寻找
　　　　　　　　　　node=node.Right;
　　　　　　　　}
　　　　　　}
　　　　　　returnfalse;//返回false表示删除失败
　　　　}
　　　　//删除指定结点
　　　　privatevoidRemoveNode(Nodenode)
　　　　{
　　　　　　Nodetmp=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;
　　　　　　}
　　　　　　//当只有左子树或右子树或为叶子结点时
　　　　　　//首先找到惟一的孩子结点
　　　　　　NodenewTmp=tmp.Left;
　　　　　　if(newTmp==null)//如果只有右孩子或没孩子
　　　　　　　{
　　　　　　　　newTmp=tmp.Right;
　　　　　　}
　　　　　　if(p>0)
　　　　　　{
　　　　　　　　Nodeparent=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)
　　　　　　{　//剩下的是双黑的情况
　　　　　　　　//首先找到兄弟结点
　　　　　　　　Nodecurrent=path[p];
　　　　　　　　Nodeparent=path[p-1];
　　　　　　　　boolcurrentIsLeft=(parent.Left==current);
　　　　　　　　Nodesibling=currentIsLeft?parent.Right:parent.Left;
　　　　　　　　//红兄的情况，需要LL旋转或RR旋转
　　　　　　　　if(IsRed(sibling))
　　　　　　　　{
　　　　　　　　　　NodenewRoot;
　　　　　　　　　　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//黑兄红侄
　　　　　　　　　　{
　　　　　　　　　　　　NodenewRoot;
　　　　　　　　　　　　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为旋转根双亲结点
　　　　privateNodeLL(Noderoot)//LL型旋转，返回旋转后的新子树根
　　　　{
　　　　　　Nodeleft=root.Left;
　　　　　　root.Left=left.Right;
　　　　　　left.Right=root;
　　　　　　returnleft;
　　　　}
　　　　privateNodeLR(Noderoot)//LR型旋转，返回旋转后的新子树根
　　　　{
　　　　　　Nodeleft=root.Left;
　　　　　　Noderight=left.Right;
　　　　　　root.Left=right.Right;
　　　　　　right.Right=root;
　　　　　　left.Right=right.Left;
　　　　　　right.Left=left;
　　　　　　returnright;
　　　　}
　　　　privateNodeRR(Noderoot)//RR型旋转，返回旋转后的新子树根
　　　　{
　　　　　　Noderight=root.Right;
　　　　　　root.Right=right.Left;
　　　　　　right.Left=root;
　　　　　　returnright;
　　　　}
　　　　privateNodeRL(Noderoot)//RL型旋转，返回旋转后的新子树根
　　　　{
　　　　　　Noderight=root.Right;
　　　　　　Nodeleft=right.Left;
　　　　　　root.Right=left.Left;
　　　　　　left.Left=root;
　　　　　　right.Left=left.Right;
　　　　　　left.Right=right;
　　　　　　returnleft;
　　　　}
　　}
}

　　完成红黑树后，做了一个比较粗糙的测试程序，对我自己实现的红黑树RBTree，C#类库中的红黑树TreeSet和我自己实现的AVL树AVLTree进行了简单的测试，为了公平起见，我把TreeSet改成了整型版，这样大家都站在了同一起跑线上。考虑到垃圾回收，这样的测试并不是很精确、科学，但也能说明一些问题。以后我会专门写程序对各种常见的查找数据结构进行测试

　　测试结果基本证实了我的想法，惟一意外的是AVL树有两个项目输给了RBTree。在理论上，RBTree在某些方面的确是比AVL树更为优秀，但从程序员的角度来说，红黑树的实现需要调用大量方法，比如结点颜色的判断，这会抵消红黑树的性能优势。国外网站也有针对红黑树和AVL树的测试，结果基本上是AVL树胜出。

　　红黑树的动画还有一些bug，整体效果也不尽如人意，我也懒得再改了，写它比写红黑树困难些。写它主要是为了学习Silverlight，这也算是第一个Silverlight动画作品，东西弄懂了就不想再动了。打算将来更深入地了解Silverlight后再全面修改这个动画。