CODEWITHSUNDEEP
c#.netdata-structures
LBushkin
LBushkin

Reputation: 131806

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

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).

Upvotes: 98

Views: 45491

Answers (8)

Matt Brunell
Matt Brunell

Reputation: 10399

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

Upvotes: 16

Gulzar Nazim
Gulzar Nazim

Reputation: 52198

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

An Extensive Examination of Data Structures

Upvotes: 1

John Feminella
John Feminella

Reputation: 311665

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).

Upvotes: 35

Joel Coehoorn
Joel Coehoorn

Reputation: 416121

There's a TreeNode you can use. It's not generic and hidden away in windows forms and used with the treeview control, but you can use it elsewhere as well.

Upvotes: -5

Jason
Jason

Reputation: 28600

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; }
}

Upvotes: 80

Sean
Sean

Reputation: 599

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

Upvotes: 16

Alun Harford
Alun Harford

Reputation: 3124

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

Upvotes: 46

Andrew Hare
Andrew Hare

Reputation: 351648

No, there isn't any "Tree<T>-like" type in the BCL (something that has always puzzled me as well) but here is a good article that will walk you through implementing your own in C#.

I guess you could make the argument that tree-based data structures are less commonly used in the kind of applications that .NET is usually used for (business apps, data-moving apps, etc.). Still, I agree with you, it is strange that the BCL has no implementation at all.

Upvotes: 10

Related Questions