Существует ли встроенное Дерево двоичного поиска в.NET 4.0?
Существует ли встроенное дерево двоичного поиска в.NET 4.0, или я должен создать этот абстрактный тип данных с нуля?
Править
Это о дереве двоичного поиска и не абстрактном типе данных "деревья" в целом.
5 ответов
Я думаю, что класс SortedSet в System.Collections.Generic - это то, что вы ищете.
Он реализован с помощью самобалансирующееся красно-чёрное дерево, что дает сложность производительности O(log n) для вставки, удаления и Поиска. Он используется для сохранения элементы в отсортированном порядке, чтобы получить подмножество элементов в конкретном диапазон, или получить Min или Max элемент набора.
Исходный код https://github.com/dotnet/corefx/blob/master/src/System.Collections/src/System/Collections/Generic/SortedSet.cs
Библиотека коллекций C5 (см. http://www.itu.dk/research/c5/ ) включает классы TreeDictionary <> со сбалансированными красно-черными двоичными деревьями. Примечание: я еще не использовал эту библиотеку, поскольку для моей работы не требуется ничего, кроме стандартных коллекций .NET.
Спасибо herzmeister der welten , теперь я знаю, что есть! Я попробовал, и это действительно сработало!
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();
}
}
}
Я не уверен, что именно вы имеете в виду под словом «дерево», но вы можете использовать двоичный код выполняет поиск по классу 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 );
Ответ: Нет.
Тем не менее, существуют реализации. Взгляните на следующую ссылку: