Trees in Python?

[Xavier Combelle]

> Every once in a while, I'm envious of the C++ guys with their STL.  The 
> I make my saving throw vs insanity and the feeling passes.
In my point of view, I am envious of man who are programming python
as a job.

By looking for red-black python in google. I found an implementation
of red-black trees.
http://newcenturycomputers.net/projects/rbtree.html
It seems that should fit your purpose.
 From license point of view, it seems to be free.
"Source code, when part of a software project, may be used freely 
without reference to the author."

Xavier