Implementation of Red-Black Tree in C#

I'm looking for an implem开发者_如何学编程entation of a Red-Black Tree in C#, with the following features:

• Search, Insert and Delete in O(log n).
• Members type should be generic.
• Support in Comparer(T), for sorting T by different fields in it.
• Searching in the tree should be with the specific field, so it won't accept T, but it'll accept the field type sorting it.
• Searching shouldn't be only exact value. Should support searching the lower/higher one.

Thank you.

You mostly just described SortedDictionary<T, U>, except for the next-lowest/next-highest value binary search, which you could implement on your own without much difficulty.

Are there specific reasons that SortedDictionary is insufficient for you?

Rip the TreeSet from C5 collection libs.

This is exactly the OrderedDictionary in PowerCollections. It's pretty much identical to SortedDictionary (red black tree with generics) with the addition of the ability to set a start key/end key and scan all values in that range.

SortedDicionary only allows exposes a GetEnumerator() function that starts at the beginning of the collection and only allows a MoveNext() call, so even if you use LINQ there is nothing magic happening: it starts at the beginning and runs your expression on every single node, in order, until it finds those matching your LINQ expression.

OrderedDictionary has a function that gets an enumerator at or before a particular key and that does the lookup in O(log n).

A word of caution though: the enumerator in the PowerCollections OrderedDictionary is implemented using "yield" and the memory usage and enumeration performance is at least O(n^2)... you can change the implementation yourself to make it implement a traditional enumerator and both of these problems go away. I'll submit that patch to Codeplex if I can ever find the time.