Wie ist die zeitliche Komplexität der Operation zum Entfernen eines Elements aus dem assoziativen Container map?

In der Standardimplementierung eines assoziativen Containers map (z.B. in C++ STL) wird ein balancierter Baum (meist ein Rot-Schwarz-Baum) verwendet. Die zeitliche Komplexität der Entfernung eines Elements aus einem solchen map beträgt O(log n), wobei n die Anzahl der Elemente im Container ist.

Dies liegt daran, dass zum Entfernen zuerst das Element gefunden werden muss (logarithmische Zeit), und dann die Umstrukturierung des Baumes erfolgt, was ebenfalls in logarithmischer Zeit geschieht.