Red Black Tree implementation?

[Dan Stromberg]

On Mon, May 6, 2013 at 5:55 PM, duncan smith <buzzard at invalid.invalid>wrote:

>
> What license?
>>
>> Thanks!
>>
>>
> Here's the text I usually prepend.
>
>
> ##Copyright (c) 2013 duncan g. smith
> ##
> ##Permission is hereby granted, free of charge, to any person obtaining a
> ##copy of this software and associated documentation files (the
> "Software"),
> ##to deal in the Software without restriction, including without limitation
> ##the rights to use, copy, modify, merge, publish, distribute, sublicense,
> ##and/or sell copies of the Software, and to permit persons to whom the
> ##Software is furnished to do so, subject to the following conditions:
> ##
> ##The above copyright notice and this permission notice shall be included
> ##in all copies or substantial portions of the Software.
> ##
> ##THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
> ##OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
> MERCHANTABILITY,
> ##FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
> ##THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
> ##OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
> ##ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
> ##OTHER DEALINGS IN THE SOFTWARE.
>
>
> Basically, "do what you want with it but don't blame me if it goes tits
> up". I'm happy to consider tidying it up a bit and using a more recognized
> form of licence. Just had a bank holiday here, so bug not yet squashed. But
> it is the sort of bug that might account for what you've seen (if a similar
> bug exists in the code you've been using). The tree doesn't always get
> properly rebalanced on node removals. I'll attack the problem later
> tomorrow (technically, later today). Cheers.
>

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20130506/0b579527/attachment.html>