Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #44610

Re: Red Black Tree implementation?

Show all headers | View raw

On 02/05/13 00:11, Dan Stromberg wrote:
>
> What's the best Red Black Tree implementation for Python with an
> opensource license?
>
> I started out looking at
> http://newcenturycomputers.net/projects/rbtree.html because 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!
>
>


I have an implementation that you can try out. It's not based on any 
other implementation, so my bugs will be independent of any bugs in the 
code you're currently using. It looks more like a set - add, remove, 
discard. Not tried on Python 3 or run through pylint. I just tried 
adding a million items to a tree, and it takes about 25% longer to add 
items at the end compared to those at the beginning. Timing removals 
uncovered a bug. So if you want the code I'll fix the bug and send it 
(to your gmail e-mail address?). Cheers.

Duncan

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