Amortized analysis of red-black trees
You may need to look at this report:
https://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf

Each individual operation takes $O(\log n)$ but when you apply amortized analysis to a sequence of operations, you get something interesting. 

Directly from this report:
"However, amortized analysis can be used to show that any sequence of $m$ insert and delete operations causes $O(m)$ structural modifications in the worst case (Cormen et al. p.428). It can similarly be shown that the total time for  $m$ consecutive insertions in a tree of $n$ nodes is $O(n + m)$ (Tarjan 1985)."