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.