Qual é a complexidade temporal da operação de remoção de um elemento do contêiner associativo map?

Na implementação padrão de um contêiner associativo map (por exemplo, na STL do C++), é utilizado uma árvore balanceada (geralmente uma árvore vermelho-preto). A complexidade temporal da operação de remoção de um elemento desse map é O(log n), onde n é o número de elementos no contêiner.

Isso ocorre porque, para remover, primeiro é necessário encontrar o elemento (tempo logarítmico), e depois realizar a reestruturação da árvore, o que também acontece em tempo logarítmico.