No trees in the stdlib?

[Aahz]

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.

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
-- 
Aahz (aahz at pythoncraft.com)           <*>         http://www.pythoncraft.com/

"as long as we like the same operating system, things are cool." --piranha