No trees in the stdlib?

[João Valverde]

João Valverde wrote:
> Paul Rubin wrote:
>> João Valverde <backup95 at netcabo.pt> writes:
>>  
>>> Interesting, thanks. The concept is not difficult to understand but
>>> I'm not sure it would be preferable. A copy operation should have the
>>> same cost as a "snapshot",     
>>
>> You mean a deep-copy?  That is unnecessarily expensive; with a
>> functional structure you can snapshot (or copy) by copying a single
>> pointer.
>>
>>   
>
> Shallow copy...
>
>>> undo is kind of redundant and multithreading... don't see a
>>> compelling use that would justify it.     
>>
>> Here is one:
>>  http://groups.google.com/group/comp.lang.python/msg/1fbe66701e4bc65b
>>
>>   
>
> I just skimmed that but if someone really needs multithreading for 
> such intensive processing without wanting a database, fair enough I 
> guess.
>
>>> Have you considered how the syntax would work in Python by the way? 
>>> This:
>>> new_tree = old_tree.insert(object)
>>> Just looks wrong.     
>>
>> It looks fine to me.  Obviously you could support a wrapper with
>> a mutating slot that holds a pointer to the tree.
>>   
> I didn't get the last part, sorry. But I think you'd have a lot of 
> users annoyed that the interface is similar to a list yet their 
> objects mysteriously disappear. To me, tree.insert() implies 
> mutability but I defer that to others like yourself with more 
> experience in Python than me.
>

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?