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: 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: <5181ca0e$0$13974$862e30e2@ngroups.net> <518850f8$0$8157$862e30e2@ngroups.net> <518ade0f$1$60230$862e30e2@ngroups.net> Date: Wed, 8 May 2013 18:40:06 -0700 Subject: Re: Red Black Tree implementation? From: Dan Stromberg To: Python List 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Newsgroups: comp.lang.python Message-ID: 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 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 wrote: > On 07/05/13 02:20, Dan Stromberg wrote: >> >> On Mon, May 6, 2013 at 5:55 PM, duncan smith > > 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 >