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

  • Thread starter Just Another Victim of the Ambient Morality
  • Start date
J

Just Another Victim of the Ambient Morality

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...
Thank you...
 
G

Gabriel Genellina

At Thursday 14/12/2006 22:20, Just Another Victim of the Ambient
Morality said:
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...

There are several implementations, try google...


--
Gabriel Genellina
Softlab SRL

__________________________________________________
Correo Yahoo!
Espacio para todos tus mensajes, antivirus y antispam ¡gratis!
¡Abrí tu cuenta ya! - http://correo.yahoo.com.ar
 
J

Jorgen Grahn

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

Nitpick: std::map is implemented using RB-trees, but it isn't one,
interface-wise.

/Jorgen
 
S

Stuart D. Gathman

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.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top