No trees in the stdlib?

[greg]

João Valverde wrote:

> What's lacking is an associative array that preserves ordering, doesn't 
> require a hash function and has fast insertions and deletions in 
> O(log(n)).

Careful here -- you can't get away from the need for
hashability just by using a tree. Even if you don't
need to actually hash the values, it's still important
that the criterion for ordering between objects doesn't
change while they're in the tree, otherwise they'll
be in the wrong place and won't be found by subsequent
lookups.

 > I'm genuinely surprised to know
> there are no data structures that efficiently support such a common need 
> in Python.

Is it really all that common? If it truly were common,
there probably *would* be something for it in the
stdlib by now.

What sort of things are you doing that you want such
a structure for? Maybe we can suggest a way of using
the existing data structures to achieve the same
goal.

-- 
Greg