Eu estava apenas fazendo uma pesquisa sobre o RedBlack Tree. Eu sabia que a classe SortedSet no .net 4.0 usa a árvore RedBlack. Então eu tirei essa parte como está usando o Reflector e criei uma classe RedBlackTree. Agora, estou executando um teste de desempenho neste RedBlackTree e SortedSet, inserindo 40000 valores integrais seqüenciais (começando de 0 a 39999). Estou surpreso ao ver que há uma enorme diferença de desempenho da seguinte maneira:

 RBTree    took 9.27208   sec to insert 40000 values 
 SortedSet took 0.0253097 sec to insert 40000 values

Qual é a razão por trás disso? BTW, executei o teste apenas na configuração da versão e aqui está o pequeno código de teste

            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);

Editar

Gostaria de compartilhar também o código do RBTree que extraí para que você também possa executar o diagnóstico

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;
            }
        }
    }

Editar

Eu executei o mesmo diagnóstico em alguma outra estrutura de dados (alguns criados por mim *, alguns do framework .net **) e aqui estão os resultados interessantes

*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 é o mesmo que acima (excluído da classe SortedSet).Eu tentei com 400000 valores também, mas RBTree parece levar para sempre, Eu realmente não sei o porquê.