Kāda ir laika sarežģītība elementa dzēšanas operācijai no asociatīvā konteinerā map?

Standarta map (piemēram, C++ STL) realizācijā tiek izmantots līdzsvarots koks (parasti sarkans-melns koks). Šī map elementa dzēšanas laika sarežģītība ir O(log n), kur n ir elementu skaits konteinerā.

Tas ir tāpēc, ka, lai dzēstu, vispirms ir jāatrod elements (logaritmisks laiks), un pēc tam jāpārkārto koks, kas arī notiek logaritmiskajā laikā.