logo标签列表

.NET 4.0中是否内置了二叉搜索树？

c#.netbinary-tree
81

在.NET 4.0中是否有内置的二叉搜索树，还是需要从头开始构建这个抽象数据类型？

编辑

这是关于二叉搜索树特别地，而不是一般意义上的“树”这种抽象数据类型。

可能是重复的问题，与代表树的对象有关。 - Robert MacLean
1
是的，你六年前也知道这个：http://stackoverflow.com/a/3262982/53236 :P - Robert MacLean
1
@RobertMacLean...自那时起，.NET已经发展壮大，去年我学到了真正的答案是YES https://dev59.com/LXA75IYBdhLWcg3wf5NV#34083290 :) - Benny Skogberg
2
那么基于StackOverflow是可编辑的事实，难道不应该有人回来编辑或关闭这些问题吗？基本上，通过留下一个旧的错误/不完整的答案，我们难道不是在伤害未来的知识搜索者吗？ - Robert MacLean
https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.list-1.binarysearch?view=netframework-4.7.2 - BigChief
感谢您提出这个问题。不幸的是，这里的答案并不符合我的需求。例如，SortedSet<T>使用二叉搜索树（BST），但它不是BST，因为它没有公开经典的BST方法和属性。因此，我已经从头开始实现了一个库。 - kmschaal
6个回答
76
2
红黑树实际上是一种特殊的二叉搜索树。请查看我的答案以获取更多详细信息。 - Muhammad Rehan Saeed
15
不幸的是，这个类没有提供许多经典二叉搜索树的有用方法，例如 lower_bound（在C ++中已在std :: set中实现）。要注意GetViewBetween方法。意外的是，它具有线性运行时间。 - renadeen
这个答案是错误的。SortedSet<T> 不是二叉搜索树（BST）。插入和删除操作的时间复杂度为 O(n)。 - ataravati
1
SortedSet是一种二叉搜索树。dotnet的开源代码可在GitHub上参考。 https://github.com/dotnet/corefx/blob/master/src/System.Collections/src/System/Collections/Generic/SortedSet.cs - Ravi Sankar Rao
这使用了在列表上进行二分查找的方法。https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.list-1.binarysearch?view=netframework-4.7.2 - BigChief
SortedSet.First() 应该返回 BST 的根节点吗？如果不是，它是返回第一个添加的项吗？还是最后添加的项？ - joym8
23

五年后，我才意识到在 .NET 4.0 中确实有内置的二叉搜索树。它可能是在之后添加的，并且按预期工作。每次插入后它会自我平衡（遍历），这会降低在添加大量项时的性能。

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

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

2
为什么你需要一个键（也许是因为你的模型需要它）？SortedSet<T>已经覆盖了这个问题（但没有键）吗？ - bbqchickenrobot
1
@bbqchickenrobot 这就是为什么我接受了 SortedSet<T> 的答案;-) - Benny Skogberg
11
不，.NET没有包含二叉搜索树。它包含一种特殊的二叉搜索树红黑树，其中每个节点都被涂成红色或黑色，并且使用这些颜色有一定的规则来保持树的平衡，并允许树保证O(logn)的搜索时间。标准的二叉搜索树无法保证这些搜索时间。
该类称为{{link3：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
4

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

不错。红黑树与普通的二叉搜索树有些不同，但仍然是一个非常好的算法！我会立即收藏那个链接，并保存在我的XMarks账户中 :) 谢谢Herbie博士。 - Benny Skogberg
2

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

我不确定你所说的“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 );
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接