What is the time complexity of removing an element from an associative container map?

In the standard implementation of an associative container map (for example, in C++ STL), a balanced tree (usually a red-black tree) is used. The time complexity of deleting an element from such a map is O(log n), where n is the number of elements in the container.

This is because, to delete an element, you first need to find the element (logarithmic time), and then perform a tree restructuring, which also takes logarithmic time.