C++ 표준 라이브러리의 std::map 은 자주 쓰이는 연관 컨테이너(associative container) 중 하나이다

기본 개념

• std::map 은 key-value 쌍을 저장하는 컨테이너.
• 각 원소는 (key, value) 형태로 저장되고, key 를 기준으로 자동 정렬.
• 내부적으로는 레드-블랙 트리(균형 이진 탐색 트리)를 사용합니다.
• 즉, std::map 은 자동 정렬 + 빠른 탐색을 제공하는 자료구조

---

주요 특징

정렬된 상태 유지

• 원소들이 항상 key 순서대로 정렬
• 정렬 기준은 기본적으로 < 연산자지만, 사용자 정의 비교 함수(std::less 등)를 넣을 수도 있음

중복 키 허용 X

• 같은 키를 두 번 넣을 수 없음
• 중복 키를 허용하려면 std::multimap 을 사용

시간 복잡도 보장

• 탐색: O(log n)
• 삽입: O(log n)
• 삭제: O(log n)
• 내부적으로 레드-블랙 트리를 쓰기 때문에 항상 로그 시간 보장이 된다.

---

주요 함수

삽입

std::map<int, std::string> m;
m.insert({1, "one"});
m[2] = "two";   // operator[] 사용

탐색

auto it = m.find(1);  // 키 1을 찾음
if (it != m.end()) {
    std::cout << it->second;  // "one"
}

삭제

m.erase(2);  // 키 2 삭제

순회

for (auto& [key, value] : m) {
    std::cout << key << " => " << value << "\n";
}

---

언제 쓰면 좋은가?

• 데이터를 항상 정렬된 상태로 보관하면서 삽입/탐색/삭제를 모두 효율적으로 하고 싶을 때.

예시
순서가 중요한 데이터 관리

사전(Dictionary) 구현

범위 탐색(lower_bound, upper_bound) 활용할 때

---

레드-블랙 트리

개념

• 레드-블랙 트리는 균형 이진 탐색 트리(Balanced Binary Search Tree) 의 일종
• 일반적인 이진 탐색 트리(BST)는 삽입 순서에 따라 한쪽으로 치우쳐서 최악의 경우 성능이 O(n)까지 떨어질 수 있다.
• 레드-블랙 트리는 "균형 유지 규칙" 을 두어서 트리의 높이가 항상 O(log n) 이 되도록 보장.
• 검색, 삽입, 삭제 모두 O(log n) 시간 복잡도로 동작

---

규칙

• 각 노드는 "빨강(red)" 또는 "검정(black)" 색을 가진다.
  균형을 유지하기 위해 아래 규칙들이 지켜져야 한다

1. 모든 노드는 빨강 또는 검정이다.
2. 루트 노드는 항상 검정이다.
3. 모든 리프(NULL, NIL 노드)는 검정이다.
4. 빨강 노드의 자식은 반드시 검정이다. (빨강이 연속으로 나오면 안 됨)
5. 루트에서 모든 리프(NULL)까지 가는 경로에는 같은 수의 검정 노드가 있어야 한다.
6. 이 규칙들 덕분에 트리가 한쪽으로 심하게 치우치지 않고 균형을 유지

---

삽입/삭제 시 동작

삽입

• 새 노드는 항상 빨강으로 삽입.
• 삽입 후 규칙을 위반할 수 있으므로 "회전(rotation)"과 "색상 변경(recoloring)"을 통해 규칙을 복구합니다.

삭제

• 삭제 시 검정 노드가 빠지면 규칙 5가 깨질 수 있음.
• 이때도 마찬가지로 "회전"과 "색상 변경"을 사용해서 균형을 유지

---

시간 복잡도

• 검색: O(log n)
• 삽입: O(log n)
• 삭제: O(log n)

레드-블랙 트리의 높이는 항상 2 * log2(n+1) 이하로 유지되므로, 최악의 경우에도 균형이 크게 깨지지 않는다.

---

정리

• 레드-블랙 트리는 "균형을 유지하는 이진 탐색 트리"이고, std::map 은 이를 이용해서 항상 정렬된 상태로 key-value 를 관리하며 탐색, 삽입, 삭제 모두 O(log n)을 보장.