I need a red-black tree in Python and I was wondering if there was one
built in or if there's a good implementation out there. Something that,
lets face it, does whatever the C++ std::map<> allows you to do...
Are you really looking specifically for a red-black tree, or do you want a
container where iterators return values in sorted order? For instance, my
favorite sorted container is the skip-list:
* inherently thread safe even during container updates
* updates as fast as searches - significantly faster than red-black tree
* search as fast as trees on average - but probablistic (like hashtable)
* sequential access as fast as a linked list
* Uses 33% less memory than binary trees (like red-black tree)
* in general, performs like a hashtable, but sorted
Java example:
http://bmsi.com/java/SkipList.java
In Python, the performance of a pure Python container will be
disappointing unless it leverages a native container. For many
applications, you can use a dict and sort when iterating (using heapq to
amortize the sorting).
If I ever get the time, I would seriously consider trying to modify Python
to replace the built-in dict with a skip-list algorithm and compare the
performance. Failing that, an extension module implementing a sorted
container of some description would be useful.