Paul Rubin no.email at nospam.invalid
Thu Jul 13 04:15:17 EDT 2017

• Previous message (by thread): Write this accumuator in a functional style
• Next message (by thread): Write this accumuator in a functional style
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

---

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.

---

• Previous message (by thread): Write this accumuator in a functional style
• Next message (by thread): Write this accumuator in a functional style
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

---

More information about the Python-list mailing list