No trees in the stdlib?

João Valverde backup95 at netcabo.pt
Fri Jun 26 14:57:42 EDT 2009


Aahz wrote:
> In article <006078f0$0$9721$c3e8da3 at news.astraweb.com>,
> Steven D'Aprano  <steve at REMOVE-THIS-cybersource.com.au> wrote:
>   
>> Hash tables (dicts) are useful for many of the same things that trees are 
>> useful for, but they are different data structures with different 
>> strengths and weaknesses, and different uses. To argue that we don't need 
>> trees because we have dicts makes as much sense as arguing that we don't 
>> need dicts because we have lists.
>>     
>
> The problem is that trees are like standards: there are so many to choose
> from.  Each has its own tradeoffs, and because Python dicts and lists can
> substitute for many of the traditionals uses of trees, the tradeoffs are
> less clear.  I think nobody would object to adding trees to the standard
> library, but it will certainly require a clear PEP, preferably with a
> pointer to an existing PyPI library that has acquired real-world use.
>
>
>   
Wish I had asked this before this year's GSoC started.

What's lacking is an associative array that preserves ordering, doesn't 
require a hash function and has fast insertions and deletions in 
O(log(n)). The particular algorithm to achieve this is a secondary 
issue. It's a BST for sure, AVL vs RBT vs something else. It's my fault 
for having opened the topic with simply "trees" instead, it would have 
avoided this vagueness problem, but I'm genuinely surprised to know 
there are no data structures that efficiently support such a common need 
in Python. And I really enjoy the using this language.



More information about the Python-list mailing list