SortedDictionary是红黑树吗？
我在互联网上看到了几个关于此的引用，但没有官方文档？ 谁能告诉我在哪里可以获得有关此信息？
这不应该被记录，因为它是一个实现细节 。
例如， SortedDictionary有多个实现：有微软，还有Mono实现。
事实上，Mono实现在其当前版本（2.10.9）中使用了红黑树。 当前的.NET版本也是如此（您可以通过反编译代码来找到它，例如通过使用Reflector ， ildasm.exe或MonoDevelop中的内置IL查看器）。
但是，这可能会在未来发生变化，因为实际上有更高效的实现 （如B树 ）。
所以，再次说明：这些信息没有用，它是一个实现细节，并且它将以很高的概率发生变化。
这是MSDN页面的官方文档;
SortedDictionarygenerics类是一个带有O（log n）检索的二叉搜索树，其中n是字典中元素的数量
SortedDictionery是红黑树吗？
好吧 ，我不是太熟悉red-black tree但我只是用dotPeek （这是免费的）反编译SortedDictionary类，但红黑树的删除算法和SortedDictionary的Remove（）方法的代码似乎并不相似。 所以，我的钱是No。
SortedDictionary保持其键始终排序。 它允许您避免自己对键进行排序。 它的查找性能比Dictionary 。 如果您需要在内存中排序的查找表，它具有优势。
Dictionary lookup time: Close to O(1) SortedDictionary lookup time: O(log n)
从here查看更多详细信息。
文档确实似乎保证从BST检索O（log n）。 如果他们“平均”报告各自可能的树，那么即使是非平衡的实现也可以声称。 即使它是一个更糟糕的情况保证，这与BST一起还不足以说明它是否实施为红黑树而不采用反编译。 它也可以是AVL，展开或其他一些平衡种类。
我掏出了小偷。 在4.0.0.0系统程序集上。 OrderedDictionary使用Treeset，它是SortedSet的子类。 这似乎可能是一棵红黑树。 然而，这并不是类似于Web上的许多示例的典型示例，这些示例在插入或删除之后实现平衡。 实现主要是迭代的，并且插入似乎在向下而不是在插入之后修复颜色（自上而下 – 有关于这种方法的几篇论文）。 类似的东西与删除有关，但没有时间来validation它。 当然不是直接可比的东西。
至少，我的猜测是应该有类似的运行时特性。 当它到达插入/删除点时，它没有多少，因为它是在完成的过程中完成的。
从其MSDN页面：
SortedDictionarygenerics类是一个带有O（log n）检索的二叉搜索树，其中n是字典中元素的数量
你可以反编译它（例如使用Reflector）……但是因为这是一个“实现细节”我不会依赖它，它可以随时更改任何更新。
不知道这样的实现细节有多相关，但如果你真的需要一个RedBlack树那么明确地实现它……其他任何东西都是“技术债务”/“等待发生的灾难”恕我直言。