Здравствуйте, samius, Вы писали:

S>        static bool SearchAndInsert<T>(this Node<T> tree, T value)
S>        {
S>            if (tree == null)
S>                throw new ArgumentNullException("tree");

S>            var eq = Comparer<T>.Default.Compare(tree.Value, value);
S>            if (eq == 0)
S>                return true;

S>            if(eq > 0)
S>            {
S>                if(tree.Left != null)
S>                    SearchAndInsert(tree.Left, value);
S>                else
S>                    tree.Left = new Node<T>(value, null, null);
S>            }
S>            else
S>            {
S>                if (tree.Right != null)
S>                    SearchAndInsert(tree.Right, value);
S>                else
S>                    tree.Right = new Node<T>(value, null, null);
S>            }
S>            return false;
S>        }

Боже, зачем же так сложно и длинно ? Да еще ArgumentNullException, которого тут вообще не должно быть!

    class Node<T>
    {
        public Node(T value, Node<T> left, Node<T> right)
        {
            Value = value;
            Left = left;
            Right = right;
        }
        public T Value { get; set; }
        public Node<T> Left { get; set; }
        public Node<T> Right { get; set; }

// мне пришлось заменить свойства на поля, так как свойства нельзя передавать по ref
// public их делать совсем не обязательно, но лень было возиться :-)
// так что в моем коде не используются твои Left и Right, а используются мои left и right

        public Node<T> left;
        public Node<T> right;
    }

    static class Program
    {
        static Node<T> Insert<T>(this Node<T> tree, T value)
        {
            if (tree == null)
                return new Node<T>(value, null, null);
            var eq = Comparer<T>.Default.Compare(tree.Value, value);
            if (eq == 0)
                return tree;
            return eq > 0
               ? new Node<T>(tree.Value, Insert(tree.Left, value), tree.Right)
               : new Node<T>(tree.Value, tree.Left, Insert(tree.Right, value));
        }

        static bool SearchAndInsert<T>(this Node<T> tree, T value)
        {
            if (tree == null)
                throw new ArgumentNullException("tree");

            var eq = Comparer<T>.Default.Compare(tree.Value, value);
            if (eq == 0)
                return true;

            if (eq > 0)
            {
                if (tree.Left != null)
                    SearchAndInsert(tree.Left, value);
                else
                    tree.Left = new Node<T>(value, null, null);
            }
            else
            {
                if (tree.Right != null)
                    SearchAndInsert(tree.Right, value);
                else
                    tree.Right = new Node<T>(value, null, null);
            }
            return false;
        }

// а вот и моя версия - чистая калька с С++
// DPL - это я (Дворкин Павел Лазаревич :-)
// как видишь, она ничуть не сложнее твоей LinQ-овской, скорее проще :-)

        static bool DPLSearchAndInsert<T>(ref Node<T> tree, T value)
        {
            if (tree == null)
            {
                tree = new Node<T>(value, null, null);
                return false;
            }

            var eq = Comparer<T>.Default.Compare(tree.Value, value);
            if (eq == 0)
                return true;

            if (eq > 0)
                    return DPLSearchAndInsert(ref tree.left, value);
            else
                    return DPLSearchAndInsert(ref tree.right, value);
        }


        static Node<T> BuildTree<T>(IEnumerable<T> data)
        {
            return data.Aggregate(default(Node<T>), Insert);
        }

        static Node<T> BuildTreeM<T>(IEnumerable<T> data)
        {
            var iter = data.GetEnumerator();
            if (!iter.MoveNext())
            {
                throw new ArgumentException();
            }
            var result = new Node<T>(iter.Current, null, null);
            while (iter.MoveNext())
                SearchAndInsert(result, iter.Current);
            return result;
        }
// это мои построитель

        static Node<T> DPLBuildTreeM<T>(IEnumerable<T> data)
        {
            var iter = data.GetEnumerator();
            if (!iter.MoveNext())
            {
                throw new ArgumentException();
            }
// пришлось заменить var на Node<T>, так как var нельзя присвоить null
            Node<T> result = null;
            while (iter.MoveNext())
                DPLSearchAndInsert(ref result, iter.Current);
            return result;
        }
        static void Main()
        {
            var buffer = Enumerable.Range(0, 1000000).ToArray();
            var rnd = new Random();
            for (int i = 0; i < buffer.Length; i++)
            {
                int j = rnd.Next(buffer.Length);
                var tmp = buffer[i];
                buffer[i] = buffer[j];
                buffer[j] = tmp;
            }

            Test(() => BuildTree(buffer), "Immutable insert");
            Test(() => BuildTreeM(buffer), "SearchAndReplace");
            Test(() => DPLBuildTreeM(buffer), "DPLSearchAndReplace");

            Console.ReadKey();
        }

        static void Test(Action action, string name)
        {
            Console.WriteLine();
            Console.WriteLine(name);
            var sw = Stopwatch.StartNew();
            action();
            Console.WriteLine(sw.Elapsed);
        }
    }

S>При том что иммутабельное заполнение дерева в 3 и более раз короче, оно во столько же раз проигрывает по производительности императивному на миллионе вставок.


Immutable insert
00:00:09.9648256

SearchAndReplace
00:00:03.2450794

DPLSearchAndReplace
00:00:02.8752006


S>Можно сказать паритет

Нет, 2.5:0.5 в мою пользу. Я сделал эту DPLSearchAndInsert столь же простой, как твоя, и даже проще, а выигрыш по времени в 3 раза и ни одного лишнего new. Так что я выиграл и по памяти, и по времени, а вот по простоте кода — в лучшем случае паритет

P.S. А вот машина у тебя получше раза в 2. Если не секрет, какой процессор ? У меня Athlon Dual 4200+