Is there a built-in Binary Search Tree in .NET 4.0?

Question

Is there a built-in binary search tree in .NET 4.0, or do I need to build this abstract data type from scratch?

Edit

This is about the binary search tree specifically, and not abstract data type "trees" in general.

Answer 1

I think the SortedSet<T> class in System.Collections.Generic is what you're looking for.

From this CodeProject article:

It is implemented using a self-balancing red-black tree that gives a performance complexity of O(log n) for insert, delete, and lookup. It is used to keep the elements in sorted order, to get the subset of elements in a particular range, or to get the Min or Max element of the set.

Source code https://github.com/dotnet/corefx/blob/master/src/System.Collections/src/System/Collections/Generic/SortedSet.cs

Answer 2

Five years after I asked the question I realized that there is indeed a built in Binary Search Tree in .NET 4.0. It has probably been added later on, and works as expected. It self-balances (traversing) after each insert which decrease performance on adding a large range of items.

The SortedDictionary<TKey, TValue> Class has the following remarks:

The SortedDictionary generic class is a binary search tree with O(log n) retrieval, where n is the number of elements in the dictionary. In this respect, it is similar to the SortedList generic class. The two classes have similar object models, and both have O(log n) retrieval.

Answer 3

No, .NET does not contain a Binary Search Tree. It does contain a Red-Black Tree which is a specialized kind of Binary Search Tree in which each node is painted red or black and there are certain rules using these colours which keep the tree balanced and allows the tree to guarantee O(logn) search times. A standard Binary Search Tree cannot guarantee these search times.

The class is called a SortedSet<T> and was introduced in .NET 4.0. You can look at it's source code here. Here is an example of it's use:

// Created sorted set of strings.
var set = new SortedSet<string>();

// Add three elements.
set.Add("net");
set.Add("net");  // Duplicate elements are ignored.
set.Add("dot");
set.Add("rehan");

// Remove an element.
set.Remove("rehan");

// Print elements in set.
foreach (var value in set)
{
    Console.WriteLine(value);
}

// Output is in alphabetical order:
// dot
// net

Answer 4

The C5 collections library (see http://www.itu.dk/research/c5/) includes TreeDictionary<> classes with balanced red-black binary trees. Note: I have not used this library yet, as the work I do needs nothing more that the standard .NET collections.

Answer 5

Thanx to herzmeister der welten, I now know there are! I tried it and it really worked!

namespace Tree
{
    public partial class Form1 : Form
    {
        private SortedSet<int> binTree = new SortedSet<int>();

        public Form1()
        {
            InitializeComponent();
        }

        private void Insert(int no)
        {
            binTree.Add(no);
        }

        private void Print()
        {
            foreach (int i in binTree)
            {
                Console.WriteLine("\t{0}", i);
            }
        }

        private void btnAdd_Click(object sender, EventArgs e)
        {
            Insert(Int32.Parse(tbxValue.Text));
            tbxValue.Text = "";
        }

        private void btnPrint_Click(object sender, EventArgs e)
        {
            Print();
        }
    }
}

Answer 6

I'm not sure what exactly you mean with 'tree', but you can do binary searchs on the List class.

public int BinarySearch( T item );
public int BinarySearch( T item, IComparer<T> comparer );
public int BinarySearch( int index, int count, T item, IComparer<T> comparer );