Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.mixmin.net!newsreader4.netcologne.de!news.netcologne.de!xlned.com!feeder7.xlned.com!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.020 X-Spam-Evidence: '*H*': 0.96; '*S*': 0.00; 'programmer': 0.03; 'tree': 0.05; 'elements.': 0.07; 'trees': 0.09; 'runs': 0.10; 'python': 0.11; 'believes': 0.16; 'dictionary,': 0.16; 'to:name:python list': 0.16; 'so.': 0.16; '2.x': 0.24; 'passes': 0.24; 'looks': 0.24; "i've": 0.25; 'gets': 0.27; 'message-id:@mail.gmail.com': 0.30; "i'm": 0.30; 'getting': 0.31; 'comparison': 0.31; 'operators': 0.31; 'subject:skip:i 10': 0.31; 'thanks!': 0.32; "i'd": 0.34; 'something': 0.35; 'but': 0.35; 'received:google.com': 0.35; 'google': 0.35; 'subject:?': 0.36; 'url:org': 0.36; 'should': 0.36; 'half': 0.37; 'to:addr:python- list': 0.38; 'short': 0.38; 'to:addr:python.org': 0.39; '8bit%:6': 0.40; 'black': 0.61; 'high': 0.63; 'skip:n 10': 0.64; 'million': 0.74; 'opensource': 0.84; 'subject:Red': 0.84; 'wanted,': 0.84 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:x-received:date:message-id:subject:from:to :content-type; bh=uSCpIYUfBecZpTrc1bF9oyfHoVp2+8gzMl+sPbtmXNY=; b=gdqq9IEXZoA3So8702jNKLYGMGAcwGbwP5xx96n1rXf9+IaKzsxHQIUPTf86h41WwQ fjwe7xnLk677+Ht5vrEqc7ZP9ouP9htYbca3I7hmP7wBMh7M6kA0GqAOQtUWntnvYjiT fp7U5lvyA9O791666z6ODsce/ebHvd3Mt8eLNZajEj8y78p1ZKT+XV62s/W15O1lmWcb v7kxV5U878L/8XuyULtO0Ns9tRf4bgVf8E5h/9bN+7ny2grAQeR0531epwRwBRkChP5n jVyqED0LLjN4aTZDgMnpdKjsmbzzCf8/rePSzHmuXk/WGoQAEOMWQfY9mvo+6d/6n8Z3 KaEg== MIME-Version: 1.0 X-Received: by 10.224.23.10 with SMTP id p10mr5682513qab.39.1367449873002; Wed, 01 May 2013 16:11:13 -0700 (PDT) Date: Wed, 1 May 2013 16:11:12 -0700 Subject: Red Black Tree implementation? From: Dan Stromberg To: Python List Content-Type: multipart/alternative; boundary=001a11c23262edb5a404dbb03b19 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: 48 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1367449881 news.xs4all.nl 15906 [2001:888:2000:d::a6]:34923 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:44606 --001a11c23262edb5a404dbb03b19 Content-Type: text/plain; charset=ISO-8859-1 What's the best Red Black Tree implementation for Python with an opensource license? I started out looking at http://newcenturycomputers.net/projects/rbtree.htmlbecause it was pretty high in Google and had the operators I wanted, but it gets very slow at about half a million elements. I've been discussing this with a C programmer who believes that Red Black Trees should perform very similarly to an AVL tree, but that's not at all what I'm getting with the newcenturycomputers implementation. I'd prefer something that looks like a dictionary, runs on 2.x and 3.x, and passes pylint, but if that's not yet available I might make it so. This is part of a comparison of Python tree types I did a while back... I've been thinking that I've given Red Black Trees short shrift by using a poor implementation. The comparison so far is at http://stromberg.dnsalias.org/~strombrg/python-tree-and-heap-comparison/ Thanks! --001a11c23262edb5a404dbb03b19 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable

What's the best Red Blac= k Tree implementation for Python with an opensource license?

I start= ed out looking at http://newcenturycomputers.net/projects/rbtree.html because it w= as pretty high in Google and had the operators I wanted, but it gets very s= low at about half a million elements.=A0 I've been discussing this with= a C programmer who believes that Red Black Trees should perform very simil= arly to an AVL tree, but that's not at all what I'm getting with th= e newcenturycomputers implementation.

I'd prefer something that looks like a dictionary, runs on 2.= x and 3.x, and passes pylint, but if that's not yet available I might m= ake it so.

This is part of a comparison of Python tree types I= did a while back...=A0 I've been thinking that I've given Red Blac= k Trees short shrift by using a poor implementation.=A0 The comparison so f= ar is at http://stromberg.dnsalias.org/~strombrg/python-tree-and-= heap-comparison/

Thanks!


--001a11c23262edb5a404dbb03b19--