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

Question

The base class library in .NET has some excellent data structures for collections (List, Queue, Stack, Dictionary), but oddly enough it does not contain any data structures for binary trees. This is a terribly useful structure for certain algorithms, such as those that take advantage of different traversal paths. I'm looking for a correctly written, free implementation.

Am I simply blind, and not finding it... is it buried somewhere in the BCL? If not, can someone recommend a free or open-source C#/.NET library for binary trees? Preferably one that employs generics.

EDIT: To clarify what I'm looking for. I'm not interested in ordered dictionary collections that internally use a tree. I'm actually interested in a binary tree - one that exposes its structure so that you can do things like extract subtrees, or perform post-fix traversal on the nodes. Ideally such a class could be extended to provide the behaviors of specialized trees (ie. Red/Black, AVL, Balanced, etc).

Solution 1

You're right, there's nothing in the BCL. I suspect this is because the choice of whether to use a tree is typically an implementation detail and is otherwise an unconventional way to access data. That is, you don't say, "binary-search-for element #37"; instead, you say, "get me element #37".

But have you taken a look at C5? It's super-handy and they have several tree implementations (1, 2, 3).

Solution 2

You could define your own:

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

Or unkeyed:

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

Solution 3

What would you want from such an implementation?

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

A tree is more a pattern than a data structure, and they tend to be used where performance matters (so implementation details probably matter too). If the BCL included some kind of a tree class, you'd only have to roll your own anyway

Solution 4

I believe that SortedDictionary as the log(n) insert, retrieval characteristics that you would expect from a Tree Data Stucture.

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

Solution 5

SortedSet<T> is implemented as a binary search tree^ref. SortedDictionary<TKey, TValue> internally makes use of SortedSet<T> so it too is a binary search tree ^ref.

View more solutions

Comments

[Henk Holterman]

Yeah, but it just has a Tag property of System.Object ype. No Generic <T> parameter

[Paul Morie]

I always feel weird about doing stuff like that. It's less visible with your specific example, but if people routinely re-purpose classes from, say, dependencies, this can result in hard-to-explain dependencies and can get you into trouble if the re-purposed class changes in an unexpected way across dependency versions.

[LBushkin]

Unfortunately these are simply implementations of ordered maps and lists. Neither is helpful for reuse as a binary tree - these tree structures are simply an implementation detail of the collection. I'm actually looking for a class that exposes the tree structure.

[LBushkin]

Indeed, the implementation details matter. In my case, I'm looking to implement some algorithms that would perform different traversals (infix, postfix) on an organized set of data as part of a series of transformations. A tree structure is the most elegant way of solving my problem.

[Johnny]

C5 supports Red Black trees not B-Tree. They are differences whick people should be aware of. B-Tree is more optimal for a disk based tree or large memory based tree. More nodes are kept in the same locality so you get better processor cache performance and is quicker to read write to disk.

[user492238]

What would be the profit of using it? A tree node does usually not have any relevant functionality in it. It just holds references to childs and eventually a parent. No reason to misuse a System.Windows.Forms class for it! Just write it yourself - in a minute or less.

[Veverke]

This however requires you to know how many tree levels you will handle at compile time, am I wrong ?

[Jason]

No, the C# compiler supports this syntax.

[rymdsmurf]

In a parallel universe someone is asking the question: "Why are there no list types in .Net?", and they get the answer: "What would you want from such an implementation? An array? A linked list? A queue? A dictionary?" I think this is a non sequitur answer.

[Sebastian]

Beware that elements are un-ordered this way

[Tom Blodget]

@Veverke Perhaps you were thinking of C++ templates. .NET generics are runtime types.

[Syaiful Nizam Yahya]

Im curious. How do you use this? Practically? Any sample?

[John K]

To make it an ordered tree inherit from System.Collections.Specialized.OrderedDictionary