Why is there no <T> class in .NET?

Question

The .NET base class library has some excellent data structures for collections (List, Queue, Stack, Dictionary), but, strangely enough, it does not contain any data structures for binary trees. This is a terribly useful structure for certain algorithms, such as those that use different workarounds. I am looking for a well-written, free implementation.

I'm just blind, and I can’t find him ... is he buried somewhere in the BCL? If not, can someone recommend a free or open C # /. NET library for binary trees? Preferably one that uses generics.

EDIT: To clarify what I'm looking for. I am not interested in ordered collections of dictionaries that use the tree internally. I'm really interested in a binary tree - one that reveals its structure so that you can do things like extract subtrees, or perform a workaround on nodes. Ideally, such a class can be extended to provide the behavior of specialized trees (e.g., Red / Black, AVL, Balanced, etc.).

Answer 1

You are right, there is nothing in BCL. I suspect that this is due to the fact that the choice of whether to use the tree is usually an implementation detail, and otherwise, an unconventional way to access data. That is, you do not say: "element binary-search-for # 37"; instead, you say, "Get item No. 37."

But did you watch the C5 ? This is super-convenient and they have several tree implementations ( 1 , 2 , 3 ).

Answer 2

You can define your own:

public class MyTree<K, V> : Dictionary<K, MyTree<K, V>> { public V Value { get; set; } } 

Or without a key:

 public class MyTree<V> : HashSet<MyTree<V>> { public V Value { get; set; } } 

Answer 3

What would you like from such an implementation?

Binary tree? Red and black? Radix tree? B-tree? R-tree? R * -tree?

A tree is more a template than a data structure, and they are usually used where performance is important (therefore, implementation details are likely to matter). If some tree class is included in BCL, you will still need to roll yourself

Answer 4

I believe SortedDictionary as an insertion of log (n), the search characteristics that you expect from a tree data structure.

http://msdn.microsoft.com/en-us/library/f7fta44c(VS.80).aspx

Answer 5

SortedSet<T> is implemented as a ^ref binary search tree. SortedDictionary<TKey, TValue> internally uses SortedSet<T> , so it is also a binary ^ref search tree.

Answer 6

No, there is no < Tree<T> -like "type in BCL (which has always puzzled me), but here is a good article that will guide you through implementing your own in C #.

I think you could make the argument that tree-like data structures are less commonly used in applications that typically use .NET (business applications, data transfer applications, etc.). However, I agree with you, it is strange that BCL has no implementation at all.

Answer 7

This series of articles was useful to me when I had to write my own, especially part 3 and 4.

Extensive data structure analysis

Answer 8

Here is a TreeNode that you can use. It is not shared and hidden in window forms and is used with the treeview control, but you can also use it elsewhere.