Re: Red Black Tree implementation?

Path	csiph.com!usenet.pasdenom.info!gegeweb.org!de-l.enfer-du-nord.net!feeder2.enfer-du-nord.net!feeds.phibee-telecom.net!newsfeed.xs4all.nl!newsfeed4.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
Return-Path	<drsalists@gmail.com>
X-Original-To	python-list@python.org
Delivered-To	python-list@mail.python.org
X-Spam-Status	OK 0.008
X-Spam-Evidence	'H': 0.98; 'S': 0.00; 'tree': 0.05; 'method.': 0.07; 'dan': 0.09; 'skip:2 30': 0.09; 'trees': 0.09; 'url:github': 0.09; 'apache': 0.15; '__del__': 0.16; 'address).': 0.16; 'bsd': 0.16; 'bug,': 0.16; 'buggy': 0.16; 'deletion': 0.16; 'deletions': 0.16; 'element.': 0.16; 'limit.': 0.16; 'md5': 0.16; 'to:name:python list': 0.16; 'url:py': 0.16; 'eager': 0.16; 'wrote:': 0.18; 'code,': 0.22; 'issue.': 0.22; 'saying': 0.22; 'passes': 0.24; 'mon,': 0.24; "i've": 0.25; 'header:In-Reply- To:1': 0.27; 'tried': 0.27; 'appear': 0.29; 'fixed': 0.29; 'properties': 0.29; "doesn't": 0.30; 'message-id:@mail.gmail.com': 0.30; "i'm": 0.30; 'url:mailman': 0.30; 'code': 0.31; 'subject:skip:i 10': 0.31; 'this.': 0.32; 'probably': 0.32; 'url:python': 0.33; "i'd": 0.34; 'could': 0.34; 'test': 0.35; 'but': 0.35; 'received:google.com': 0.35; 'url:listinfo': 0.36; 'doing': 0.36; "didn't": 0.36; 'possible': 0.36; 'subject:?': 0.36; 'url:org': 0.36; 'should': 0.36; 'url:eu': 0.37; 'so,': 0.37; 'two': 0.37; 'performance': 0.37; 'starting': 0.37; 'gmail': 0.38; 'mine': 0.38; 'to:addr:python-list': 0.38; 'pm,': 0.38; 'though,': 0.39; 'to:addr:python.org': 0.39; 'changed': 0.39; 'url:mail': 0.40; 'deleting': 0.60; 'removing': 0.60; 'affect': 0.61; 'black': 0.61; 'introduced': 0.61; 'become': 0.64; 'love': 0.65; 'smith': 0.68; 'million': 0.74; 'subject:Red': 0.84; 'url:master': 0.84; '2013': 0.98
DKIM-Signature	v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:x-received:in-reply-to:references:date:message-id :subject:from:to:content-type; bh=1DMXSRxY0j9dhgO6MccEISojK+16P5lCIT5ZF2DY8HM=; b=LzYRzTbqVAYrv8JPaxbfq5NsGVIgj8TLJITNwd4DBn6ToHocLI3+y9mOOsyztQ21U8 pMFIZ+vMK9A0KqJcdK4Madu46Gw2ujMDaa5a7Qi/b63Q5Uh5lB5BVjaYV21O7Vt+GnTB bEPuCdmKtjN3+qrRBOejQoM2YRMkAERrZvQ+aOi4keUynbVebHrW3HtaGyTetnXyYa9v 862RCSqpP2f+CH3rAYI9gbw8l76QDLtH40ncNZnwiKUO0Ym2TD+piplN8MFL44BygiMd ZomPVBIBMuHvDDe2NKk4TPncJ1a3omIPItkkh4hcitP/RpX1FX4UPjVozQPh1uyvKHQe v8ig==
MIME-Version	1.0
X-Received	by 10.49.81.179 with SMTP id b19mr7627121qey.46.1368063606840; Wed, 08 May 2013 18:40:06 -0700 (PDT)
In-Reply-To	<518ade0f$1$60230$862e30e2@ngroups.net>
References	<mailman.1225.1367449881.3114.python-list@python.org> <5181ca0e$0$13974$862e30e2@ngroups.net> <mailman.1260.1367546417.3114.python-list@python.org> <518850f8$0$8157$862e30e2@ngroups.net> <mailman.1393.1367889616.3114.python-list@python.org> <518ade0f$1$60230$862e30e2@ngroups.net>
Date	Wed, 8 May 2013 18:40:06 -0700
Subject	Re: Red Black Tree implementation?
From	Dan Stromberg <drsalists@gmail.com>
To	Python List <python-list@python.org>
Content-Type	text/plain; charset=ISO-8859-1
X-BeenThere	python-list@python.org
X-Mailman-Version	2.1.15
Precedence	list
List-Id	General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe	<http://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive	<http://mail.python.org/pipermail/python-list/>
List-Post	<mailto:python-list@python.org>
List-Help	<mailto:python-list-request@python.org?subject=help>
List-Subscribe	<http://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups	comp.lang.python
Message-ID	<mailman.1473.1368063609.3114.python-list@python.org> (permalink)
Lines	46
NNTP-Posting-Host	2001:888:2000:d::a6
X-Trace	1368063609 news.xs4all.nl 15865 [2001:888:2000:d::a6]:39933
X-Complaints-To	abuse@xs4all.nl
Xref	csiph.com comp.lang.python:44988

Show key headers only | View raw

OK, I've got one copy of trees.py with md5
211f80c0fe7fb9cb42feb9645b4b3ffe.  You seem to be saying I should have
two though, but I don't know that I do...


On 5/8/13, duncan smith <buzzard@invalid.invalid> wrote:
> 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
>

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