[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

- Prev by Date:
**Write this accumuator in a functional style** - Next by Date:
**Write this accumuator in a functional style** - Previous by thread:
**Write this accumuator in a functional style** - Next by thread:
**Write this accumuator in a functional style** - Index(es):