No trees in the stdlib?

[João Valverde]

Aahz wrote:
> In article <mailman.2170.1246042676.8015.python-list at python.org>,
> =?ISO-8859-1?Q?Jo=E3o_Valverde?=  <backup95 at netcabo.pt> wrote:
>   
>> 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.
>>     
>
> Why AVL/RBT instead of B*?  It's not that simple....  Another problem is
> that unless the tree is coded in C, the constant factors are going to
> swamp algorithmic complexity for many use cases -- that in turn makes it
> more difficult to deploy a PyPI library for real-world testing.
>   

I wouldn't consider anything other than C for such a module on 
efficiency alone, unless it was a prototype of course. But I have little 
knowledge about the Python C API.

About B* trees, again not an expert but I don't see how the added 
complexity brings any noticeable advantage to implement the associative 
array data structure I mentioned. Simple is better.

> Anyway, I'm *not* trying to discourage you, just explain some of the
> roadblocks to acceptance that likely are why it hasn't already happened.
>
> If you're serious about pushing this through, you have two options:
>
> * Write the code and corresponding PEP yourself (which leads to the
> second option, anyway)
>
> * Lobby on the python-ideas mailing list
>   

Currently I don't have a strong need for this. I just believe it would 
be a benefit to a language I like a lot.  Lobbying isn't my thing. I'd 
rather write code, but neither am I the most qualified person for the 
job. It would certainly be interesting and fun and challenging in a good 
way and a great way to learn some new stuff. But I would definitely need 
mentoring or asking some silly questions on the mailing list. Maybe I'll 
seriously consider it some other time.