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

Question

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

编辑

这具体是关于二叉搜索树,而不是一般的抽象数据类型"树".

Answer 1

我认为SortedSet<T>上课System.Collections.Generic是你正在寻找的.

从这个CodeProject文章:

它使用 自平衡的红黑树实现,该树为插入,删除和查找提供了O(log n)的性能复杂性 .它用于保持元素按排序顺序,获取特定范围内的元素子集,或获取 集合的Min或Max元素.

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

Answer 2

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

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

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

Answer 3

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

该类称为a 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

Answer 4

可以在http://code.google.com/p/self-balancing-avl-tree/上找到一个C#平衡的AVL二叉树.它还实现了对数连接和拆分操作