SortedDictionary是一种红黑树吗？

Question

我在互联网上看到了几个关于此事的引用，但没有官方文件。 有人能告诉我在哪里获取相关信息吗？

我在互联网上看到了几个关于此事的引用，但没有官方文献。有人可以告诉我在哪里可以获取这方面的信息吗？

- Nahum

Answer 1

这不应该被记录，因为这是一项实现细节。

例如，SortedDictionary 有多个实现：有Microsoft的，也有Mono的实现。

事实上，Mono实现的当前版本（2.10.9）确实使用红黑树。 .NET的当前版本也是如此（您可以通过反编译代码找到该信息，例如使用Reflector，ildasm.exe或MonoDevelop中内置的IL查看器）。

然而，由于存在更有效的实现方式（如B树），这很可能会在未来发生变化。

因此，再次强调：这些信息并没有用处，它们只是实现细节，并且很可能会改变。

- Konrad Rudolph

---

这并没有回答问题。 - Greg Graham

@GregGraham，它为什么不行？我很清楚地解释了当前（回答时）实现的情况，以及为什么将来不应该依赖这些信息。您还需要从答案中获取什么信息吗？ - Konrad Rudolph

Answer 2

这是来自MSDN官方文档的内容：

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

---

SortedDictionery是红黑树吗？

好吧，我不太熟悉红黑树，但我刚刚使用免费的dotPeek反编译了SortedDictionary类，但红黑树的删除算法和SortedDictionary的Remove()方法的代码似乎不相似。所以，我的答案是不是。 SortedDictionary始终保持其键值排序。它允许您避免自己对键进行排序。它的查找性能比Dictionary慢。如果您需要在内存中进行排序的查找表，则具有优势。

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

请查看更多详细信息，点击这里。

- Soner Gönül

---

不确定你反编译了什么，但 SortedDictionary 内部只是使用了 TreeSet，它是一个内部类，并且确实是基于红黑树实现的。 - Konrad Rudolph

@KonradRudolph 嗯，我反编译了 Remove() 方法，它使用了 internal virtual bool DoRemove(T item) 方法，但似乎没有任何类似于 红黑树 的（这是一种二叉搜索树）删除算法。我错过了什么吗？ - Soner Gönül

我目前实际上没有访问.NET实现的权限（我在Mac上），但我已经检查了相关资源和Rotor参考实现（当然不是官方的），我几乎可以确定SortedDictionary使用的是红黑树，即TreeSet。 - Konrad Rudolph

此外，MSDN文章实际上保证（当前实现的）SortedDictionary是一棵二叉搜索树，因此您对DoRemove方法的评估必须是错误的。话虽如此，MSDN实际上在这一点上非常奇怪，因为正如我在答案中所写的那样，使用二叉搜索树（而不是广义搜索树）是一个实现细节，它肯定会改变，因此这些信息在MSDN中没有任何地方。 - Konrad Rudolph

参考源代码确认这是一棵红黑树（至少在4.5.2版本中）; http://referencesource.microsoft.com/#System/compmod/system/collections/generic/sortedset.cs - alexn

Answer 3

文档似乎保证了从BST中检索的O(log n)。如果他们报告“平均”与可能的树有关，则即使非平衡实现也可以声明。即使它是更糟糕的情况，这个与BST一起并不足以说它是否实现为红黑树，而不必诉诸反编译。它也可以是AVL、Splay或其他平衡品种。

我使用dot peek查看了4.0.0.0系统程序集。OrderedDictionary使用Treeset，它是SortedSet的子类。这似乎很可能是红黑树。然而，它并不是类似于网上许多例子的典型示例，在插入或删除之后进行平衡。实现主要是迭代的，插入似乎在下行时修复颜色，而不是在插入之后（自上而下 - 有几篇关于这种方法的论文）。移除也有类似的情况，但没有时间验证。肯定不是直接可比较的东西。

至少，我的猜测是它应该具有类似的运行时间特征。当它到达插入/删除点时，它所做的事情并不多，因为所有操作都在下行时完成了。

- ptthiem

Answer 4

从MSDN页面得知：

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

- CodeCaster

Answer 5

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

不确定这样的实现细节有多相关，但如果你真的需要一个红黑树，那么请明确地实现它... 否则，其他任何东西都将成为“技术债务”/“等待发生的灾难”在我看来。

- Yahia

---

为什么要反编译，当微软将 .Net 发布为开源时？http://referencesource.microsoft.com/#System/compmod/system/collections/generic/sorteddictionary.cs - nivs1978

Answer 6

真正的问题是："SortedDictionary是否实现为平衡树？" 如果不是的话，当数据按排序顺序插入时，搜索性能将降至O(n)，就像顺序链表一样。如果数据以排序顺序写入文件，然后再读入一个不平衡的树中，这种情况就会发生。很难想象Microsoft不会将其实现为某种平衡树。 他们可能会改变实现方式，但只要树保持相对平衡，这并不重要。

- Thomas Fernandez

---

这并没有回答问题。一旦你有足够的声望，你就可以评论任何帖子；相反，提供不需要提问者澄清的答案。- 来自评论 - undefined

用户问是否SortedDictionary是以红黑树实现的。我的观点是这并不重要，重要的是树是否平衡。一个简单的二叉树可能是不平衡的，性能也会很差。红黑树是平衡的，但也有其他方法来保持树的平衡，这些方法也是可以的。你说得对，我没有给出正确的答案给提问者。我做的是给出了正确的问题。 - undefined