Search code examples
c#red-black-tree

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.

Solution

  • 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?