No trees in the stdlib?

Aahz aahz at
Fri Jun 26 21:14:42 CEST 2009

In article <mailman.2170.1246042676.8015.python-list at>,
=?ISO-8859-1?Q?Jo=E3o_Valverde?=  <backup95 at> 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           <*>

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

More information about the Python-list mailing list