No trees in the stdlib?

[Chris Rebert]

On Fri, Jun 26, 2009 at 12:09 AM, João Valverde<backup95 at netcabo.pt> 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

Linked list?! Python lists are *array-based*.
<"You must be new here" joke redacted>

Cheers,
Chris
-- 
http://blog.rebertia.com