在C＃实现红 - 黑树的

我正在寻找在C＃中Red-Black Tree的实现，具有以下特点：在C＃实现红 - 黑树的

搜索，插入的O删除（log n）的。
成员类型应该是通用的。
支持Comparer(T)，用于排序T不同的字段。
在树中搜索应该与特定的字段，所以它不会接受T，但它会接受字段类型排序它。
搜索不应该只是确切的价值。应该支持搜索更低/更高的一个。

谢谢。

来源

2009-11-09 Alon Gubkin

回答您的另一个问题，名为“书或教师”，*真正*学习编程的最佳途径是*编写程序*。写下你自己的，然后你会学到一些东西。 – 2009-11-09 19:47:57

@Pavel：我可以写这个，但是我正在寻找一些准备好的东西，所以我可以继续开发我的程序的主要部分，并加速开发。 – 2009-11-09 19:54:42

您大多只描述了SortedDictionary<T, U>，除了次低/次高值二进制搜索之外，您可以自行实施而不会有太大困难。

SortedDictionary对您而言有没有具体原因？

来源

2009-11-09 19:47:04 mquander

*“你可以自己实现而没有太大困难。”*我不相信你可以轻松地扩展SortedDictionary。从查看元数据，并试图扩展它，必要的内部部分似乎不可访问。我错了吗？ – Catskul 2010-02-03 16:46:20

您的意思是SortedDictionary 是否实现了红黑树？如果你这样做，你在哪里找到这个？我在MSDN页面上看不到任何提及。 – comecme 2011-03-05 21:12:25

是的;我只是通过在Reflector中浏览课程来验证它。在内部，它将密钥放入一个'SortedSet '，它被实现为红/黑树。我不知道我在哪里听说过 - 我感觉MSDN文档的旧版本更详细地讨论了与SortedList相反的'SortedDictionary'的实现。另外，恩，我不完全确定为什么我认为他可以轻松地扩展它。目前还不清楚他可以。好吧。 – mquander 2011-03-06 03:17:50

从C5集合库中取出TreeSet。

来源

2009-11-09 19:46:44

这正是PowerCollections中的OrderedDictionary。它与SortedDictionary（具有泛型的红黑树）非常相似，并增加了设置开始键/结束键的功能，并扫描该范围内的所有值。

SortedDicionary只允许公开一个从集合开始处开始的GetEnumerator（）函数，并且只允许进行MoveNext（）调用，所以即使使用LINQ也没有任何魔法发生：它从一开始就运行表达式按顺序排列，直到找到与您的LINQ表达式匹配的表达式。

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

尽管如此：PowerCollections OrderedDictionary中的枚举器是使用“yield”实现的，内存使用情况和枚举性能至少为O（n^2）...您可以自己更改实现实施传统的统计员，这两个问题都会消失。如果我能找到时间，我会将该补丁提交给Codeplex。

来源

2013-02-11 19:09:00 huntharo

在C＃实现红 - 黑树的

回答

相关问题