Write this accumuator in a functional style
Marko Rauhamaa
marko at pacujo.net
Thu Jul 13 06:25:58 EDT 2017
Paul Rubin <no.email at nospam.invalid>:
> Chris Angelico <rosuav at 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
More information about the Python-list
mailing list