SortedDictionary 是红黑树吗？

Question

我在互联网上看到了一些关于此的引用，但没有官方文档？谁能告诉我在哪里可以得到这方面的信息？

Answer 1

这不应该被记录下来，因为它是一个实现细节。

例如，

SortedDictionary

有不止一种实现：有 Microsoft 的，也有 Mono 实现的。

事实上，Mono 实现在其当前版本（2.10.9）中确实使用了红黑树。当前的 .NET 版本也是如此（您可以通过反编译代码来发现这一点，例如使用 Reflector、

ildasm.exe

或 MonoDevelop 中的内置 IL 查看器）。

但是，这可能将来会改变，因为实际上有更有效的实现（如B树）。

所以，再说一遍：这些信息没有用，它是一个实现细节，并且它将很有可能发生变化。

Answer 2

这是来自

MSDN

页面的官方文档；

SortedDictionary 泛型类是一个二叉搜索树，具有 O(log n) 检索，其中 n 是字典中元素的数量

---

SortedDictionary 是红黑树吗？

嗯，我不太熟悉

red-black tree

，但我只是用SortedDictionary

（免费的）反编译了

dotPeek类，但是红黑树的删除算法和SortedDictionary的Remove()方法代码看起来不相似。所以，我的钱是用来不。

SortedDictionary

保持其键始终排序。它可以让您避免自己对键进行排序。它的查找性能比

Dictionary

慢。如果您需要内存中的排序查找表，它具有优势。

Dictionary lookup time:       Close to O(1)
SortedDictionary lookup time: O(log n) 

查看更多详情

here

。

Answer 3

文档似乎确实保证从 BST 检索的时间复杂度为 O(log n)。如果他们对可能的树进行“平均”报告，那么即使是非平衡实现也可以声明这一点。即使这是最坏的情况保证，这与 BST 一起也不足以说明它是否作为红黑树实现，而不需要反编译。它也可以是 AVL、splay 或其他一些平衡品种。

我拿出了点窥视。关于 4.0.0.0 系统组件。 OrderedDictionary 使用 Treeset，它是 SortedSet 的子类。这看起来确实很可能是一棵红黑树。然而，这并不是像网上很多例子那样实现插入或删除后平衡的典型例子。该实现主要是迭代的，并且插入似乎是在向下的过程中而不是在插入之后修复颜色（自上而下 - 有几篇关于这种方法的论文）。删除时也出现了类似的情况，但没有时间验证。当然不是直接可比的东西。

至少，我的猜测是它应该具有类似的运行时特性。当它到达插入/删除点时，它并没有做太多事情，因为它都是在下行过程中完成的。

Answer 4

来自其 MSDN 页面：

SortedDictionary 泛型类是一个二叉搜索树，检索时间为 O(log n)，其中 n 是字典中的元素数量

Answer 5

您可以反编译它（例如使用 Reflector）...但由于这是一个“实现细节”，我不会依赖它，它可以随时通过任何更新进行更改。

不确定这样的实现细节有多相关，但如果你真的需要一棵红黑树，那么明确地实现它......其他任何东西都将是“技术债务”/“等待发生的灾难”恕我直言。

Answer 6

真正的问题： “SortedDictionary 是否实现为平衡树？” 如果不是，那么当按排序顺序插入数据时，搜索性能将下降到 O(n)，就像顺序链表一样。如果数据被写出到文件（按排序顺序）然后读回到不平衡树中，就会发生这种情况。很难想象微软不会将其实现为某种平衡树。 他们可能会改变他们的做法，但只要树保持相当好的平衡就没有多大关系。