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 <[EMAIL PROTECTED]> 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. -- http://mail.python.org/mailman/listinfo/python-list
