The complexity of std::map::erase(iterator) is amortized O(1) (see here, for example). While the standard library does not dictate implementations, this de-facto means that the number of rebalancing operations needed for a red-black tree is amortized O(1). In fact, the Wikipedia entry on red-black trees seems to confirm this:
Restoring the red–black properties requires a small number (O(log n) or amortized O(1)) of color changes (which are very quick in practice) and no more than three tree rotations (two for insertion).
but seemingly without a link (and I couldn't find it in other places).
As the number of rotations is constant, the amortization is on the number of recolorings needed on the node-root path. While most nodes in a balanced tree are toward the bottom of the tree (and hence the average path is logarithmic), it apparently is amortized O(1), which is surprising and interesting. How can the amortized constant cost be proved?