Red Black Tree implementation?

[Christian Heimes]

Am 02.05.2013 01:11, schrieb Dan Stromberg:
> 
> 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
> <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.

No wonder it's getting slow and doesn't stand a change against Python's
dict implementation. The rbtree implementation from
newcenturycomputers.net is written entirely in Python. It's good code
for academic research in order to study the properties of a rbtree.

If you need something production ready then you have to use an
implemetation with an optimized backend like a C code, PyPy or Cython.

Christian