SortedDictionary

SortedDictionary<int, string> sortedDict = new SortedDictionary<int, string>();

https://github.com/dotnet/runtime/blob/main/src/libraries/System.Collections/src/System/Collections/Generic/SortedDictionary.cs

• System.Collections.Generic
• 균형 이진 트리 기반 (BST)
  • 해시 테이블 사용하지 않음
  • capacity 설정 없음
• Red-Black Tree
  • 모든 노드는 Red or Black
    • Red : 임시 노드 (균형 조정 가능)
    • Black 경로 균형을 유지하는 기준 노드
  • 새로 삽입되는 노드는 항상 Red
  • Root는 항상 Black
  • Red 노드는 연속될 수 없다
    • Rotation + Recolor
  • 어떤 경로든 Black 노드의 갯수는 같다
• Key 기준 자동 정렬
  • 오름차순
  • Left < Parent < Right
• Node 구조
  • TKey Key
  • TValue Value
  • Node Left : 이 노드보다 Key가 작은 노드
  • Node Right : 이 노드보다 Key가 큰 노드
  • bool IsRed : 트리 균형 표식
• 시간 복잡도
  • 탐색 : O(log N)
  • 삽입, 삭제 : O(log N)
    • new Node() ⇒ GC
    • 메모리 파편화 ⇒ Cache Hit Rate 낮음