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 <st****@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.
