SortedDictionary是红黑树吗？
Nah*_*hum 15 .net c# binary-tree sorteddictionary
我在互联网上看到了几个关于此的引用,但没有官方文档？谁能告诉我在哪里可以获得有关此信息？
Kon*_*lph 28
这不应该被记录,因为它是一个实现细节.
例如,有多个实现SortedDictionary:有微软,有Mono实现.
事实上,Mono实现在其当前版本(2.10.9)中使用了红黑树.如此做当前.NET版本(你可以发现,通过进行反编译的代码,例如通过使用反射,ildasm.exe或内置在IL观众MonoDevelop中).
但是,这可能会在未来发生变化,因为实际上有更高效的实现(如B树).
所以,再次说明:这些信息没有用,它是一个实现细节,并且很有可能发生变化.
- @GregGraham 怎么样？我清楚地解释了*当前*（在回答时）实现正在做什么，以及为什么将来不应该依赖这些信息。你从答案中还遗漏了什么？ (5认同)
- 这并不能回答问题。 (3认同)
这是MSDN页面的官方文档;
SortedDictionary泛型类是一个带有O(log n)检索的二叉搜索树,其中n是字典中元素的数量
SortedDictionery是红黑树吗？
好吧,我不是太熟悉,red-black tree但我只是反编译SortedDictionary类dotPeek(这是免费的)但红黑树的删除算法和SortedDictionary的Remove()方法的代码似乎并不相似.所以,我的钱是否定的.
SortedDictionary保持其键始终排序.它允许您避免自己对键进行排序.它的查找性能比慢Dictionary.如果您需要在内存中排序的查找表,它具有优势.
Dictionary lookup time: Close to O(1)
SortedDictionary lookup time: O(log n)
查看更多详细信息here.
- 不确定你反编译但是`SortedDictionary`内部只使用`TreeSet`这是一个内部类,是的,是用红黑树实现的. (2认同)
小智 5
文档确实似乎保证从BST检索O(log n).如果他们报告"平均"与可能的树相对应,那么即使非平衡实现也可以声称.即使它是一个更糟糕的案例保证,这与BST一起还不足以说明它是否实施为红黑树而不采用反编译.它也可以是AVL,展开或其他一些平衡种类.
我掏出了小偷.在4.0.0.0系统程序集上.OrderedDictionary使用Treeset,它是SortedSet的子类.这似乎可能是一棵红黑树.然而,这并不是类似于Web上的许多示例的典型示例,这些示例在插入或删除之后实现平衡.实现主要是迭代的,并且插入似乎在向下而不是在插入之后修复颜色(自上而下 - 这种方法有几篇论文).类似的东西与删除有关,但没有时间来验证它.当然不是直接可比的东西.
至少,我的猜测是应该有类似的运行时特性.当它到达插入/删除点时,它没有太大的作用,因为它是在完成的过程中完成的.