On 07/05/13 02:20, Dan Stromberg wrote:
On Mon, May 6, 2013 at 5:55 PM, duncan smith <buzzard@invalid.invalid <mailto:buzzard@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
