Red Black Tree implementation?
duncan smith
buzzard at invalid.invalid
Wed May 8 19:21:50 EDT 2013
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
More information about the Python-list
mailing list