Implementation of Red-Black Tree in C#

views:

579

answers:

+1 Q:

Implementation of Red-Black Tree in C#

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.

+1 A:

Rip the TreeSet from C5 collection libs.

rama-jka toti 2009-11-09 19:46:44

+3 A:

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?

mquander 2009-11-09 19:47:04

*"which you could implement on your own without much difficulty."* I don't believe you can easily extend SortedDictionary. From looking at the metadata, and simply trying to extend it, the internal pieces necessary do not seem to be accessible. Am I wrong?

Catskul 2010-02-03 16:46:20

Red-Black Trees in C#
http://www.codeproject.com/KB/recipes/redblackcs.aspx

Robert Harvey 2009-11-09 19:48:28

I tried using the code from this article, but it didn't work for me... Did you try it yourself anytime ??

gillyb 2010-02-22 21:38:45

@gillyb: Arrgghh...No, I haven't tried it. If that implementation doesn't work, the C5 Generic Collection Library's `TreeSet` algorithm has a red-black tree implementation that should work. http://www.itu.dk/research/c5/

Robert Harvey 2010-02-22 22:56:10

ansaurus

tags:

views:

answers:

Implementation of Red-Black Tree in C#

related questions