João Valverde <backu...@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. -- http://mail.python.org/mailman/listinfo/python-list
