我在互联网上看到了一些关于此的引用，但没有官方文档？谁能告诉我在哪里可以得到这方面的信息？
问问题
14786 次
5 回答
32
这不应该被记录，因为它是一个实现细节。
例如，有不止一种实现SortedDictionary：有微软的，也有 Mono 的实现。
事实上，Mono 实现在其当前版本 (2.10.9) 中确实使用了红黑树。当前的 .NET 版本也是如此（您可以通过反编译代码来发现这一点，例如使用Reflector或MonoDevelopildasm.exe中的内置 IL 查看器）。
但是，这可能会在未来发生变化，因为实际上有更有效的实现（如B 树）。
所以，再说一遍：这个信息没有用，它是一个实现细节，它很可能会改变。
于 2013-02-16T12:47:25.190 回答
8
这是MSDN页面上的官方文档；
SortedDictionary 泛型类是具有 O(log n) 检索的二叉搜索树，其中 n 是字典中的元素数
SortedDictionery 是红黑树吗？
好吧，我不太熟悉，red-black tree但我只是用（免费）反编译SortedDictionary了类，dotPeek但红黑树的删除算法和 SortedDictionary 的 Remove() 方法的代码似乎并不相似。所以，我的钱是用于No。
SortedDictionary始终保持其键排序。它使您可以避免自己对键进行排序。它的查找性能比Dictionary. 如果您需要在内存中排序查找表，它具有优势。
Dictionary lookup time: Close to O(1)
SortedDictionary lookup time: O(log n)
从 中查看更多详细信息here。
于 2013-02-16T11:45:11.383 回答
5
文档似乎确实保证了从 BST 检索的 O(log n)。如果他们针对可能的树报告“平均”，那么即使是非平衡实现也可以声称这一点。即使这是一个更坏的情况保证，这与作为 BST 一起也不足以说明它是否被实现为红黑树而不诉诸反编译。它也可以是 AVL、splay 或其他一些平衡变体。
我拔出了点窥视。在 4.0.0.0 系统组件上。OrderedDictionary 使用 Treeset，它是 SortedSet 的子类。这看起来很可能是一棵红黑树。但是，它并不是典型的例子，类似于网络上的许多例子，这些例子实现了插入或删除后的平衡。该实现主要是迭代的，并且插入似乎在向下而不是在插入之后修复颜色（自上而下 - 有几篇关于这种方法的论文）。删除时出现了类似的情况，但没有时间验证它。当然不是直接可比的东西。
至少，我的猜测是它应该具有类似的运行时特性。当它到达插入/删除点时，它并没有做太多事情，因为这一切都是在下降的过程中完成的。
于 2013-08-23T17:24:27.383 回答
2
从其 MSDN 页面：
SortedDictionary 泛型类是具有 O(log n) 检索的二叉搜索树，其中 n 是字典中的元素数
于 2013-02-16T11:41:24.670 回答
1
您可以对其进行反编译（例如使用 Reflector）...但是因为这是一个“实现细节”，我不会依赖它，它可以随时通过任何更新进行更改。
不确定这样的实现细节有多相关，但如果你真的需要一棵红黑树，那么明确地实现它......其他任何事情都是“技术债务”/“等待发生的灾难”恕我直言。
于 2013-02-16T11:42:16.970 回答