Write this accumuator in a functional style

[Chris Angelico]

On Thu, Jul 13, 2017 at 6:15 PM, Paul Rubin <no.email at nospam.invalid> wrote:
> Chris Angelico <rosuav at gmail.com> writes:
>> some point it'll need to be rebalanced, which could at worst case
>> be O(n).
>
> No, you use a structure like an AVL tree or red-black tree, so it's
> within a constant factor of balanced after each insertion.  You rewrite
> O(log n) of the nodes, and juggle around a constant number of them at
> the top of the tree.  The Wikipedia articles about those data structures
> are pretty good.  C++ std::map is also implemented that way, I think.

Sure, that deals with the algorithmic complexity, but that would
entail a lot more rebalancing work, and if everything's immutable,
that means reconstructing the tree more often, right? 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.

ChrisA