Red Black Tree implementation?

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	<drsalists@gmail.com>
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 <drsalists@gmail.com>
To	Python List <python-list@python.org>
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 <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.1225.1367449881.3114.python-list@python.org> (permalink)
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

Show key headers only | View raw

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

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!

Back to comp.lang.python | Previous | Next — 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