SortedSet의 <T> 및 복잡성

Question

MSDN에 추가하면 다음 SortedSet(T).Add Method 상태 :

카운트 내부 어레이의 용량보다 작은 경우는, 이러한 방법은 O (1) 동작이다.

"어떻게 그렇게"설명해 주시겠습니까? 내 말은 새로운 값을 추가 할 때 값을 추가하기위한 정확한 위치 (다른 값과 비교)를 찾고 내부 구현은 O (log N) 삽입 복잡성을 가진 "Red-Black tree"처럼 보일 것입니다.

Answer 1

댓글이 잘못되었습니다. 네, 삽입을위한 붉은 검정색 나무, O (log (n))입니다. 리플 렉 토커 (Reflector)를 사용하여 보았을 때, 개인 AddIfNotPresent() 메소드는 일반적인 적 - 검은 노드 탐색을 사용하여 삽입 지점을 찾기위한 while() 루프를 포함합니다.

이 문서 버그는 이미 been submitted에 의해 you-know-who에 의해 있습니다.