Red Black Tree implementation?

[Dan Stromberg]

OK, I've got one copy of trees.py with md5
211f80c0fe7fb9cb42feb9645b4b3ffe.  You seem to be saying I should have
two though, but I don't know that I do...


On 5/8/13, duncan smith <buzzard at invalid.invalid> wrote:
> On 07/05/13 02:20, Dan Stromberg wrote:
>>
>> On Mon, May 6, 2013 at 5:55 PM, duncan smith <buzzard at invalid.invalid
>> <mailto:buzzard at invalid.invalid>> wrote:
>>
>>
>
> [snip]
>
>>
>> I'd prefer Apache or MIT or BSD 3-clause, but I could probably work with
>> this.
>> http://joinup.ec.europa.eu/community/eupl/news/licence-proliferation-way-out
>>
>> I'm eager to see the code, and would love it if you sorted out the
>> deletion rebalance issue.
>>
>> I just plunked some time into
>> https://github.com/headius/redblack/blob/master/red_black_tree.py , only
>> to find that it didn't appear to be doing deletions correctly - the tree
>> would become unprintable after deleting one element.  It's possible I
>> introduced the bug, but right now I don't particularly suspect so,
>> having not changed the __del__ method.
>>
>> I'm starting to think Red Black Trees are pretty complex.
>>
>>
>
> Mine is fixed now (sent to your gmail address). Restoring the tree
> properties after deletion is awkward to get right, and doesn't affect
> the performance noticeably for smallish trees if you get it wrong.
>
> I realised my code was buggy when I tried adding, then removing a
> million items and ran into the recursion limit. It now passes a test
> where I check the tree properties after each addition / deletion.
>
> Duncan
> --
> http://mail.python.org/mailman/listinfo/python-list
>