No trees in the stdlib?
Tue Jun 30 04:40:56 CEST 2009
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.
More information about the Python-list