在.NET 4.0中是否有一个内置的二叉查找树？

有没有一个内置的二叉查找树。NET 4.0，还是我需要从头开始构建这个抽象数据类型？

Edit

这是关于具体的二叉查找树，而不是一般的抽象数据类型“树”。

71253 次浏览
小开

我不确定你说的“树”到底是什么意思，但是你可以在 List 类上进行二进制搜索。

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 );
小开

The C5 collections library (see http://www.itu.dk/research/c5/) includes TreeDictionary<> classes with balanced red-black binary trees. Note: I have not used this library yet, as the work I do needs nothing more that the standard .NET collections.

小开
最佳答案

我认为 System.Collections.Generic中的 SortedSet<T>课程就是你要找的。

来自 这篇 CodeProject 文章:

它是使用 自平衡的红黑树 使性能复杂化 O (logn) 表示插入、删除和 它用于保存 元素以排序顺序排列，以获取 特定元素的子集 范围，或得到 Min或 麦克斯 集合的元素。

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

小开

感谢 世界大师，我现在知道有! 我试过了，它真的工作！

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

不。NET 不包含 Binary Search Tree。它确实包含一个 红黑树，这是一种特殊的二叉查找树，每个节点都被涂成红色或黑色，并且使用这些颜色有一定的规则来保持树的平衡，使得树能够保证 登录的搜索时间。一个标准的二叉查找树不能保证这些搜索时间。

这个类称为 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
小开

五年后我问了这个问题，我意识到确实有一个内置的二叉查找树。NET 4.0.它可能是后来添加的，并且按照预期工作。它在每次插入之后自平衡(遍历) ，这会降低添加大量项目时的性能。

SortedDictionary<TKey, TValue>班有以下意见:

SortedDictionary 泛型类是一个带有 o (log n)检索的二叉查找树，其中 n 是字典中的元素数。在这方面，它类似于 SortedList 泛型类。这两个类具有相似的对象模型，并且都具有 O (logn)检索。


提交答案