我只是在对 RedBlack Tree 进行一些研究。我知道 .Net 4.0 中的 SortedSet 类使用 RedBlack 树。所以我像使用 Reflector 一样把这部分拿出来,并创建了一个 RedBlackTree 类。现在我在这个 RedBlackTree 和 SortedSet 上运行一些性能测试,插入 40000 个连续的整数值(从 0 到 39999),我很惊讶地发现性能差异很大,如下所示:
RBTree took 9.27208 sec to insert 40000 values
SortedSet took 0.0253097 sec to insert 40000 values
背后的原因是什么?顺便说一句,我只在发布配置中运行了测试,这里是小测试代码
var stopWatch = new Stopwatch();
var rbT = new RedBlackTree<int>();
stopWatch = new Stopwatch();
stopWatch.Start();
for (int i = 0; i < 40000; i++) {
rbT.Add(i);
}
stopWatch.Stop();
Console.WriteLine(stopWatch.Elapsed);
var ss = new SortedSet<int>();
stopWatch = new Stopwatch();
stopWatch.Start();
for (int i = 0; i < 40000; i++) {
ss.Add(i);
}
stopWatch.Stop();
Console.WriteLine(stopWatch.Elapsed);
编辑
我还想分享我提取的 RBTree 代码,以便您也可以运行诊断程序
public class Node<T>
{
public Node(){}
public Node(T value)
{
Item = value;
}
public Node(T value, bool isRed)
{
Item = value;
IsRed = isRed;
}
public T Item;
public Node<T> Left;
public Node<T> Right;
public Node<T> Parent;
public bool IsRed;
}
public class RedBlackTree<T>
{
public RedBlackTree(){}
public Node<T> root;
int count, version;
Comparer<T> comparer = Comparer<T>.Default;
public void Add(T item)
{
if (this.root == null)
{
this.root = new Node<T>(item, false);
this.count = 1;
this.version++;
return;
}
Node<T> root = this.root;
Node<T> node = null;
Node<T> grandParent = null;
Node<T> greatGrandParent = null;
this.version++;
int num = 0;
while (root != null)
{
num = this.comparer.Compare(item, root.Item);
if (num == 0)
{
this.root.IsRed = false;
return;
}
if (Is4Node(root))
{
Split4Node(root);
if (IsRed(node))
{
this.InsertionBalance(root, ref node, grandParent, greatGrandParent);
}
}
greatGrandParent = grandParent;
grandParent = node;
node = root;
root = (num < 0) ? root.Left : root.Right;
}
Node<T> current = new Node<T>(item);
if (num > 0)
{
node.Right = current;
}
else
{
node.Left = current;
}
if (node.IsRed)
{
this.InsertionBalance(current, ref node, grandParent, greatGrandParent);
}
this.root.IsRed = false;
this.count++;
}
private static bool IsRed(Node<T> node)
{
return ((node != null) && node.IsRed);
}
private static bool Is4Node(Node<T> node)
{
return (IsRed(node.Left) && IsRed(node.Right));
}
private static void Split4Node(Node<T> node)
{
node.IsRed = true;
node.Left.IsRed = false;
node.Right.IsRed = false;
}
private void InsertionBalance(Node<T> current, ref Node<T> parent, Node<T> grandParent, Node<T> greatGrandParent)
{
Node<T> node;
bool flag = grandParent.Right == parent;
bool flag2 = parent.Right == current;
if (flag == flag2)
{
node = flag2 ? RotateLeft(grandParent) : RotateRight(grandParent);
}
else
{
node = flag2 ? RotateLeftRight(grandParent) : RotateRightLeft(grandParent);
parent = greatGrandParent;
}
grandParent.IsRed = true;
node.IsRed = false;
ReplaceChildOfNodeOrRoot(greatGrandParent, grandParent, node);
}
private static Node<T> RotateLeft(Node<T> node)
{
Node<T> right = node.Right;
node.Right = right.Left;
right.Left = node;
return right;
}
private static Node<T> RotateRight(Node<T> node)
{
Node<T> left = node.Left;
node.Left = left.Right;
left.Right = node;
return left;
}
private static Node<T> RotateLeftRight(Node<T> node)
{
Node<T> left = node.Left;
Node<T> right = left.Right;
node.Left = right.Right;
right.Right = node;
left.Right = right.Left;
right.Left = left;
return right;
}
private static Node<T> RotateRightLeft(Node<T> node)
{
Node<T> right = node.Right;
Node<T> left = right.Left;
node.Right = left.Left;
left.Left = node;
right.Left = left.Right;
left.Right = right;
return left;
}
private void ReplaceChildOfNodeOrRoot(Node<T> parent, Node<T> child, Node<T> newChild)
{
if (parent != null)
{
if (parent.Left == child)
{
parent.Left = newChild;
}
else
{
parent.Right = newChild;
}
}
else
{
this.root = newChild;
}
}
}
编辑
我对其他一些数据结构(一些由我创建*,一些来自 .net 框架**)进行了相同的诊断,这是有趣的结果
*AATree 00:00:00.0309294
*AVLTree 00:00:00.0129743
**SortedDictionary 00:00:00.0313571
*RBTree 00:00:09.2414156
**SortedSet 00:00:00.0241973
RBTree 与上面相同(从 SortedSet 类中剥离出来)。我也尝试了 400000 个值,但 RBTree 似乎在使用 FOREVER,我真的不知道为什么。