9

I'm looking for an implementation of aRed-Black Tree in C#, with the following features:

  • Search, Insert and Delete in O(log n).
  • Members type should be generic.
  • Support inComparer(T), for sortingT by different fields in it.
  • Searching in the tree should be with the specific field, so it won't acceptT, 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.

askedNov 9, 2009 at 19:43
Alon Gubkin's user avatar
2
  • 1
    Answering to your other question, named "Book or Teacher", thereally best way to learn programming is towrite programs. Write this one on your own and then you'll learn something.CommentedNov 9, 2009 at 19:47
  • 1
    @Pavel: I could write this, but I'm looking for something ready, so I can continue develop the main sides of my program, and speed up development.CommentedNov 9, 2009 at 19:54

4 Answers4

13

You mostly just describedSortedDictionary<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 thatSortedDictionary is insufficient for you?

answeredNov 9, 2009 at 19:47
mqp's user avatar
Sign up to request clarification or add additional context in comments.

3 Comments

"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?
Do you mean the SortedDictionary<T, U> implements a Red-Black Tree? If you do, where did you find this? I don't see any mention of it on the MSDN pages.
Yes; I just verified it by skimming the class in Reflector. Internally, it puts the keys into aSortedSet<T>, which is implemented as a red/black tree. I'm not sure where I heard about it -- I feel like an old version of the MSDN documentation went into more detail about the implementation ofSortedDictionary in contrast toSortedList. Also, umm, I'm not exactly sure why I thought he could easily extend it. It isn't clear that he could. Oh well.
2

Rip the TreeSet from C5 collection libs.

answeredNov 9, 2009 at 19:46
rama-jka toti's user avatar

Comments

0

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.

answeredFeb 11, 2013 at 19:09
huntharo's user avatar

Comments

0

System.Collections.Generic.SortedSet is implemented as a red-black tree.

answeredMay 12, 2023 at 16:38
Mark Lauter's user avatar

Comments

Your Answer

Sign up orlog in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

By clicking “Post Your Answer”, you agree to ourterms of service and acknowledge you have read ourprivacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.