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.

Solution 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

Solution 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.

Solution 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