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.

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

Solution 4

a C# balanced AVL binary tree can be found @ http://code.google.com/p/self-balancing-avl-tree/ .it also implements logarithmic concatenate and split operations

Solution 5

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.

View more solutions

Comments

[Benny Skogberg]

Thanx - this was new info for me - thanx

[Benny Skogberg]

Nice one. Red-Black trees are a little different than ordinary BinarySearchTrees, but still a very nice algorithm! I'll bookmark that link right away, and save it on my XMarks account :) Thanx Dr Herbie.

[Muhammad Rehan Saeed]

A Red-Black Tree is really a specialized kind of Binary Search Tree. See my answer for more details.

[renadeen]

Unfortunatly this class doesn't provide many useful methods of classic Binary Search Tree, e. g. lower_bound (which is implemented in std::set in C++). Beware of GetViewBetween method. Unexpectedly it has linear running time

[bbqchickenrobot]

Why would you need a key (perhaps your model required it)? Doesn't SortedSet<T> cover this already (but without the key)?

[Benny Skogberg]

@bbqchickenrobot That's why I accepted the answer SortedSet<T> ;-)

[ataravati]

This answer is wrong. SortedSet<T> is not a BST. The insert and delete have a time-complexity of O(n).

[Ravi Sankar Rao]

SortedSet is a Binary Search Tree. dotnet opensource code is available on github for reference. github.com/dotnet/corefx/blob/master/src/System.Collections/‌​src/…

[BigChief]

This uses binary search on list docs.microsoft.com/en-us/dotnet/api/…

[joym8]

Should SortedSet.First() return the root node of the BST? If not, is it returning the first item that was added? Or the one that was added last?