NET 4.0中是否有内置的二进制搜索树?

.NET 4.0中是否有内置的二进制搜索树,还是我需要从头开始构建此抽象数据类型?

编辑

这是专门针对二进制搜索树的,而不是一般的抽象数据类型“树”。

Benny Skogberg asked 2019-10-09T11:29:29Z
8个解决方案
51 votes

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

从此CodeProject文章中:

它使用   自平衡的红黑树   使性能复杂度为   O(log n)用于插入,删除和   抬头。 它用于保持   元素按排序顺序,以获取   特定元素的子集   范围,或获取最小值或最大值   集合的元素。

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

herzmeister answered 2019-10-09T11:30:05Z
18 votes

问了问题五年后,我意识到在.NET 4.0中确实存在一个内置的二进制搜索树。 它可能稍后会添加,并且可以按预期工作。 每次插入后,它都会自平衡(移动),这会降低添加大量项目时的性能。

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

SortedDictionary泛型类是具有O(log n)检索的二进制搜索树,其中n是字典中元素的数量。 在这方面,它类似于SortedList通用类。 这两个类具有相似的对象模型,并且都具有O(log n)检索。

Benny Skogberg answered 2019-10-09T11:30:44Z
7 votes

不,.NET不包含二进制搜索树。 它确实包含一棵红黑树,这是一种特殊的二进制搜索树,其中的每个节点都被涂成红色或黑色,并且使用这些颜色的某些规则使树保持平衡并允许树保证O(logn)搜索 次。 标准的二进制搜索树不能保证这些搜索时间。

该类称为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
Muhammad Rehan Saeed answered 2019-10-09T11:31:17Z
6 votes

可以在@ [http://code.google.com/p/self-balancing-avl-tree/]中找到C#平衡的AVL二叉树。它还实现了对数级联和拆分运算

ros answered 2019-10-09T11:31:43Z
3 votes

答案是不。

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

C#中的二叉树

Leniel Maccaferri answered 2019-10-09T11:32:23Z
3 votes

C5集合库(请参阅[http://www.itu.dk/research/c5/)]包括TreeDictionary<>类,具有平衡的红黑二叉树。 注意:我还没有使用过该库,因为我所做的工作只需要标准的.NET集合即可。

Dr Herbie answered 2019-10-09T11:32:49Z
2 votes

我不确定“ tree”到底是什么意思,但是您可以在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 );
Trap answered 2019-10-09T11:33:16Z
2 votes

多亏了她的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();
        }
    }
}
Benny Skogberg answered 2019-10-09T11:33:41Z
translate from https://stackoverflow.com:/questions/3262947/is-there-a-built-in-binary-search-tree-in-net-4-0