Balanced trees

Mark Lawrence breamoreboy at
Sat Mar 8 21:37:58 CET 2014

On 08/03/2014 19:58, Dan Stromberg wrote:
> On Sat, Mar 8, 2014 at 12:34 AM, Marko Rauhamaa <marko at> wrote:
>> Ian Kelly <ian.g.kelly at>:
>>> I already mentioned this earlier in the thread, but a balanced binary
>>> tree might implement += as node insertion and then return a different
>>> object if the balancing causes the root node to change.
>> True.
>> Speaking of which, are there plans to add a balanced tree to the
>> "batteries" of Python? Timers, cache aging and the like need it. I'm
>> using my own AVL tree implementation, but I'm wondering why Python
>> still doesn't have one.
> I think it'd probably be a good idea to add one or more balanced
> binary trees to the standard library.  But I suspect it's been tried
> before, and didn't happen.  It might be good to add an _un_balanced
> tree too, since they do quite well with random keys.
> Here's a performance comparison I did of a bunch of tree types in Python:

I've found this link useful

I also don't want all sorts of data structures added to the Python 
library.  I believe that there are advantages to leaving specialist data 
structures on pypi or other sites, plus it means Python in a Nutshell 
can still fit in your pocket and not a 40 ton articulated lorry, unlike 
the Java equivalent.

My fellow Pythonistas, ask not what our language can do for you, ask 
what you can do for our language.

Mark Lawrence

This email is free from viruses and malware because avast! Antivirus protection is active.

More information about the Python-list mailing list