No trees in the stdlib?

[Miles Kaufmann]

On Jun 26, 2009, at 2:23 AM, Chris Rebert wrote:

> On Thu, Jun 25, 2009 at 10:55 PM, João Valverde<backup95 at netcabo.pt>  
> 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.
>>>
>>
>> Simple example usage case: Insert string into data structure in  
>> sorted order
>> if it doesn't exist, else retrieve it.
>
> That's pretty much the bisect module in a nutshell. It manipulates a
> sorted list using binary search.

With O(n) insertions and removals, though.  A decent self-balancing  
binary tree will generally do those in O(log n).

-Miles