Red Black Tree implementation?

Date	2013-05-01 16:11 -0700
Subject	Red Black Tree implementation?
From	Dan Stromberg <drsalists@gmail.com>
Newsgroups	comp.lang.python
Message-ID	<mailman.1225.1367449881.3114.python-list@python.org> (permalink)

Show all headers | 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