Red Black Tree implementation?

[duncan smith]

On 03/05/13 03:00, Dan Stromberg wrote:
>
> On Wed, May 1, 2013 at 7:06 PM, duncan smith <buzzard at invalid.invalid
> <mailto:buzzard at invalid.invalid>> wrote:
>
>     I have an implementation that you can try out. It's not based on any
>     other implementation, so my bugs will be independent of any bugs in
>     the code you're currently using. It looks more like a set - add,
>     remove, discard. Not tried on Python 3 or run through pylint. I just
>     tried adding a million items to a tree, and it takes about 25%
>     longer to add items at the end compared to those at the beginning.
>     Timing removals uncovered a bug. So if you want the code I'll fix
>     the bug and send it (to your gmail e-mail address?). Cheers.
>
>     Duncan
>     --
>     http://mail.python.org/__mailman/listinfo/python-list
>     <http://mail.python.org/mailman/listinfo/python-list>
>
>
> 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.

Duncan