[자료구조] 5. STL Map

1. Map 간단 요약

  STL에 속한 Map은 key로 정렬되는 Red-Black Tree 구조이며, key마다 value를 가진다. 데이터의 삽입/삭제 및 탐색의 시간복잡도가 O(logn)으로 빠르다.

 

2. Map 구조

- Map은 Red-Black Tree로 구현되어있다. 이 때 노드의 크기 비교는 key값을 이용한다.

- Red-Black Tree : 자가 균형 이진 탐색 트리

  1) 조건

- 모든 노드는 빨간색 또는 검은색이다.

- 루트 노드는 항상 검은색이다.

- 모든 리프 노드(Null leaf, NIL : 값을 가지지 않는 트리의 끝에 있는 노드)는 검은색이다.

- 빨간색 노드의 자식은 검은색이다. 빨간색 노드가 연속될 시 Double Red라고 부르고, 아래 소개하는 방법들로 해결한다.

- 모든 임의의 노드에서 그 노드의 자손 리프 노드까지 가는 경로의 검은색 노드의 수는 같다.

 

  2) 데이터 삽입 과정

- 삽입은 항상 빨간색 노드로 한다.

- 빨간색 노드의 자식이 빨간색인 경우(= Double Red) 두 가지 선택지 중 하나를 선택한다.

> Restructuring : 부모 노드의 형제 노드가 검은색일때 수행

1. 새로 추가될 노드와 부모 노드, 그리고 부모의 부모노드까지 오름차순으로 정렬한다.
2. 세 노드의 중간값을 부모 노드로 만들고 나머지 노드를 해당 노드의 자식 노드로 만든다.
3. 새 부모 노드를 검은색 노드로 만들고 자식 노드가 된 나머지 노드를 빨간색 노드로 만든다.

Resturcturing 예시

> Recoloring : 부모 노드의 형제 노드가 빨간색일때 수행

새로 추가될 노드의 부모 노드와 부모의 형제 노드를 검은색 노드로 만들고 검은색 노드로 만든 둘의 부모 노드를 빨간색
노드로 만든다. 이때 루트 노드가 검은색이 아니라면 검은색 노드로 만들고, 이 과정을 거친 뒤에 다시 Double Red 문제가
발생하면 조건에 따라 Resturcturing/REecoloring을 Double Red가 발생하지 않을 때까지 반복한다.

Recoloring 예시

 

  3) 데이터 삭제 과정

- 일반적인 이진 트리와 동일한 맥락으로 노드 삭제를 우선 진행한다.

1. 자식이 없는 노드는 삭제 후 조치가 없다.
2. 자식이 하나면 삭제할 노드의 부모 노드가 삭제할 노드의 자식 노드를 가리키게 한 후 노드를 삭제한다.
3. 자식이 두개인 노드는 1) Predecessor(왼쪽 자식 포함 하위 노드 중 가장 큰 값) 또는 2) Successor(오른쪽 자식
포함 하위 노드중 가장 작은 값)을 삭제한 노드의 위치로 가져온다.

 

- 삭제되는 색 : 삭제하는 노드의 자식 노드가 없거나 하나인 경우 삭제되는 노드의 색을, 자식 노드가 둘이라면 삭제되는 노드의 자리를 대체하는 노드(Predecessor/Successor)의 색을 삭제되는 색이라고 해보자.

- 삭제되는 색이 빨간색인 경우 아래의 이유에 근거하여 Red-Black Tree 특성을 해치지 않는다.

1. 다른 색을 추가하지 않았으므로 노드 색은 항상 빨간색이나 검은색이라는 규칙엔 변화가 없다.
2. 루트 노드는 항상 검은색이므로 루트를 제거하지 않았다.
3. 리프 노드는 항상 검은색이므로 제거한 노드와 상관이없다.
4. 빨간색 노드를 추가한 게 아니므로 빨간색 노드의 자식이 검은색이라는 규칙을 위반하지 않는다.
5. 삭제한 노드가 빨간색이므로 임의의 노드에서 리프 노드까지의 검은색 노드의 수에는 변화가 없다.

- 삭제되는 색이 검은색인 경우 2, 3, 5번 규칙을 위반할 가능성이 있다. 따라서 특성을 유지하기 위한 조치가 필요하다.

- 루트 노드가 빨간색이 된 경우 > 루트 노드를 검은색으로 바꿔준다.
- 임의의 노드에서 리프 노드까지 가는 경로의 검은색 노드 수가 일치하지 않게 된 경우

> 삭제된 색을 대체하는 노드에 extra black을 부여하여 해당 노드의 extra black 속성을 검은색으로 카운트한다. 이때 검은색 노드였다면 Double Black, 빨간색 노드였다면 Red-And-Black이라고 부른다.

> Red-And-Black의 경우, 그대로 검은색 노드로 바꾸어준다.

> Double Black의 경우, 다시 네 가지 경우로 나누어 해결한다(아래 해결책은 오른쪽 <> 왼쪽이 바뀌어도 대칭이므로 성립한다).

 

Case 1) Double Black의 오른쪽 형제 노드가 검은색, 그 형제의 오른쪽 자식 노드가 빨간색일때

>	오른쪽 형제 노드는 부모 노드의 색을 부여하고 부모 노드의 색과 오른쪽 형제의 오른쪽
	자식 노드의 색을 검은색으로 한 뒤 부모를 기준으로 왼쪽으로 회전한다.

Case 2) Double Black의 오른쪽 형제 노드가 검은색, 형제의 왼쪽 자식 노드가 빨간색, 오른쪽 자식 노드가 검은색일때

>	형제 노드를 기준으로 오른쪽으로 회전시켜 1.과 같은 형태로 만들어 1.의 해결책을 적용한다.

Case 3) Double Black의 오른쪽 형제 노드 및 형제의 자식 노드가 전부 검은색일때

>	형제 노드를 빨간색으로 바꾸고, Double Black 노드의 extra black 속성을 제거한 뒤 부모에 extra black 속성을
	전달한다. 이후 부모가 Red-And-Black인 경우 검은색 노드로 바꿔 해결하고, 부모가 Double Black이 되면 루트
	노드인 경우 검은색 노드로 바꾸어 해결, 아닌 경우 다시 해결 방법 중 하나를 선택하여 해결한다.

Case 4) Double Black의 형제 노드가 빨간색일때

>	형제 노드를 검은색 노드로 만들어주고, 다시 해결 방법 중 하나를 선택하여 해결한다.

 

3. Map 함수 정리

  1) 반복자(iterator) 관련

- begin() : 가장 왼쪽 노드(가장 작은 key)를 가리키는 iterator 반환

- end() : 가장 오른쪽 노드(가장 큰 key)의 자식 노드(리프 노드)를 가리키는 iterator 반환

- rbegin() : 가장 오른쪽 노드를 가리키는 iterator 반환, rend()와 함께 사용하며 뒤에서 앞으로 가는 반복문에서 사용

- rend() : 가장 왼쪽 노드의 자식 노드를 가리키는 iterator 반환, end()처럼 값이 있는 노드가 리프 노드를 가리킴

- cbegin() : begin()과 동일하나 수정이 불가능한(constant) iterator

- cend() : end()의 constant 버전

- crbegin() : rbegin()의 constant 버전

- crend() : rend()의 constant 버전

 

  2) 크기 관련

- empty() : Map이 비어있다면 true, 아니라면 false 반환

- size() : Map의 크기 반환

- max_size() : Map이 저장할 수 있는 노드의 최대 개수

 

  3) 원소 관련

- at(n) : n을 key로 가지는 value 반환, 없는 경우 out_of_range 예외 호출

- Map[n] : n을 key로 가지는 value 반환, 없는 경우 n을 key로 가지는 노드를 새로 만들고, 해당 레퍼런스 반환

 

  4) Map 수정 관련

- insert() : Map의 원소 추가

- erase() : Map의 원소 제거, erase(iter) : iter가 가리키는 노드 제거, erase(n) : n을 key로 하는 노드 제거, erase(iterFirst, iterEnd) : [iterFirst, iterEnd) 노드 제거

- swap(map) : 함수를 호출한 Map과 매개변수로 전달된 map의 원소 교환

- clear() : Map의 모든 원소 제거

- emplace() : insert와 비슷하나, 주어지는 매개변수로 make_pair()를 내부적으로 수행

- emplace_hint(iter, key, value) : insert의 경우 노드 자리 탐색에 O(logn)의 시간이, Map[]의 경우 선형 탐색이므로 O(n)의 시간이 드는 단점이 있어 emplace_hint()의 iter를 통해 근처의 iterator를 줌으로써 Amortized O(1)의 시간으로 새 노드의 추가가 가능하다.

 

  4) 연산자

- find(n) : n을 key 값으로 갖는 iterator 반환, 없으면 end()를 반환

- count(n) : n을 key 값으로 갖는 원소의 개수를 반환, Map은 key 값이 유일하므로 0 또는 1이 나와야하고, 2가 나오면 false로 간주한다.

- lower_bound(n) : n보다 작거나 같은 key 중에서 가장 큰 key를 가지는 iterator 반환, n을 키로 가지는 노드가 있다면 해당 노드를 반환한다(Predecessor가 아니다! 주의할 것)

- upper_bound(n) : n보다 큰 key 중에서 가장 작은 key를 가지는 iterator 반환 == Successor의 iterator 반환

- equal_range(n) : pair(lower_bound(n), upper_bound(n))를 반환

 

* lower_bound(), upper_bound(), equal_range() 예시

#include <iostream>
#include <map>

using namespace std;

int main()
{
	map<int, char> MyMap;
	
	MyMap.emplace(1, 'b');
	MyMap.emplace(2, 'a');
	MyMap.emplace(3, 'c');

	auto iterLower = MyMap.lower_bound(2);
	auto iterUpper = MyMap.upper_bound(2);

	cout << "iterLower : " << iterLower->first << "-" << iterLower->second << endl;
	cout << "iterUpper : " << iterUpper->first << "-" << iterUpper->second << endl;

	auto iterRange = MyMap.equal_range(2);

	cout << "equal_range : lower[" << iterRange.first->first << "-" << iterRange.first->second << "],";
	cout << "upper[" << iterRange.second->first << " - " << iterRange.second->second << "]" << endl;

	return 0;
}

 

iterLower : 2-a
iterUpper : 3-c
equal_range : lower[2-a], upper[3-c]