c# - C#中红黑树的实现

Question

我正在寻找C# 中红黑树的实现，具有以下功能：

• 在 O(log n) 中搜索、插入和删除。
• 成员类型应该是通用的。
• 支持Comparer(T)，用于按其中的不同字段进行排序T。
• 在树中搜索应该使用特定的字段，所以它不会接受T，但它会接受对它进行排序的字段类型。
• 搜索不应该只是精确值。应该支持搜索较低/较高的。

谢谢你。

Answer 1

您大多只是描述了SortedDictionary<T, U>，除了次低/次高二进制搜索，您可以轻松地自行实现。

是否有具体的原因SortedDictionary对您来说不够？

Answer 2

从 C5 集合库中提取 TreeSet。

Answer 3

这正是 PowerCollections 中的 OrderedDictionary。它与 SortedDictionary（带有泛型的红黑树）几乎相同，还增加了设置开始键/结束键并扫描该范围内所有值的能力。

SortedDicionary 只允许公开从集合开头开始的 GetEnumerator() 函数，并且只允许 MoveNext() 调用，因此即使您使用 LINQ 也不会发生任何神奇的事情：它从开头开始并在每一个上运行您的表达式节点，按顺序，直到找到与您的 LINQ 表达式匹配的节点。

OrderedDictionary 有一个函数可以在特定键处或之前获取枚举器，并在 O(log n) 中进行查找。

不过需要注意的是：PowerCollections OrderedDictionary 中的枚举器是使用“yield”实现的，内存使用量和枚举性能至少为 O(n^2)……您可以自己更改实现以使其实现传统的枚举器这两个问题都消失了。如果我能找到时间，我会将该补丁提交给 Codeplex。