Ajouter à SortedSet et sa complexité

Question

MSDN indique ce qui suit SortedSet (T) .Add procédé :

  

Si le nombre est inférieur à la capacité de la matrice interne, cette méthode est une opération O (1).

Quelqu'un pourrait-il expliquer s'il vous plaît « comment si »? Je veux dire quand l'ajout de nouvelles valeur que nous devons trouver un bon endroit pour ajouter une valeur (comparer avec une autre valeur) et la mise en œuvre interne ressemble à un « arbre rouge-noir » avec O (log N) complexité d'insertion.

Answer 1

Le commentaire est tout simplement faux. Oui, il est un arbre rouge-noir, O (log (n)) pour les insertions. Si l'on regarde avec réflecteur le confirme, le procédé AddIfNotPresent privé () contient une boucle while () pour trouver le point d'insertion, en utilisant noeud rouge-noir normale traversal.

Ce bogue doc a déjà été soumis par vous-savez-qui.