No trees in the stdlib?

[João Valverde]

João Valverde wrote:
> João Valverde wrote:
>> Aahz wrote:
>>> In article <mailman.2139.1245994218.8015.python-list at python.org>,
>>> Tom Reed  <tomreed05 at gmail.com> wrote:
>>>  
>>>> Why no trees in the standard library, if not as a built in? I 
>>>> searched the archive but couldn't find a relevant discussion. Seems 
>>>> like a glaring omission considering the batteries included 
>>>> philosophy, particularly balanced binary search trees. No interest, 
>>>> no good implementations, something other reason? Seems like a good 
>>>> fit for the collections module. Can anyone shed some light?
>>>>     
>>>
>>> What do you want such a tree for?  Why are dicts and the bisect module
>>> inadequate?  Note that there are plenty of different tree 
>>> implementations
>>> available from either PyPI or the Cookbook.
>>>   
>> A hash table is very different to a BST.  They are both useful. The 
>> bisect module I'm not familiar with, I'll have to look into that, 
>> thanks.
>>
>> I have found pyavl on the web, it does the job ok, but there no 
>> implementations for python3 that I know of.
>>
>> Simple example usage case: Insert string into data structure in 
>> sorted order if it doesn't exist, else retrieve it.
>>
> After browsing the bisect module I don't think it is the complete 
> answer. Please correct me if I'm mistaken but...
>
> Ignoring for a moment that subjectively I feel this is not very 
> pythonic for my use case, if I get back the insertion position, 
> doesn't that mean I have to go over on average N/2 items on a linked 
> list to insert the item in position? Maybe less for sophisticated 
> implementations but still O(n)? That doesn't compare favorably to the 
> cost of (possibly) having to rebalance a tree on insertion.
I was indeed corrected on this shameful blunder, but in my defense array 
based lists are implementation dependent and the case for trees can be 
made on deletion.