Write this accumuator in a functional style

[Marko Rauhamaa]

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