Implementation of Red-Black Tree in C#

Question

I'm looking for an implementation 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.

Answer 1

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?

Answer 2

Rip the TreeSet from C5 collection libs.

Answer 3

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.