I'm looking for a pythonic red-black tree...

[Stuart D. Gathman]

On Fri, 15 Dec 2006 01:20:34 +0000, Just Another Victim of the Ambient
Morality wrote:

>     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.

-- 
	      Stuart D. Gathman <stuart at bmsi.com>
Business Management Systems Inc.  Phone: 703 591-0911 Fax: 703 591-6154
"Confutatis maledictis, flamis acribus addictis" - background song for
a Microsoft sponsored "Where do you want to go from here?" commercial.