Is SortedDictionary a red-black tree?
Solution 1
This isn’t supposed to be documented since it’s an implementation detail.
For instance, there is more than one implementation of SortedDictionary
: there’s Microsoft’s and there’s the Mono implementation.
And the Mono implementation does, in fact, use a red-black tree in its current version (2.10.9). So does the current .NET version (you can find that out by decompiling the code, for instance by using Reflector, ildasm.exe
or the built-in IL viewer in MonoDevelop).
However, this is probably going to change in the future since there are actually more efficient implementations (as B trees).
So, again: this information isn’t useful, it’s an implementation detail, and it is going to change with high probability.
Solution 2
This is the official documentation from MSDN
page;
The SortedDictionary generic class is a binary search tree with O(log n) retrieval, where n is the number of elements in the dictionary
Is SortedDictionery a red-black tree?
Well, I'm not too much fimiliar with red-black tree
but I just decompiled SortedDictionary
class with dotPeek
(which is free) but red-black tree's deletion algorithm and SortedDictionary's Remove() method's code doesn't seems similar. So, my money is for No.
SortedDictionary
keeps its keys always sorted. It allows you to avoid sorting the keys on your own. Its lookup performance is slower than Dictionary
. It has advantages if you require a sorted lookup table in memory.
Dictionary lookup time: Close to O(1)
SortedDictionary lookup time: O(log n)
Check out more details from here
.
Solution 3
Documentation does seem to guarantee O(log n) for retrieval from a BST. If they are reporting "on average" with respective to possible trees then even non-balancing implementations can claim that. Even if it were a worse case guarantee, this together with being a BST isn't enough to say whether it is or isn't implemented as a red-black trees without resorting to decompiling. It could also be an AVL, splay, or some other balancing variety.
I pulled out dot peek. On The 4.0.0.0 System Assembly. OrderedDictionary uses Treeset which subclasses SortedSet. This does appear likely to be a red-black tree. However, it is not the typical example similar to many examples on the web these implement balancing after insertion or deletion. The implementation is primarily iterative, and the insert appears to fix the colors on the way down instead of after the insertion (top-down - there are a couple papers on this sort of approach). Something similar was up with the removal, but don't have time to verify it. Certainly not something directly comparable.
At the very least, my guess is it should have a similar kind of run-time characteristic. By the time it gets to the insert/deletion point there isn't much it does since it was all done on the way down.
Solution 4
From its MSDN page:
The SortedDictionary generic class is a binary search tree with O(log n) retrieval, where n is the number of elements in the dictionary
Solution 5
You can decompile it (for example with Reflector)... BUT since that is an "implementation detail" I would not rely on it, it could be changed anytime with any update.
Not sure how relevant such an implementation detail is but if you really need a RedBlack tree THEN implement it explicitly... anything else would be "technical debt" / "desaster waiting to happen" IMHO.
Related videos on Youtube
![Nahum](https://i.stack.imgur.com/SEZKp.jpg?s=256&g=1)
Nahum
a Software Engineer & a Geek, linkedin: http://il.linkedin.com/in/lnahum/ careers2.0: https://careers.stackoverflow.com/nahumlitvin
Updated on November 08, 2022Comments
-
Nahum over 1 year
I saw several quotes about this on the Internet but no official documentation? Can anyone tell me where I can get information about this?
-
Konrad Rudolph over 11 yearsNot sure what you decompiled but
SortedDictionary
internally just usesTreeSet
which is an internal class and, yes, is implemented in terms of a red-black tree. -
Soner Gönül over 11 years@KonradRudolph Hmm, I decompiled
Remove()
method which its usedinternal virtual bool DoRemove(T item)
method but it doesn't seems any fimiliar thing withred-black tree
's (Which is a binary tree search ) deletion algorithm. Am I missing here what? -
Konrad Rudolph over 11 yearsI haven’t actually got access to the .NET implementation at the moment (I’m on Mac) but I’ve checked related resources and the Rotor reference implementation (which of course is not official) and I am all but certain that
SortedDictionary
does useTreeSet
which is a red-black tree. -
Konrad Rudolph over 11 yearsWhat’s more, the MSDN article in fact guarantees that (the current implementation of)
SortedDictionary
is a binary search tree so your assessment of theDoRemove
method must be erroneous. Having said that, it’s weird that the MSDN is actually specific on this point because as I’ve written in my answer, the fact that a binary search tree (rather than a generalised search tree) is used is an implementation detail, and it’s bound to change so this info has no place in the MSDN. -
sam over 9 yearsReference Source confirmes that it's a Red-Black tree (at least in 4.5.2); referencesource.microsoft.com/#System/compmod/system/…
-
Greg Graham about 5 yearsThis doesn't answer the question.
-
Konrad Rudolph about 5 years@GregGraham How doesn’t it? I’m clearly explaining what the current (at the time of answering) implementations are doing, and why this information shouldn’t be relied on in the future. What else are you missing from the answer?