Quelle est la complexité temporelle de l'opération de suppression d'un élément du conteneur associatif map?

Dans l'implémentation standard d'un conteneur associatif map (par exemple, dans la STL C++), un arbre équilibré (généralement un arbre rouge-noir) est utilisé. La complexité temporelle de la suppression d'un élément de ce map est O(log n), où n est le nombre d'éléments dans le conteneur.

Cela est dû au fait que pour supprimer, il faut d'abord trouver l'élément (temps logarithmique), puis effectuer la restructuration de l'arbre, ce qui se produit également en temps logarithmique.