c# - Agregar a SortedSet<T> y su complejidad

time-complexity

Question

MSDN indica el siguiente método SortedSet (T) .Add :

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

¿Podría alguien explicar "cómo"? Me refiero a que al agregar un nuevo valor necesitamos encontrar un lugar correcto para agregar un valor (comparándolo con otros valores) y la implementación interna parece un "árbol rojo-negro" con complejidad de inserción O (registro N).

Answer 1

El comentario es simplemente incorrecto. Sí, es un árbol rojo-negro, O (log (n)) para inserciones. Mirar con Reflector lo confirma, el método privado AddIfNotPresent () contiene un bucle while () para encontrar el punto de inserción, usando el recorrido normal del nodo rojo-negro.

Este error de documentación ya ha sido enviado por you-know-who.