Just a few minutes ago, I was looking for something in the System. Collections.Generic using Reflector. I turned on visibility for Private members in options and then I saw something new, a TreeSet<T>. A few days before I was playing with tree structures, so this class turned my attention. After a short search on google, I found a kinf of documentation on Danish university webpage.
An implementation of Red-Black trees as an indexed, sorted collection with set semantics, cf. CLRS. TreeBag<T> for a version with bag semantics. TreeDictionary<K,V> for a sorted dictionary based on this tree implementation. The comparer (sorting order) may be either natural, because the item type is comparable (generic: or non-generic: System.IComparable) or it can be external and supplied by the user in the constructor.TODO: describe performance hereTODO: discuss persistence and its useful usage modes. Warn about the space leak possible with other usage modes.
What the Red-Black tree is? According to Wikipedia:
A red-black tree is a type of self-balancing binary search tree, a data structure used in computer science, typically used to implement associative arrays. The original structure was invented in 1972 by Rudolf Bayer who called them "symmetric binary B-trees", but acquired its modern name in a paper in 1978 by Leo J. Guibas and Robert Sedgewick. It is complex, but has good worst-case running time for its operations and is efficient in practice: it can search, insert, and delete in O(log n) time, where n is the number of elements in the tree.
Sounds great but … this is the internal class in System.Collections.Generic. Has anyone the slightest idea why is this class still kept in secret internal goods? That could be so useful. That is not fair.
I am going to cry alone.