No trees in the stdlib?

João Valverde backup95 at netcabo.pt
Fri Jun 26 02:21:05 EDT 2009


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.
The main problem with pyavl by the way is that it doesn't seem to be 
subclassable (?). Besides some interface glitches, like returning None 
on delete if I recall correctly.

There's also rbtree, which I didn't try. And I think that's it. On the 
whole not a lot of choice and not as practical for such a common data 
structure.



More information about the Python-list mailing list