Wat is de tijdcomplexiteit van de bewerking om een element uit de associatieve container map te verwijderen?

In de standaardimplementatie van een associatieve container map (bijvoorbeeld in C++ STL) wordt een gebalanceerde boom gebruikt (meestal een rood-zwart boom). De tijdscomplexiteit van het verwijderen van een element uit zo'n map is O(log n), waarbij n het aantal elementen in de container is.

Dit komt doordat je eerst het element moet vinden (logaritmische tijd), en vervolgens de boom moet herstructureren, wat ook in logaritmische tijd gebeurt.