No trees in the stdlib?

[João Valverde]

João Valverde wrote:
> Paul Rubin wrote:
>> João Valverde <backup95 at netcabo.pt> writes:
>>  
>>> Could you clarify what you mean by immutable? As in... not mutable? As
>>> in without supporting insertions and deletions?      
>>
>> Correct. 
>>  
>>> That's has the same performance as using binary search on a sorted
>>> list.  What's the point of using a tree for that?
>>>     
>>
>> The idea is you can accomplish the equivalent of insertion or deletion
>> by allocating a new root, along with the path down to the place you
>> want to insert, i.e. O(log n) operations.  So instead of mutating an
>> existing tree, you create a new tree that shares most of its structure
>> with the old tree, and switch over to using the new tree.  This
>> trivially lets you maintain snapshots of old versions of the tree,
>> implement an "undo" operation, have a background thread do a complex
>> operation on a snapshot while the foreground thread does any number of
>> update-and-replace operations, etc.
>>
>>
>>   
> 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", undo is kind of redundant and 
> multithreading... don't see a compelling use that would justify it. 
> Also the interface is a mapping so it'd be rather nice to emulate dict's.
>
> Have you considered how the syntax would work in Python by the way? This:
>
> new_tree = old_tree.insert(object)
>

Heh, that's a poor example for a mapping. But:

bst[key] = object

is even dicier for immutable structures no?