Is there a Binary Search Tree implementation in .NET 4?

Question

I'm looking for a built-in Binary Search Tree implementation in .NET 4. Is there one?

Answer 1

The SortedDictionary<K,V> class uses a Tree, is that what you're after?

See this SO answer for a discussion.

Answer 2

You could use SortedDictionary<TKey, TValue>

Answer 3

Another option is to use a List and sort it. Then you can use the BinarySearch method to find items. To maintain the sorted list you can use the index returned by the BinarySearch to insert at. If the returned index is negative use the complement (~ operator) as your insert location, if the returned index is positive you can insert at that location (unless you want set like behavior in which case don't insert at all).

Answer 4

C5 library:

Class TreeDictionary implements interface ISortedDictionary and represents a dictionary of (key,value) pairs, or entries, using an ordered balanced redblack binary tree. Entry access, entry deletion, and entry insertion take time O(logn). Enumeration of the keys, values or entries of a tree dictionary follow the key order, as determined by the key comparer.