Какова временная сложность операции удаления элемента из ассоциативного контейнера map?

В стандартной реализации ассоциативного контейнера map (например, в C++ STL) используется сбалансированное дерево (обычно красно-чёрное дерево). Временная сложность операции удаления элемента из такого map составляет O(log n), где n — количество элементов в контейнере.

Это связано с тем, что для удаления нужно сначала найти элемент (логарифмическое время), а затем выполнить перестройку дерева, что также происходит за логарифмическое время.