Paul Rubin <no.email@nospam.invalid>: > Chris Angelico <ros...@gmail.com> writes: >> Maybe I'm completely on the wrong track here, but the last time I >> implemented a self-balancing tree, it usually involved a fair amount >> of mutation. > > AVL trees are fairly simple to implement without mutation. Red-black > trees are traditionally implemented with mutation, inserting by making > nodes mis-colored, then going and re-coloring them. But they can be > done mutation-free as well.
Simple, yes, but is the worst case insertion/deletion time still within O(log n)? Marko -- https://mail.python.org/mailman/listinfo/python-list
