Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #44870

Re: Red Black Tree implementation?

Show all headers | View raw

[Multipart message — attachments visible in raw view] - view raw

On Mon, May 6, 2013 at 5:55 PM, duncan smith <buzzard@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.

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Red Black Tree implementation? Dan Stromberg <drsalists@gmail.com> - 2013-05-01 16:11 -0700
  Re: Red Black Tree implementation? duncan smith <buzzard@invalid.invalid> - 2013-05-02 03:06 +0100
    Re: Red Black Tree implementation? Dan Stromberg <drsalists@gmail.com> - 2013-05-02 19:00 -0700
      Re: Red Black Tree implementation? duncan smith <buzzard@invalid.invalid> - 2013-05-07 01:55 +0100
        Re: Red Black Tree implementation? Chris Angelico <rosuav@gmail.com> - 2013-05-07 11:21 +1000
        Re: Red Black Tree implementation? Dan Stromberg <drsalists@gmail.com> - 2013-05-06 18:20 -0700
          Re: Red Black Tree implementation? duncan smith <buzzard@invalid.invalid> - 2013-05-07 14:28 +0100
          Re: Red Black Tree implementation? duncan smith <buzzard@invalid.invalid> - 2013-05-09 00:21 +0100
            Re: Red Black Tree implementation? Dan Stromberg <drsalists@gmail.com> - 2013-05-08 18:40 -0700
              Re: Red Black Tree implementation? duncan smith <buzzard@invalid.invalid> - 2013-05-09 05:31 +0100
              Re: Red Black Tree implementation? duncan smith <buzzard@invalid.invalid> - 2013-05-09 14:52 +0100
                Re: Red Black Tree implementation? Dan Stromberg <drsalists@gmail.com> - 2013-05-11 16:24 -0700
                Re: Red Black Tree implementation? duncan smith <buzzard@invalid.invalid> - 2013-05-12 02:34 +0100
                Re: Red Black Tree implementation? Dan Stromberg <drsalists@gmail.com> - 2013-05-11 18:29 -0700
                Re: Red Black Tree implementation? duncan smith <buzzard@invalid.invalid> - 2013-05-12 03:02 +0100
                Re: Red Black Tree implementation? duncan smith <buzzard@invalid.invalid> - 2013-05-12 19:15 +0100

csiph-web