Balanced trees (was: Re: Tuples and immutability)

[Dan Stromberg]

On Sat, Mar 8, 2014 at 12:34 AM, Marko Rauhamaa <marko at pacujo.net> wrote:
> 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.

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:
http://stromberg.dnsalias.org/~strombrg/python-tree-and-heap-comparison/2014-01/