En la implementación estándar de un contenedor asociativo map (por ejemplo, en C++ STL), se utiliza un árbol balanceado (generalmente un árbol rojo-negro). La complejidad temporal de eliminar un elemento de dicho map es O(log n), donde n es la cantidad de elementos en el contenedor.

Esto se debe a que para eliminar, primero hay que encontrar el elemento (tiempo logarítmico), y luego realizar la reestructuración del árbol, lo cual también ocurre en tiempo logarítmico.

Anterior Siguiente