On Sat, Mar 8, 2014 at 12:34 AM, Marko Rauhamaa <ma...@pacujo.net> wrote: > Ian Kelly <ian.g.ke...@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/ -- https://mail.python.org/mailman/listinfo/python-list
