红黑树C#算法。
在线javascript演示地址：http://sandbox.runjs.cn/show/2nngvn8w
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.Threading;
using System.IO;
using System.Collections; namespace ConsoleApplication2
{
public class Program
{
public static void Main()
{
int[] a = {,,,,,,,,}; RBTree<int> rbTree = new RBTree<int>();
foreach (var item in a)
{
rbTree.Insert(item);
}
rbTree.Remove(); rbTree.PreOrder(t => Console.Write(t.ToString()+" ")); Console.Read();
}
} #region 实体
public enum NodeColor
{
Black,
Red
} public class RBTreeNode<T> where T : IComparable
{
public T Key { get; set; }
public NodeColor Color { get; set; }
public RBTreeNode<T> Parent { get; set; }
public RBTreeNode<T> LeftNode { get; set; }
public RBTreeNode<T> RightNode { get; set; } public RBTreeNode(T key, NodeColor color, RBTreeNode<T> parent, RBTreeNode<T> leftNode, RBTreeNode<T> rightNode)
{
this.Key = key;
this.Color = color;
this.Parent = parent;
this.LeftNode = leftNode;
this.RightNode = rightNode;
} public override string ToString()
{
return this.Key + "(" + Color.ToString() + ")";
}
}
#endregion public class RBTree<T> where T : IComparable
{
public RBTreeNode<T> RootNode { get; set; }//根节点 #region 插入
public void Insert(T key)
{
if (this.RootNode == null)
{
this.RootNode = new RBTreeNode<T>(key, NodeColor.Black, null, null, null);
}
else
{
var newNode = Inserts(key);
InsertFixUp(newNode);
}
} private RBTreeNode<T> Inserts(T key)
{
var node = RootNode; var newNode = new RBTreeNode<T>(key, NodeColor.Red, null, null, null);
while (true)
{
if (key.CompareTo(node.Key) > )
{
if (node.RightNode == null)
{
newNode.Parent = node;
node.RightNode = newNode;
break;
}
node = node.RightNode;
}
else if (key.CompareTo(node.Key) < )
{
if (node.LeftNode == null)
{
newNode.Parent = node;
node.LeftNode = newNode;
break;
}
node = node.LeftNode;
}
else
{
break;
}
}
return newNode;
} private void InsertFixUp(RBTreeNode<T> node)
{
var parentNode = node.Parent;
if (parentNode != null && NodeColor.Red == parentNode.Color)
{
var gparentNode = parentNode.Parent;
if (parentNode == gparentNode.LeftNode)
{
var uncleNode = gparentNode.RightNode;
if (uncleNode != null && NodeColor.Red == uncleNode.Color)//case1
{
parentNode.Color = NodeColor.Black;
uncleNode.Color = NodeColor.Black;
gparentNode.Color = NodeColor.Red;
InsertFixUp(gparentNode);
}
else
{
if (parentNode.RightNode == node)//case2
{
LeftRotation(parentNode);
InsertFixUp(parentNode);
}
else if (parentNode.LeftNode == node)//case3
{
parentNode.Color = NodeColor.Black;
gparentNode.Color = NodeColor.Red;
RightRotion(gparentNode);
}
}
}
else
{
var uncleNode = gparentNode.LeftNode;
if (uncleNode != null && NodeColor.Red == uncleNode.Color)//case1
{
parentNode.Color = NodeColor.Black;
uncleNode.Color = NodeColor.Black;
gparentNode.Color = NodeColor.Red;
InsertFixUp(gparentNode);
}
else
{
if (parentNode.LeftNode == node)//case2
{
RightRotion(parentNode);
InsertFixUp(parentNode);
}
else if (parentNode.RightNode == node)//case3
{
parentNode.Color = NodeColor.Black;
gparentNode.Color = NodeColor.Red;
LeftRotation(gparentNode);
}
}
}
}
RootNode.Color = NodeColor.Black; //直接将根节点设置为黑色
}
#endregion #region 旋转
private void LeftRotation(RBTreeNode<T> node)
{
RBTreeNode<T> temp = node.RightNode; node.RightNode = temp.LeftNode;
if (temp.LeftNode != null)
{
temp.LeftNode.Parent = node;
} temp.Parent = node.Parent; if (node.Parent == null)
{
RootNode = temp;
}
else
{
if (node.Parent.LeftNode == node)
{
node.Parent.LeftNode = temp;
}
else
{
node.Parent.RightNode = temp;
}
}
temp.LeftNode = node;
node.Parent = temp;
} private void RightRotion(RBTreeNode<T> node)
{
RBTreeNode<T> temp = node.LeftNode; node.LeftNode = temp.RightNode;
if (temp.RightNode != null)
{
temp.RightNode.Parent = node;
} temp.Parent = node.Parent; if (node.Parent == null)
{
RootNode = temp;
}
else
{
if (node == node.Parent.RightNode)
{
node.Parent.RightNode = temp;
}
else
{
node.Parent.LeftNode = temp;
}
}
temp.RightNode = node;
node.Parent = temp;
}
#endregion #region 删除
public void Remove(T key)
{
RBTreeNode<T> node = Search(key);
if (node == null)
{
return;
}
else
{
Remove(node);
}
} private void Remove(RBTreeNode<T> itWasDeletedNode)
{
RBTreeNode<T> child;
RBTreeNode<T> parent;
NodeColor nodeColor; if (itWasDeletedNode.LeftNode != null && itWasDeletedNode.RightNode != null)
{
var tempNode = this.FindMin(itWasDeletedNode.RightNode);
if (itWasDeletedNode.Parent == null)
{
this.RootNode = tempNode;
}
else
{
if (itWasDeletedNode.Parent.LeftNode.Key.CompareTo(itWasDeletedNode.Key) == )
{
itWasDeletedNode.Parent.LeftNode = tempNode;
}
else
{
itWasDeletedNode.Parent.RightNode = tempNode;
}
} child = tempNode.RightNode;
parent = tempNode.Parent;
nodeColor = tempNode.Color; if (parent.Key.CompareTo(itWasDeletedNode.Key) == )
{
parent = tempNode;
}
else
{
if (child != null)
{
child.Parent = parent;
}
parent.LeftNode = child; tempNode.RightNode = itWasDeletedNode.RightNode;
itWasDeletedNode.RightNode.Parent = tempNode;
} tempNode.Parent = itWasDeletedNode.Parent;
tempNode.Color = itWasDeletedNode.Color;
tempNode.LeftNode = itWasDeletedNode.LeftNode;
itWasDeletedNode.LeftNode.Parent = tempNode; if (nodeColor == NodeColor.Black)
{
RemoveFixUp(child, parent);
} itWasDeletedNode = null;
return;
} if (itWasDeletedNode.LeftNode != null)
{
child = itWasDeletedNode.LeftNode;
}
else
{
child = itWasDeletedNode.RightNode;
} parent = itWasDeletedNode.Parent;
nodeColor = itWasDeletedNode.Color; if (child != null)
{
child.Parent = parent;
} if (parent != null)
{
if (parent.LeftNode != null && parent.LeftNode.Key.CompareTo(itWasDeletedNode.Key) == )
{
parent.LeftNode = child;
}
else
{
parent.RightNode = child;
}
}
else
{
this.RootNode = child;
} if (nodeColor == NodeColor.Black)
{
RemoveFixUp(child, parent);
}
itWasDeletedNode = null;
} private void RemoveFixUp(RBTreeNode<T> node, RBTreeNode<T> parentNode)
{
RBTreeNode<T> otherNode; while ((node == null || node.Color == NodeColor.Black) && (node != this.RootNode))
{
if (parentNode.LeftNode == node)
{
otherNode = parentNode.RightNode;
if (otherNode.Color == NodeColor.Red)
{
otherNode.Color = NodeColor.Black;
parentNode.Color = NodeColor.Red;
LeftRotation(parentNode);
otherNode = parentNode.RightNode;
} if ((otherNode.LeftNode == null || otherNode.LeftNode.Color == NodeColor.Black) &&
(otherNode.RightNode == null || otherNode.RightNode.Color == NodeColor.Black))
{
otherNode.Color = NodeColor.Red;
node = parentNode;
parentNode = node.Parent;
}
else
{
if (otherNode.RightNode == null || otherNode.RightNode.Color == NodeColor.Black)
{
otherNode.LeftNode.Color = NodeColor.Black;
otherNode.Color = NodeColor.Red;
RightRotion(otherNode);
otherNode = parentNode.RightNode;
} otherNode.Color = parentNode.Color;
parentNode.Color = NodeColor.Black;
otherNode.RightNode.Color = NodeColor.Black;
LeftRotation(parentNode);
node = this.RootNode;
break;
}
}
else
{
otherNode = parentNode.LeftNode;
if (otherNode.Color == NodeColor.Red)
{
otherNode.Color = NodeColor.Black;
parentNode.Color = NodeColor.Red;
RightRotion(parentNode);
otherNode = parentNode.LeftNode;
} if ((otherNode.LeftNode == null || otherNode.LeftNode.Color == NodeColor.Black) &&
(otherNode.RightNode == null || otherNode.RightNode.Color == NodeColor.Black))
{
otherNode.Color = NodeColor.Red;
node = parentNode;
parentNode = node.Parent;
}
else
{
if (otherNode.LeftNode == null || otherNode.LeftNode.Color == NodeColor.Black)
{
otherNode.RightNode.Color = NodeColor.Black;
otherNode.Color = NodeColor.Red;
LeftRotation(otherNode);
otherNode = parentNode.LeftNode;
} otherNode.Color = parentNode.Color;
parentNode.Color = NodeColor.Black;
otherNode.LeftNode.Color = NodeColor.Black;
RightRotion(parentNode);
node = this.RootNode;
break;
}
}
} if (node != null)
{
node.Color = NodeColor.Black;
}
}
#endregion #region 查找
public RBTreeNode<T> Search(T key)
{
return Search(RootNode, key);
} private RBTreeNode<T> Search(RBTreeNode<T> node, T key)
{
if (node == null)
{
return null;
} if (node.Key.CompareTo(key) > )
{
return Search(node.LeftNode, key);
}
else if (node.Key.CompareTo(key) < )
{
return Search(node.RightNode, key);
}
else
{
return node;
}
} public RBTreeNode<T> FindMin()
{
return FindMin(RootNode);
} private RBTreeNode<T> FindMin(RBTreeNode<T> node)
{
if (node.LeftNode == null)
{
return node;
}
return FindMin(node.LeftNode);
} public RBTreeNode<T> FindMax()
{
return FindMax(RootNode);
} private RBTreeNode<T> FindMax(RBTreeNode<T> node)
{
if (node.RightNode == null)
{
return node.RightNode;
} return FindMax(node.RightNode);
} public List<RBTreeNode<T>> SearchRange(T minKey, T maxKey)
{
return SearchRange(minKey,maxKey,this.RootNode,new List<RBTreeNode<T>>());
} private List<RBTreeNode<T>> SearchRange(T minKey, T maxKey, RBTreeNode<T> node,List<RBTreeNode<T>> nodeList)
{
if (node == null)
{
return nodeList;
} if (node.Key.CompareTo(minKey) > )
{
SearchRange(minKey,maxKey,node.LeftNode,nodeList);
} if (node.Key.CompareTo(minKey) >= && node.Key.CompareTo(maxKey) <= )
{
nodeList.Add(node);
} if (node.Key.CompareTo(maxKey) < )
{
SearchRange(minKey,maxKey,node.RightNode,nodeList);
} return nodeList;
}
#endregion #region 遍历
public void LevelOrder(Action<RBTreeNode<T>> action)
{
LevelOrder(RootNode, action);
} private void LevelOrder(RBTreeNode<T> note, Action<RBTreeNode<T>> action)
{
Queue<RBTreeNode<T>> queue = new Queue<RBTreeNode<T>>();
queue.Enqueue(note); while (queue.Count > )
{
var temp = queue.Dequeue(); action(temp); if (temp.LeftNode != null)
{
queue.Enqueue(temp.LeftNode);
} if (temp.RightNode != null)
{
queue.Enqueue(temp.RightNode);
}
}
} public void PreOrder(Action<RBTreeNode<T>> action)
{
TreeOrder(RootNode, preOrderAction: action);
} public void InOrder(Action<RBTreeNode<T>> action)
{
TreeOrder(RootNode, inOrderAction: action);
} public void PostOrderAction(Action<RBTreeNode<T>> action)
{
TreeOrder(RootNode, postOrderAction: action);
} private void TreeOrder(RBTreeNode<T> node, Action<RBTreeNode<T>> preOrderAction = null, Action<RBTreeNode<T>> inOrderAction = null, Action<RBTreeNode<T>> postOrderAction = null)
{
if (preOrderAction != null)
{
preOrderAction(node);
} if (node.LeftNode != null)
{
TreeOrder(node.LeftNode, preOrderAction, inOrderAction, postOrderAction);
} if (inOrderAction != null)
{
inOrderAction(node);
} if (node.RightNode != null)
{
TreeOrder(node.RightNode, preOrderAction, inOrderAction, postOrderAction);
} if (postOrderAction != null)
{
postOrderAction(node);
}
}
#endregion }
}
算法参考：http://www.cnblogs.com/skywang12345/p/3603935.html