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 create this abstract data type from scratch?

Edit

This applies to the binary search tree, and not to the abstract trees data type in general.

Answer 1

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

From this CodeProject article :

It is implemented using a self-balancing red-black tree , which gives the complexity of executing O (log n) for insert, delete, and look. It is used for items in sorted order to get a subset of items in a specific range or to get a Min or Max item 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 this question, I realized that in .NET 4.0 there is a built-in binary search tree. It was probably added later and works as expected. It independently balances (moves) after each insertion, which reduces performance when adding a large number of items.

The SortedDictionary<TKey, TValue> has the following notes:

The general class SortedDictionary 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 general SortedList class. These two classes have similar object models, and both have O (log n).

Answer 3

can find a binary ACL tree with C # @ balancing http://code.google.com/p/self-balancing-avl-tree/ . Also implements logarithmic operations of concatenation and separation

Answer 4

No, .NET does not contain a binary search tree . It contains a Red-Black Tree , which is a specialized binary search tree in which each node is colored red or black, and there are certain rules that use these colors to keep the tree balanced and allow the tree to guarantee O (logn) search time. The standard binary search tree cannot guarantee these search times.

The class is called SortedSet<T> and was introduced in .NET 4.0. You can see the source code here . Here is a usage example:

 // 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 5

I'm not sure what exactly you mean by the "tree", but you can perform binary searches in 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 ); 

Answer 6

Answer: No.

Available implementations exist. Take a look at the following link:

Binary tree in c #

Answer 7

The C5 collection 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, since the work I do no longer needs standard .NET assemblies.

Answer 8

Thanx to herzmeister der welten , now I know what it is! I tried 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(); } } }