No trees in the stdlib?

[João Valverde]

Paul Rubin wrote:
> aahz at pythoncraft.com (Aahz) writes:
>   
>> (In particular, WRT the bisect module, although insertion and deletion
>> are O(N), the constant factor for doing a simple memory move at C speed
>> swamps bytecode until N gets very large -- and we already have
>> collections.deque() for some other common use cases.)
>>     
>
> Again, at least in my case, I'd hope for an immutable structure.
>
>   
Could you clarify what you mean by immutable? As in... not mutable? As 
in without supporting insertions and deletions? That's has the same 
performance as using binary search on a sorted list. What's the point of 
using a tree for that?