c# - SortedSetに追加とその複雑さ

Question

MSDNは、次のSortedSet（T）.Addメソッドを示しています。

Countが内部配列の容量よりも小さい場合、このメソッドはO（1）操作です。

誰かが「どうやって」説明してもらえますか？つまり、新しい値を追加するときは、値を追加する正しい場所を見つける必要があり（別の値と比較して）、内部実装はO（log N）挿入の複雑さを持つ「赤黒木」のように見えます。

Answer 1

コメントは単に間違っています。はい、挿入用の赤黒木 O(log(n)) です。Reflector を見てみると、これは明らかです。プライベートな AddIfNotPresent() メソッドには、通常の赤黒ノード トラバーサルを使用して、挿入ポイントを見つけるための while() ループが含まれています。

このドキュメント バグは、既にご存知の方から提出されています。