Balanced trees (was: Re: Tuples and immutability)

[Marko Rauhamaa]

Ian Kelly <ian.g.kelly at gmail.com>:

> 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.

In fact, since asyncio has timers but Python doesn't have balanced
trees, I'm led to wonder how good the asyncio implementation can be.

Note that Java "batteries" include TreeMap.


Marko