Kokia yra laiko sudėtingumas elemento pašalinimo operacijai iš asociatyvaus konteinerio map?

Standartinėje map (pavyzdžiui, C++ STL) įgyvendinime naudojama subalansuota medis (dažniausiai raudonai-juoda medis). Tokio map elemento ištrynimo laiko sudėtingumas yra O(log n), kur n yra elementų skaičius konteineryje.

Tai susiję su tuo, kad ištrynimui pirmiausia reikia rasti elementą (logaritminis laikas), o tada atlikti medžio pertvarkymą, kas taip pat vyksta logaritminiu laiku.