Која је временска сложеност операције брисања елемента из асоцијативног контејнера map?

U standardnoj implementaciji asocijativnog kontejnera map (na primer, u C++ STL) koristi se uravnoteženo stablo (obično crveno-črno stablo). Vremenska složenost operacije brisanja elementa iz takvog map je O(log n), gde je n broj elemenata u kontejneru.

To je zbog toga što je za brisanje prvo potrebno pronaći element (logaritamsko vreme), a zatim izvršiti preuređenje stabla, što se takođe dešava u logaritamskom vremenu.