在C#中实现红黑树

Question

我正在寻找一个在C#中实现红黑树的实现, 具有以下特点:

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

谢谢。

- Alon Gubkin

---

回答你的另一个问题，即“书还是老师”，学习编程的真正最佳方法是编写程序。自己动手编写一个程序，然后你就会学到东西了。 - P Shved

@Pavel：我可以写这个，但我正在寻找一些现成的东西，以便我可以继续开发我的程序的主要部分，并加快开发速度。 - Alon Gubkin

Answer 1

你主要描述了 SortedDictionary<T, U>，除了查找下一个最低/最高值的二分搜索，你可以自己实现而不需要太多困难。 SortedDictionary 对你来说不够用吗？

- mqp

---

“不需要太大困难，就可以自己实现。” 我认为你不能轻易地扩展SortedDictionary。从元数据和简单的尝试扩展它来看，必要的内部部件似乎是无法访问的。我错了吗？ - Catskul

你是说 SortedDictionary<T,U> 实现了红黑树吗？如果是这样，你从哪里找到的信息？我在 MSDN 页面上没有看到任何提及。 - comecme

是的，我刚刚通过在Reflector中浏览类来验证了它。在内部，它将键放入一个SortedSet<T>中，该集合实现为红黑树。我不确定我从哪里听说过这个——我感觉旧版本的MSDN文档更详细地介绍了SortedDictionary与SortedList的实现方式。另外，嗯，我不确定为什么我认为他可以轻松扩展它。并不清楚他是否能够。哦，算了。 - mqp

Answer 2

从C5集合库中剥离TreeSet。

- rama-jka toti

Answer 3

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

SortedDicionary仅允许公开GetEnumerator()函数，该函数从集合的开头开始，并且仅允许调用MoveNext()，因此即使使用LINQ，也没有任何魔法发生：它从开头开始，在顺序中运行您的表达式，直到找到与LINQ表达式匹配的节点。

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

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

- huntharo

Answer 4

System.Collections.Generic.SortedSet 是以红黑树实现的。

- Mark Lauter