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

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.

- Prev by Date:
**No pip3.5 bin after install python3.5.1 from source code** - 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):