In article <mailman.2170.1246042676.8015.python-l...@python.org>, =?ISO-8859-1?Q?Jo=E3o_Valverde?= <backu...@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 (a...@pythoncraft.com) <*> http://www.pythoncraft.com/ "as long as we like the same operating system, things are cool." --piranha -- http://mail.python.org/mailman/listinfo/python-list
