complejidad de set :: inserción

Question

He leído que la operación de inserción en un conjunto solo toma el tiempo de registro (n). ¿Cómo es eso posible?

Para insertar, primero tenemos que encontrar la ubicación en la matriz ordenada donde debe estar el nuevo elemento. Usando la búsqueda binaria toma log (n). Luego, para insertar en esa ubicación, todos los elementos que lo suceden deben desplazarse un lugar hacia la derecha. Tarda otro n tiempo.

Mi duda se basa en mi comprensión de que el conjunto se implementa como una matriz y los elementos se almacenan en orden ordenado. Por favor corrígeme si mi entendimiento es incorrecto.

Answer 1

std::set se implementa comúnmente como un árbol de búsqueda binario rojo-negro. La inserción en esta estructura de datos tiene el peor caso de complejidad O (log (n)), ya que el árbol se mantiene equilibrado.