Red black trees

[clayasaurus]

Walter Bright wrote:
> clayasaurus wrote:
>> 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.
> 
> That is great! But the license is critical.

I found out that the merge sort algorithm in my doubly linked list is 
under the MIT license ( 
http://www.opensource.org/licenses/mit-license.php ).

Since I was having problems with the other red black tree algorithms 
presented, I finally found a nice resource for the algorithms ( 
http://eternallyconfuzzled.com/tuts/redblack.html ).

The only problem is, on the page, it doesn't explicitly say whether the 
code is public domain or not. I sent an email to the author about it. My 
best guess is that it is public domain, since the author releases all 
his libraries on his site as such.

My templated red black tree version: 
http://svn.dsource.org/projects/freeuniverse/trunk/freeuniverse/arc/templates/redblacktree.d

I've have only done minimal testing with it, but it hasn't broken on me 
yet.

~ Clay