在.NET 4.0中是否有一个内置的二进制search树？

在.NET 4.0中是否有内置的二叉search树，还是需要从头开始构build这种抽象数据types？

编辑

这是专门针对二叉search树，而不是一般的抽象数据types“树”。

Answer 1

我认为System.Collections.Generic的SortedSet<T>类是你正在寻找的。

从这个CodeProject文章 ：

它使用一个自平衡的红黑树来实现，其插入，删除和查找的性能复杂度为O（log n） 。 它用于保持sorting顺序的元素，获取特定范围内元素的子集，或获取集合的Min或Max元素。

源代码https://github.com/dotnet/corefx/blob/master/src/System.Collections/src/System/Collections/Generic/SortedSet.cs

Answer 2

五年后，我问了这个问题，我意识到在.NET 4.0中确实有一个内置的二进制search树。 它可能后来被添加，并按预期工作。 它在每次插入之后自动平衡（遍历），从而降低添加大量项目的性能。

SortedDictionary<TKey, TValue>类具有以下注释：

SortedDictionarygenerics类是一个O（log n）检索的二叉search树，其中n是字典中元素的数量。 在这方面，它与SortedListgenerics类相似。 这两个类有相似的对象模型，都有O（log n）检索。

Answer 3

一个C＃平衡AVL二叉树可以在http://code.google.com/p/self-balancing-avl-tree/find，它也实现了对数连接和分割操作;

Answer 4

不，.NET不包含二进制search树 。 它包含一个红黑树 ，它是一种特殊的二叉search树，其中每个节点被涂成红色或黑色，并且使用这些颜色的某些规则保持树平衡并允许树保证O（logn）search倍。 标准的二叉search树不能保证这些search时间。

这个类被称为SortedSet<T> ，并在.NET 4.0中引入。 你可以在这里看看它的源代码。 这是一个使用的例子：

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

我不确定你的意思是“树”，但你可以在List类上进行二分search。

 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

答案是不。

虽然有可用的实现。 看看下面的链接：

二进制树在C＃

Answer 7

C5集合库（请参见http://www.itu.dk/research/c5/ ）包含具有平衡红黑二叉树的TreeDictionary<>类。 注意：我还没有使用这个库，因为我所做的工作不需要标准的.NET集合。

Answer 8

谢谢你 ，我现在知道有！ 我试了一下，它真的工作！

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