red-black tree data structure

[Dan Stromberg]

Bringing this back  to Python a bit:
http://newcenturycomputers.net/projects/rbtree.html
http://pypi.python.org/pypi/bintrees/0.3.0
http://pypi.python.org/pypi/treap/0.995

Red-Black trees are supposed to be slower than treaps on average, but
they're also supposed to have a lower standard deviation in execution times
compared to treaps.  So for batch processing, the treap might be better,
while for use in an interactive application, red-black trees might be
better - because for batch processing no one cares about a little
jerkiness, while in an interactive app it might annoy users.

Apparently there was an effort,  briefly, to get a red-black tree into
Python's collections module, but it was rejected.

Treaps are supposed to have a simpler implementation than red-black trees.

I'm amused by the "red and black pens" thing.  ^_^

On Wed, Apr 11, 2012 at 10:14 AM, Jabba Laci <jabba.laci at gmail.com> wrote:

> Hi,
>
> It's not really a Python-related question, sorry for that. Does anyone
> know why red-black trees got these colors in their names? Why not
> blue-orange for instance? I'm just curious.
>
> Thanks,
>
> Laszlo
> --
> http://mail.python.org/mailman/listinfo/python-list
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20120411/22e94ad4/attachment-0001.html>