sortedset とその複雑さに追加します

Question

MSDNは以下を述べています sortedset（t）.addメソッド :

カウントが内部配列の容量よりも少ない場合、この方法はO（1）操作です。

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

Answer 1

コメントは単に間違っています。はい、それは挿入用の赤黒の木、o（log（n））です。リフレクターで見てみると、プライベートaddifnotpresent（）メソッドには、通常の赤ブラックノードトラバーサルを使用して、挿入点を見つけるためにhoth（）ループが含まれています。

このドキュメントバグにはすでにあります 提出されました あなたが知っていることによって。