红黑树的C#实现

Question

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

• 搜索、插入和删除的时间复杂度为 O(log n)。
• 成员类型应该是通用的。
• 支持于 比较器(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。