Menu
I saw several quotes about this on the Internet but no official documentation? Can anyone tell me where I can get information about this?
425
A red-black tree is a kind of self-balancing binary search tree where each node has an extra bit, and that bit is often interpreted as the color (red or black). These colors are used to ensure that the tree remains balanced during insertions and deletions.
Rules That Every Red-Black Tree Follows:The root of the tree is always black. There are no two adjacent red nodes (A red node cannot have a red parent or red child). Every path from a node (including root) to any of its descendants NULL nodes has the same number of black nodes. All leaf nodes are black nodes.
Definition of a red-black tree A red-black tree is a binary search tree which has the following red-black properties: Every node is either red or black. Every leaf (NULL) is black. If a node is red, then both its children are black.
In a 1978 paper, "A Dichromatic Framework for Balanced Trees", Leonidas J. Guibas and Robert Sedgewick derived the red–black tree from the symmetric binary B-tree. The color "red" was chosen because it was the best-looking color produced by the color laser printer available to the authors while working at Xerox PARC.
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.
64
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.
37
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
