看了一下算法导论，纸上得来终觉浅，绝知此事要躬行，所以把感兴趣的算法就写了下。
红黑树在插入，删除，查找过程中都可以保持较高的运行效率，sharpdevelop 中自定义的代码编辑控件中的document模型就是运用了红黑树。
RedBlackTree.cs
using System;
namespace Cn.Linc.Algorithms.BasicStructure
{
public enum NodeColor
{
Black,
Red
}
/// <summary>
/// A binary search tree is a red-black tree if it satisfies the following red-black properties:
/// 1) Every node is either red or black.
/// 2) The root is black.
/// 3) Every leaf (NIL) is black.
/// 4) If a node is red, then both its children are black.
/// 5) For each node, all paths from the node to descendant leaves contain the same number of black nodes.
///
/// Red-black trees are one of many search-tree schemes that are "balanced" in order to
/// guarantee that basic dynamic-set operations take O(lg n) time in the worst case.
///
/// Notice, a null leaf node or parent node is colored black.
///
/// More details please find in chapter 13, Introduction to Algorithms, Second Edition
/// by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein ISBN:0262032937
/// The MIT Press © 2001 (1180 pages)
/// </summary>
/// <typeparam name="T">RedBlackTreeNode type</typeparam>
/// <typeparam name="S">IComparable type</typeparam>
public class RedBlackTree<T,S>
where T: RedBlackTreeNode<S>
where S: IComparable
{
private RedBlackTreeNode<S> root;
/// <summary>
/// Insert a new node, at first initialize the new node as red to keep the black height
/// rule of red black tree. Insert the new node to proper position accordding to its value,
/// the fix the tree according to the defination of red black tree.
/// </summary>
/// <param name="nodeValue"></param>
public void InsertNode(S nodeValue)
{
RedBlackTreeNode<S> newNode = new RedBlackTreeNode<S>(nodeValue);
if (root == null)
{
root = newNode;
}
else
{
RedBlackTreeNode<S> tempX = root;
RedBlackTreeNode<S> tempY = null;
while (tempX != null)
{
tempY = tempX;
tempX = nodeValue.CompareTo(tempX.Value) > 0 ? tempX.RightChild : tempX.LeftChild;
}
if (nodeValue.CompareTo(tempY.Value) >= 0)
{
tempY.RightChild = newNode;
}
else
{
tempY.LeftChild = newNode;
}
}
InsertFixup(newNode);
}
/// <summary>
/// Delete node.
/// If the node only have one or no child, just delete it.
/// If the node has both left and right children, find its successor, delete it and copy its
/// value to the node to be deleted.
/// After deleting, fix up the tree according to defination.
/// </summary>
/// <param name="node"></param>
public void DeleteNode(T node)
{
if (node == null)
return;
if ((node == root) && (root.RightChild == null) && (root.LeftChild == null))
{
root = null;
return;
}
RedBlackTreeNode<S> tempX = null, tempY = null;
if (node.LeftChild == null || node.RightChild == null)
{
tempY = node;
}
else
{
tempY = GetSuccessor(node);
}
tempX = (tempY.LeftChild != null) ? tempY.LeftChild : tempY.RightChild;
if (tempY.ParentNode == null)
root = tempX;
else
{
if (tempY == tempY.ParentNode.LeftChild)
{
tempY.ParentNode.LeftChild = tempX;
}
else
{
tempY.ParentNode.RightChild = tempX;
}
}
if (tempY != node)
{
node.Value = tempY.Value;
}
// if black node is deleted the black height rule must be violated, fix it.
if (tempY.Color == NodeColor.Black)
DeleteFixup(tempX,tempY.ParentNode);
}
/// <summary>
/// Find the node with specified value.
/// </summary>
/// <param name="value">specified value</param>
/// <returns></returns>
public RedBlackTreeNode<S> FindNode(S value)
{
RedBlackTreeNode<S> temp = root;
if (root == null)
{
return null;
}
do
{
if(value.CompareTo(temp.Value)==0)
{
return temp;
}
else if (temp.LeftChild != null && value.CompareTo(temp.Value) < 0)
{
temp = temp.LeftChild;
}
else if (temp.RightChild != null && value.CompareTo(temp.Value) > 0)
{
temp = temp.RightChild;
}
else
{
return null;
}
} while (true);
}
/// <summary>
/// Find the successer of specific node,
/// if the right child is not empty, the successor is the far left node of the subtree.
/// If it has a successor and its right child is null, the successor must be the nearest
/// ancestor, and the left child of the successor is ancestor of the specific node.
/// </summary>
/// <param name="currentNode">the specific node </param>
/// <returns></returns>
private RedBlackTreeNode<S> GetSuccessor(RedBlackTreeNode<S> currentNode)
{
RedBlackTreeNode<S> temp = null;
if (currentNode.RightChild != null)
{
temp = currentNode.RightChild;
while (temp.LeftChild != null)
{
temp = temp.LeftChild;
}
return temp;
}
else
{
while (temp.ParentNode != null)
{
if (temp == temp.ParentNode.LeftChild)
{
return temp.ParentNode;
}
else
{
temp = temp.ParentNode;
}
}
return null;
}
}
/// <summary>
/// Fix up red black tree after inserting node. Three cases:
/// 1) the uncle of the node is red;
/// 2) the uncle of the node is black and the node is right child(left rotate to case 3);
/// 3) the uncle of the node is black and the node is left child;
/// </summary>
/// <param name="node"></param>
private void InsertFixup(RedBlackTreeNode<S> node)
{
RedBlackTreeNode<S> temp = null;
while (node != root && node.ParentNode.Color == NodeColor.Red)
{
if (node.ParentNode == node.ParentNode.ParentNode.LeftChild)
{
temp = node.ParentNode.ParentNode.RightChild;
if (temp != null && temp.Color == NodeColor.Red)
{
node.ParentNode.Color = NodeColor.Black;
temp.Color = NodeColor.Black;
node.ParentNode.ParentNode.Color = NodeColor.Red;
node = node.ParentNode.ParentNode;
}
else
{
if (node == node.ParentNode.RightChild)
{
node = node.ParentNode;
LeftRotate(node);
}
node.ParentNode.Color = NodeColor.Black;
node.ParentNode.ParentNode.Color = NodeColor.Red;
RightRotate(node.ParentNode.ParentNode);
}
}
else
{
temp = node.ParentNode.ParentNode.LeftChild;
if (temp != null && temp.Color == NodeColor.Red)
{
node.ParentNode.Color = NodeColor.Black;
temp.Color = NodeColor.Black;
node.ParentNode.ParentNode.Color = NodeColor.Red;
node = node.ParentNode.ParentNode;
}
else
{
if (node == node.ParentNode.LeftChild)
{
node = node.ParentNode;
RightRotate(node);
}
node.ParentNode.Color = NodeColor.Black;
node.ParentNode.ParentNode.Color = NodeColor.Red;
LeftRotate(node.ParentNode.ParentNode);
}
}
}
root.Color = NodeColor.Black;
}
/// <summary>
/// Fix up tree property after delete node from tree
/// 1) node's sibling w is red;
/// 2) node's sibling w is black, and both of w's children are black;
/// 3) node's sibling w is black, w's left child is red, and w's right child is black;
/// 4) node's sibling w is black, and w's right child is red
/// </summary>
/// <param name="node"></param>
private void DeleteFixup(RedBlackTreeNode<S> node,RedBlackTreeNode<S> parentNode)
{
RedBlackTreeNode<S> tempX = null;
while (node != root && (node == null||node.Color == NodeColor.Black))
{
if (node == parentNode.LeftChild)
{
tempX = parentNode.RightChild;
if (tempX != null && tempX.Color == NodeColor.Red)
{
tempX.Color = NodeColor.Black;
node.ParentNode.Color = NodeColor.Red;
LeftRotate(node.ParentNode);
}
else
{
if ((tempX.LeftChild == null && tempX.RightChild == null)
|| (tempX.LeftChild.Color == NodeColor.Black && tempX.RightChild.Color == NodeColor.Black))
{
tempX.Color = NodeColor.Red;
node = parentNode;
parentNode = node.ParentNode;
}
else
{
if (tempX.RightChild == null || tempX.RightChild.Color == NodeColor.Black)
{
if (tempX.RightChild != null)
{
tempX.LeftChild.Color = NodeColor.Black;
tempX.Color = NodeColor.Red;
}
RightRotate(tempX);
tempX = parentNode.RightChild;
}
tempX.Color = parentNode.Color;
parentNode.Color = NodeColor.Black;
tempX.RightChild.Color = NodeColor.Black;
LeftRotate(parentNode);
node = root;
}
}
}
else
{
tempX = parentNode.LeftChild;
if (tempX != null && tempX.Color == NodeColor.Red)
{
tempX.Color = NodeColor.Black;
parentNode.Color = NodeColor.Red;
RightRotate(parentNode);
}
else
{
if ((tempX.LeftChild == null && tempX.RightChild == null)
|| (tempX.LeftChild.Color == NodeColor.Black && tempX.RightChild.Color == NodeColor.Black))
{
tempX.Color = NodeColor.Red;
node = parentNode;
parentNode = node.ParentNode;
}
else
{
if (tempX.RightChild == null || tempX.RightChild.Color == NodeColor.Black)
{
if (tempX.RightChild != null)
{
tempX.RightChild.Color = NodeColor.Black;
tempX.Color = NodeColor.Red;
}
LeftRotate(tempX);
tempX = parentNode.LeftChild;
}
tempX.Color = parentNode.Color;
parentNode.Color = NodeColor.Black;
tempX.LeftChild.Color = NodeColor.Black;
RightRotate(parentNode);
node = root;
}
}
}
}
node.Color = NodeColor.Black;
}
/// <summary>
/// Right rotate the node, used when fix up tree property
/// </summary>
/// <param name="node"></param>
private void RightRotate(RedBlackTreeNode<S> node)
{
if (node.LeftChild == null)
return;
RedBlackTreeNode<S> child = node.LeftChild;
if (node.ParentNode != null)
{
if (node.ParentNode.LeftChild != null && node.ParentNode.LeftChild == node)
{
node.ParentNode.LeftChild = child;
}
else
{
node.ParentNode.RightChild = child;
}
}
else
{
node.LeftChild.ParentNode = null;
}
node.LeftChild = child.RightChild;
child.RightChild = node;
RecheckRoot();
}
/// <summary>
/// Left rotate the node, used when fix up tree property
/// </summary>
/// <param name="node"></param>
private void LeftRotate(RedBlackTreeNode<S> node)
{
if (node.RightChild == null)
return;
RedBlackTreeNode<S> child = node.RightChild;
if (node.ParentNode != null)
{
if (node.ParentNode.LeftChild != null && node.ParentNode.LeftChild == node)
{
node.ParentNode.LeftChild = child;
}
else
{
node.ParentNode.RightChild = child;
}
}
else
{
node.RightChild.ParentNode = null;
}
node.RightChild = child.LeftChild;
child.LeftChild = node;
RecheckRoot();
}
/// <summary>
/// the rotation may change the root, check and reset the root node.
/// </summary>
private void RecheckRoot()
{
while (root.ParentNode != null)
{
root = root.ParentNode;
}
}
}
}
namespace Cn.Linc.Algorithms.BasicStructure
{
public enum NodeColor
{
Black,
Red
}
/// <summary>
/// A binary search tree is a red-black tree if it satisfies the following red-black properties:
/// 1) Every node is either red or black.
/// 2) The root is black.
/// 3) Every leaf (NIL) is black.
/// 4) If a node is red, then both its children are black.
/// 5) For each node, all paths from the node to descendant leaves contain the same number of black nodes.
///
/// Red-black trees are one of many search-tree schemes that are "balanced" in order to
/// guarantee that basic dynamic-set operations take O(lg n) time in the worst case.
///
/// Notice, a null leaf node or parent node is colored black.
///
/// More details please find in chapter 13, Introduction to Algorithms, Second Edition
/// by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein ISBN:0262032937
/// The MIT Press © 2001 (1180 pages)
/// </summary>
/// <typeparam name="T">RedBlackTreeNode type</typeparam>
/// <typeparam name="S">IComparable type</typeparam>
public class RedBlackTree<T,S>
where T: RedBlackTreeNode<S>
where S: IComparable
{
private RedBlackTreeNode<S> root;
/// <summary>
/// Insert a new node, at first initialize the new node as red to keep the black height
/// rule of red black tree. Insert the new node to proper position accordding to its value,
/// the fix the tree according to the defination of red black tree.
/// </summary>
/// <param name="nodeValue"></param>
public void InsertNode(S nodeValue)
{
RedBlackTreeNode<S> newNode = new RedBlackTreeNode<S>(nodeValue);
if (root == null)
{
root = newNode;
}
else
{
RedBlackTreeNode<S> tempX = root;
RedBlackTreeNode<S> tempY = null;
while (tempX != null)
{
tempY = tempX;
tempX = nodeValue.CompareTo(tempX.Value) > 0 ? tempX.RightChild : tempX.LeftChild;
}
if (nodeValue.CompareTo(tempY.Value) >= 0)
{
tempY.RightChild = newNode;
}
else
{
tempY.LeftChild = newNode;
}
}
InsertFixup(newNode);
}
/// <summary>
/// Delete node.
/// If the node only have one or no child, just delete it.
/// If the node has both left and right children, find its successor, delete it and copy its
/// value to the node to be deleted.
/// After deleting, fix up the tree according to defination.
/// </summary>
/// <param name="node"></param>
public void DeleteNode(T node)
{
if (node == null)
return;
if ((node == root) && (root.RightChild == null) && (root.LeftChild == null))
{
root = null;
return;
}
RedBlackTreeNode<S> tempX = null, tempY = null;
if (node.LeftChild == null || node.RightChild == null)
{
tempY = node;
}
else
{
tempY = GetSuccessor(node);
}
tempX = (tempY.LeftChild != null) ? tempY.LeftChild : tempY.RightChild;
if (tempY.ParentNode == null)
root = tempX;
else
{
if (tempY == tempY.ParentNode.LeftChild)
{
tempY.ParentNode.LeftChild = tempX;
}
else
{
tempY.ParentNode.RightChild = tempX;
}
}
if (tempY != node)
{
node.Value = tempY.Value;
}
// if black node is deleted the black height rule must be violated, fix it.
if (tempY.Color == NodeColor.Black)
DeleteFixup(tempX,tempY.ParentNode);
}
/// <summary>
/// Find the node with specified value.
/// </summary>
/// <param name="value">specified value</param>
/// <returns></returns>
public RedBlackTreeNode<S> FindNode(S value)
{
RedBlackTreeNode<S> temp = root;
if (root == null)
{
return null;
}
do
{
if(value.CompareTo(temp.Value)==0)
{
return temp;
}
else if (temp.LeftChild != null && value.CompareTo(temp.Value) < 0)
{
temp = temp.LeftChild;
}
else if (temp.RightChild != null && value.CompareTo(temp.Value) > 0)
{
temp = temp.RightChild;
}
else
{
return null;
}
} while (true);
}
/// <summary>
/// Find the successer of specific node,
/// if the right child is not empty, the successor is the far left node of the subtree.
/// If it has a successor and its right child is null, the successor must be the nearest
/// ancestor, and the left child of the successor is ancestor of the specific node.
/// </summary>
/// <param name="currentNode">the specific node </param>
/// <returns></returns>
private RedBlackTreeNode<S> GetSuccessor(RedBlackTreeNode<S> currentNode)
{
RedBlackTreeNode<S> temp = null;
if (currentNode.RightChild != null)
{
temp = currentNode.RightChild;
while (temp.LeftChild != null)
{
temp = temp.LeftChild;
}
return temp;
}
else
{
while (temp.ParentNode != null)
{
if (temp == temp.ParentNode.LeftChild)
{
return temp.ParentNode;
}
else
{
temp = temp.ParentNode;
}
}
return null;
}
}
/// <summary>
/// Fix up red black tree after inserting node. Three cases:
/// 1) the uncle of the node is red;
/// 2) the uncle of the node is black and the node is right child(left rotate to case 3);
/// 3) the uncle of the node is black and the node is left child;
/// </summary>
/// <param name="node"></param>
private void InsertFixup(RedBlackTreeNode<S> node)
{
RedBlackTreeNode<S> temp = null;
while (node != root && node.ParentNode.Color == NodeColor.Red)
{
if (node.ParentNode == node.ParentNode.ParentNode.LeftChild)
{
temp = node.ParentNode.ParentNode.RightChild;
if (temp != null && temp.Color == NodeColor.Red)
{
node.ParentNode.Color = NodeColor.Black;
temp.Color = NodeColor.Black;
node.ParentNode.ParentNode.Color = NodeColor.Red;
node = node.ParentNode.ParentNode;
}
else
{
if (node == node.ParentNode.RightChild)
{
node = node.ParentNode;
LeftRotate(node);
}
node.ParentNode.Color = NodeColor.Black;
node.ParentNode.ParentNode.Color = NodeColor.Red;
RightRotate(node.ParentNode.ParentNode);
}
}
else
{
temp = node.ParentNode.ParentNode.LeftChild;
if (temp != null && temp.Color == NodeColor.Red)
{
node.ParentNode.Color = NodeColor.Black;
temp.Color = NodeColor.Black;
node.ParentNode.ParentNode.Color = NodeColor.Red;
node = node.ParentNode.ParentNode;
}
else
{
if (node == node.ParentNode.LeftChild)
{
node = node.ParentNode;
RightRotate(node);
}
node.ParentNode.Color = NodeColor.Black;
node.ParentNode.ParentNode.Color = NodeColor.Red;
LeftRotate(node.ParentNode.ParentNode);
}
}
}
root.Color = NodeColor.Black;
}
/// <summary>
/// Fix up tree property after delete node from tree
/// 1) node's sibling w is red;
/// 2) node's sibling w is black, and both of w's children are black;
/// 3) node's sibling w is black, w's left child is red, and w's right child is black;
/// 4) node's sibling w is black, and w's right child is red
/// </summary>
/// <param name="node"></param>
private void DeleteFixup(RedBlackTreeNode<S> node,RedBlackTreeNode<S> parentNode)
{
RedBlackTreeNode<S> tempX = null;
while (node != root && (node == null||node.Color == NodeColor.Black))
{
if (node == parentNode.LeftChild)
{
tempX = parentNode.RightChild;
if (tempX != null && tempX.Color == NodeColor.Red)
{
tempX.Color = NodeColor.Black;
node.ParentNode.Color = NodeColor.Red;
LeftRotate(node.ParentNode);
}
else
{
if ((tempX.LeftChild == null && tempX.RightChild == null)
|| (tempX.LeftChild.Color == NodeColor.Black && tempX.RightChild.Color == NodeColor.Black))
{
tempX.Color = NodeColor.Red;
node = parentNode;
parentNode = node.ParentNode;
}
else
{
if (tempX.RightChild == null || tempX.RightChild.Color == NodeColor.Black)
{
if (tempX.RightChild != null)
{
tempX.LeftChild.Color = NodeColor.Black;
tempX.Color = NodeColor.Red;
}
RightRotate(tempX);
tempX = parentNode.RightChild;
}
tempX.Color = parentNode.Color;
parentNode.Color = NodeColor.Black;
tempX.RightChild.Color = NodeColor.Black;
LeftRotate(parentNode);
node = root;
}
}
}
else
{
tempX = parentNode.LeftChild;
if (tempX != null && tempX.Color == NodeColor.Red)
{
tempX.Color = NodeColor.Black;
parentNode.Color = NodeColor.Red;
RightRotate(parentNode);
}
else
{
if ((tempX.LeftChild == null && tempX.RightChild == null)
|| (tempX.LeftChild.Color == NodeColor.Black && tempX.RightChild.Color == NodeColor.Black))
{
tempX.Color = NodeColor.Red;
node = parentNode;
parentNode = node.ParentNode;
}
else
{
if (tempX.RightChild == null || tempX.RightChild.Color == NodeColor.Black)
{
if (tempX.RightChild != null)
{
tempX.RightChild.Color = NodeColor.Black;
tempX.Color = NodeColor.Red;
}
LeftRotate(tempX);
tempX = parentNode.LeftChild;
}
tempX.Color = parentNode.Color;
parentNode.Color = NodeColor.Black;
tempX.LeftChild.Color = NodeColor.Black;
RightRotate(parentNode);
node = root;
}
}
}
}
node.Color = NodeColor.Black;
}
/// <summary>
/// Right rotate the node, used when fix up tree property
/// </summary>
/// <param name="node"></param>
private void RightRotate(RedBlackTreeNode<S> node)
{
if (node.LeftChild == null)
return;
RedBlackTreeNode<S> child = node.LeftChild;
if (node.ParentNode != null)
{
if (node.ParentNode.LeftChild != null && node.ParentNode.LeftChild == node)
{
node.ParentNode.LeftChild = child;
}
else
{
node.ParentNode.RightChild = child;
}
}
else
{
node.LeftChild.ParentNode = null;
}
node.LeftChild = child.RightChild;
child.RightChild = node;
RecheckRoot();
}
/// <summary>
/// Left rotate the node, used when fix up tree property
/// </summary>
/// <param name="node"></param>
private void LeftRotate(RedBlackTreeNode<S> node)
{
if (node.RightChild == null)
return;
RedBlackTreeNode<S> child = node.RightChild;
if (node.ParentNode != null)
{
if (node.ParentNode.LeftChild != null && node.ParentNode.LeftChild == node)
{
node.ParentNode.LeftChild = child;
}
else
{
node.ParentNode.RightChild = child;
}
}
else
{
node.RightChild.ParentNode = null;
}
node.RightChild = child.LeftChild;
child.LeftChild = node;
RecheckRoot();
}
/// <summary>
/// the rotation may change the root, check and reset the root node.
/// </summary>
private void RecheckRoot()
{
while (root.ParentNode != null)
{
root = root.ParentNode;
}
}
}
}
RedBlackTreeNode.cs
using System;
namespace Cn.Linc.Algorithms.BasicStructure
{
public class RedBlackTreeNode<T> where T : IComparable
{
private T value;
public T Value
{
get { return this.value; }
set { this.value = value; }
}
private NodeColor color;
public NodeColor Color
{
get { return color; }
set { color = value; }
}
private RedBlackTreeNode<T> leftChild;
public RedBlackTreeNode<T> LeftChild
{
get { return leftChild; }
set
{
if (value != null)
value.ParentNode = this;
leftChild = value;
}
}
private RedBlackTreeNode<T> rightChild;
public RedBlackTreeNode<T> RightChild
{
get { return rightChild; }
set
{
if (value != null)
value.ParentNode = this;
rightChild = value;
}
}
private RedBlackTreeNode<T> parentNode;
public RedBlackTreeNode<T> ParentNode
{
get { return parentNode; }
set { parentNode = value; }
}
public RedBlackTreeNode(T nodeValue)
{
value = nodeValue;
color = NodeColor.Red;
}
}
}
namespace Cn.Linc.Algorithms.BasicStructure
{
public class RedBlackTreeNode<T> where T : IComparable
{
private T value;
public T Value
{
get { return this.value; }
set { this.value = value; }
}
private NodeColor color;
public NodeColor Color
{
get { return color; }
set { color = value; }
}
private RedBlackTreeNode<T> leftChild;
public RedBlackTreeNode<T> LeftChild
{
get { return leftChild; }
set
{
if (value != null)
value.ParentNode = this;
leftChild = value;
}
}
private RedBlackTreeNode<T> rightChild;
public RedBlackTreeNode<T> RightChild
{
get { return rightChild; }
set
{
if (value != null)
value.ParentNode = this;
rightChild = value;
}
}
private RedBlackTreeNode<T> parentNode;
public RedBlackTreeNode<T> ParentNode
{
get { return parentNode; }
set { parentNode = value; }
}
public RedBlackTreeNode(T nodeValue)
{
value = nodeValue;
color = NodeColor.Red;
}
}
}