No trees in the stdlib?

[Paul Rubin]

João Valverde <backup95 at netcabo.pt> writes:
> Rereading this I got what you meant by "wrapper with mutating slot".
> But that is (like I think you implied) functionally equivalent to a
> mutating data structure, with worse performance because of additional
> memory allocation and such. Is it faster to rebalance the tree with a
> persistent data structure?

If you're going to use a self-balancing tree you will have to do some
tree rotations even if the tree is mutable.  My guess is that it's
still O(log n) updates, but with a smaller proportionality constant.