¿Por qué la complejidad del contenedor de mapas C++ STL O (log (n))?

Question

Para contenedores C++ STL como vector y list, la complejidad de encontrar elementos e insertarlos o eliminarlos se explica por sí misma. Sin embargo, para el contenedor map, aunque sé por mi lectura que la complejidad/rendimiento de acceso e inserción es O (log (n)), no puedo resolver por qué. Claramente no entiendo los mapas tanto como lo necesito, por lo que sería muy apreciado algún esclarecimiento sobre este tema.

Answer 1

Los elementos de un mapa o conjunto están contenidos en una estructura de árbol; cada vez que examina un nodo del árbol, determina si el elemento que está tratando de encontrar/insertar es menor o mayor que el nodo. El número de veces que necesita hacer esto (para un árbol correctamente equilibrado) es log2 (N) porque cada comparación arroja la mitad de las posibilidades.

Answer 2

Como slavik262 puntos, los mapas se implementan generalmente con árboles rojo-negro, que son auto-equilibrados. Comprueba la complejidad de un árbol rojo-negro, por ejemplo, en el wikipedia No conozco ninguna implementación de un mapa con un árbol binario; si Mark Ransom conoce uno, me gustaría saber cuál.