Red black trees

[clayasaurus]

Walter Bright wrote:
> Red black trees are one of those basic collection types that should be 
> available. Anyone want to write one for D for placement into Phobos?

I've been trying to write one based off of a C++ version over the the 
code project (actual link is in the code file).

http://www.dsource.org/projects/arcgames/browser/trunk/physics/d/binarytree.d

However, after I add the third node, I get an access violation. I 
haven't had much time to really sit down and debug it, all I know is 
that somehow I am trying to access a null object which causes an access 
violation. Eventually I'll get it to work, just a matter of time.

---

I also have a doubly linked list with a mergesort (I wrote the list but 
I did not write the merge sort implemtation, again the link where I got 
it from is in there). It seems to work well
http://dsource.org/projects/freeuniverse/browser/trunk/freeuniverse/arc/templates/dlinkedlist.d

Then again, I'm sure the it would need some fixing up and heavy testing, 
plus making sure that the places I got some of the code from would allow 
it to be licensed under public domain before even thinking about putting 
it in a std lib. Just thought I'd mention them in case anyone finds it 
useful.

~ Clay S.