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

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

编辑

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

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

从这个CodeProject文章 :

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

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

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

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

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

不,.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 

我不确定你的意思是“树”,但你可以在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 ); 

答案是不。

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

二进制树在C#

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

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

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