Qual è la complessità temporale dell'operazione di rimozione di un elemento dal contenitore associativo map?

Nell'implementazione standard di un contenitore associativo map (ad esempio, nella STL di C++) viene utilizzato un albero bilanciato (solitamente un albero rosso-nero). La complessità temporale dell'eliminazione di un elemento da tale map è O(log n), dove n è il numero di elementi nel contenitore.

Ciò è dovuto al fatto che per eliminare, prima bisogna trovare l'elemento (tempo logaritmico), e poi eseguire la ristrutturazione dell'albero, che avviene anch'essa in tempo logaritmico.