Фундаментальные структуры данных в C#

На эту тему есть серия Статьи MSDN. Однако я сам текст не читал. Я считаю, что фреймворк коллекций .NET имеет неработающий интерфейс и не может быть хорошо расширен.

Также есть библиотека C5, которую я сейчас исследую.

По упомянутой выше причине у меня был проект по реализации моей собственной библиотеки коллекций для .NET, но я остановил этот проект после того, как первый тест показал, что даже простая, небезопасная для потоков универсальная реализация Vector работает медленнее, чем родной List<T>. Поскольку я позаботился о том, чтобы не создавать какой-либо неэффективный код IL, это означает, что .NET просто (пока) не подходит для написания замен по номиналу для внутренних структур данных, и что инфраструктура .NET должна использовать некоторые дополнительные возможности. -scenes знания для оптимизации встроенных классов коллекции.

Я бы порекомендовал два ресурса для упомянутых вами структур данных: Во-первых, это исходный код .NET Framework (информацию можно найти в блоге ScottGu здесь).

Еще один полезный ресурс - Power Collections Wintellect, который можно найти на Codeplex здесь.

Надеюсь это поможет!

Вот общее дерево двоичного поиска. Единственное, что я не сделал, - это реализовал IEnumerable <T>, чтобы вы могли перемещаться по дереву с помощью перечислителя. Однако это должно быть довольно просто.

Особая благодарность Скотту Митчелу за его статью о BSTTree, я использовал ее как справочник по методу удаления.

Класс узла:

    class BSTNode<T> where T : IComparable<T>
    {
        private BSTNode<T> _left = null;
        private BSTNode<T> _right = null;        
        private T _value = default(T);

        public T Value
        {
            get { return this._value; }
            set { this._value = value; }
        }

        public BSTNode<T> Left
        {
            get { return _left; }
            set { this._left = value; }
        }

        public BSTNode<T> Right
        {
            get { return _right; }
            set { this._right = value; }
        }        
    }

И фактический класс Tree:

    class BinarySearchTree<T> where T : IComparable<T>
    {
        private BSTNode<T> _root = null;
        private int _count = 0;

        public virtual void Clear()
        {
            _root = null;
            _count = 0;
        }

        public virtual int Count
        {
            get { return _count; }
        }

        public virtual void Add(T value)
        {
            BSTNode<T> newNode = new BSTNode<T>();
            int compareResult = 0;

            newNode.Value = value;

            if (_root == null)
            {
                this._count++;
                _root = newNode;
            }
            else
            {
                BSTNode<T> current = _root;
                BSTNode<T> parent = null;

                while (current != null)
                {
                    compareResult = current.Value.CompareTo(newNode.Value);

                    if (compareResult > 0)
                    {
                        parent = current;
                        current = current.Left;
                    }
                    else if (compareResult < 0)
                    {
                        parent = current;
                        current = current.Right;
                    }
                    else
                    {
                        // Node already exists
                        throw new ArgumentException("Duplicate nodes are not allowed.");
                    }
                }

                this._count++;

                compareResult = parent.Value.CompareTo(newNode.Value);
                if (compareResult > 0)
                {
                    parent.Left = newNode;
                }
                else
                {
                    parent.Right = newNode;
                }
            }
        }

        public virtual BSTNode<T> FindByValue(T value)
        {
            BSTNode<T> current = this._root;

            if (current == null)
                return null;   // Tree is empty.
            else
            {
                while (current != null)
                {
                    int result = current.Value.CompareTo(value);
                    if (result == 0)
                    {
                        // Found the corrent Node.
                        return current;
                    }
                    else if (result > 0)
                    {
                        current = current.Left;
                    }
                    else
                    {
                        current = current.Right;
                    }
                }

                return null;
            }
        }

        public virtual void Delete(T value)
        {

            BSTNode<T> current = this._root;
            BSTNode<T> parent = null;

            int result = current.Value.CompareTo(value);

            while (result != 0 && current != null)
            {
                if (result > 0)
                {
                    parent = current;
                    current = current.Left;
                }
                else if (result < 0)
                {
                    parent = current;
                    current = current.Right;
                }

                result = current.Value.CompareTo(value);
            }

            if (current == null)
                throw new ArgumentException("Cannot find item to delete.");



            if (current.Right == null)
            {
                if (parent == null)
                    this._root = current.Left;
                else
                {
                    result = parent.Value.CompareTo(current.Value);
                    if (result > 0)
                    {
                        parent.Left = current.Left;
                    }
                    else if (result < 0)
                    {
                        parent.Right = current.Left;
                    }
                }
            }
            else if (current.Right.Left == null)
            {
                if (parent == null)
                    this._root = current.Right;
                else
                {
                    result = parent.Value.CompareTo(current.Value);
                    if (result > 0)
                    {
                        parent.Left = current.Right;
                    }
                    else if (result < 0)
                    {
                        parent.Right = current.Right;
                    }
                }
            }
            else
            {

                BSTNode<T> furthestLeft = current.Right.Left;
                BSTNode<T> furthestLeftParent = current.Right;

                while (furthestLeft.Left != null)
                {
                    furthestLeftParent = furthestLeft;
                    furthestLeft = furthestLeft.Left;
                }

                furthestLeftParent.Left = furthestLeft.Right;

                furthestLeft.Left = current.Left;
                furthestLeft.Right = current.Right;

                if (parent != null)
                {
                    result = parent.Value.CompareTo(current.Value);
                    if (result > 0)
                    {
                        parent.Left = furthestLeft;
                    }
                    else if (result < 0)
                    {
                        parent.Right = furthestLeft;
                    }
                }
                else
                {
                    this._root = furthestLeft;
                }
            }

            this._count--;
        }
    }
}

Проверьте Ротор 2 или используйте отражатель, чтобы увидеть, как Microsoft это сделала !!!

также вы можете проверить Справочный источник Microsoft

NGenerics

«Библиотека классов, предоставляющая общие структуры данных и алгоритмы, не реализованные в стандартной платформе .NET».