Red Black Tree implementation?

[duncan smith]

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