No trees in the stdlib?

Chris Rebert clp2 at rebertia.com
Fri Jun 26 08:23:41 CEST 2009


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.
>>
>
> 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.

That's pretty much the bisect module in a nutshell. It manipulates a
sorted list using binary search.

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



More information about the Python-list mailing list