Agregar a SortedSet y su complejidad

Question

MSDN establece lo siguiente Sortedset (t) .Add Método :

Si el recuento es menor que la capacidad de la matriz interna, este método es una operación O (1).

¿Alguien podría explicar "cómo es"? Quiero decir, al agregar un nuevo valor, necesitamos encontrar un lugar correcto para agregar un valor (compararlo con otros valores) y la implementación interna parece un "árbol rojo-negro" con complejidad de inserción O (log n).

Answer 1

El comentario simplemente está mal. Sí, es un árbol rojo-negro, o (log (n)) para insertos. Echar un vistazo con Reflector lleva esto, el método privado AddifNotPresent () contiene un bucle while () para encontrar el punto de inserción, utilizando el transversal del nodo rojo rojo normal.

Este error de doctor ya ha sido enviado por ti-conoce quién.