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

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

Това се дължи на факта, че за изтриване първо трябва да намерите елемента (логаритмично време), а след това да извършите преустройството на дървото, което също става за логаритмично време.