No trees in the stdlib?

[Paul Rubin]

Lawrence D'Oliveiro <ldo at geek-central.gen.new_zealand> writes:
> >> Want sorted order?
> >>     sorted(tuple(the_set))
> >> What could be simpler?
> > 
> > Try putting that inside a loop with thousands of iterations and you'll
> > see what the problem is.
> 
> You could apply the same argument to anything. E.g. why create a tree 
> structure with a million elements? Try putting that inside a loop with 
> thousands of iterations and you'll see what the problem is.

The idea is you're going to insert or delete something in the tree
structure at each iteration, an O(log n) operation, making the whole
loop O(n log n).  If you sort a set (which is O(n log n)) inside the
loop then you end up with O(n**2 log n) which is impractical.  A
reason you might sort inside the loop might be to find the nearby
neighbors of the new element or traverse some elements in the middle.
This is trivial with a tree structure but messy with something like
sets.