Aggiungere al SortedSet e la sua complessità

Question

MSDN afferma quanto segue SortedSet (T) .Add metodo :

  

Se Count è inferiore alla capacità della matrice interna, questo metodo è un O (1) operazione.

Qualcuno potrebbe spiegare "come così"? Voglio dire, quando si aggiunge nuovo valore abbiamo bisogno di trovare un posto giusto per aggiungere un valore (a confronto con un altro valori) e implementazione interna si presenta come un "albero Rosso-Nero" con O (log N) complessità di inserimento.

Answer 1

Il commento è semplicemente sbagliato. Sì, si tratta di un albero rosso-nero, O (log (n)) per gli inserti. Dando uno sguardo con riflettore lo conferma, il metodo AddIfNotPresent privato () contiene un ciclo while () per trovare il punto di inserimento, con una normale nodo trasversale rosso-nero.

Questo bug doc ha già stato presentata di tu-sai-chi.