Fundamental Data Structures in C#

Question

I would like to know how people implement the following data structures in C# without using the base class library implementations:-

• Linked List
• Hash Table
• Binary Search Tree
• Red-Black Tree
• B-Tree
• Binomial Heap
• Fibonacci Heap

and any other fundamental data structures people can think of!

I am curious as I want to improve my understanding of these data structures and it'd be nice to see C# versions rather than the typical C examples out there on the internet!

Answer 1

There's a series of MSDN articles on this subject. However, I haven't really read the text myself. I believe that the collections framework by .NET has a broken interface and cannot be extended very well.

There's also C5, a libray that I am investigating right now.

For the reason mentioned above, I've had the project to implement my own collections library for .NET but I've stopped this project after the first benchmark revealed that even a straightforward, non-thread-safe generic Vector implementation is slower than the native List<T>. Since I've taken care not to produce any inefficient IL code, this means that .NET is simply not suited (yet) for writing on-par replacements for intrinsic data structures, and that the .NET framework has to use some behind-the-scenes knowledge to optimize the builtin collection classes.

Answer 2

Here is a generic Binary Search Tree. The only thing I didn't do was implement IEnumerable<T> so you could traverse the tree using a enumerator. However that should be fairly straight forward.

Special thanks to Scott Mitchel for his BSTTree article, I used it as a reference on the delete method.

The Node Class:

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

And the actual Tree class:

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