Trees in Python?

[Roy Smith]

I need a mapping data structure in Python which acts like a tree. The
important attributes are:

1) I need to add, modify, and access random elements quickly.

2) Given a random key, I need to be able to find the next higher key
quickly. By higher, I mean in lexicographic key order, not insertion
order. Insertions will be in random order.

I'm not quite sure what I mean by "quickly", but certainly no slower
than log(n). Is there any way to do that without rolling my own
container class?

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.

 

[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