STL map

▶ STL map

연관 컨테이너 중 하나로 자료구조는 트리로 구성. (레드 블랙 트리)

각 노드가 Key, Value 가 pair 형태로 구성.

자동으로 오름차순 정렬.

Key값은 중복이 되지 않고 Value값은 중복이 가능.

map은 자료를 저장할 때 내부에서 자동으로 정렬.

map은 key를 기준으로 정렬하며 오름차순으로 정렬.

- 내림차순 정렬을 하고 싶다면 map<int, int, greater> _map; 으로 선언

 

◇ 사용하면 유리한 조건

1. 정렬이 필요하다.

2. 많은 자료를 저장하고, 검색이 빨라야 한다.

3. 빈번한 삽입과 삭제가 발생하지않는다.

 

◆ 레드블랙트리

일종의 자가 균형 이진 탐색 트리.

1. 모든 노드는 빨간색 혹은 검은색.

2. 루트 노드는 검은색.

3. 모든 리프 노드(NIL: null leaf, 자료를 갖지않고 트리의 끝을 나타내는 노드)들은 검은색.

4. 빨간색 노드의 자식은 검은색.

- 빨간색 노드가 연속으로 나올 수 없다.

5. 모든 리프 노드에서 Black Depth는 같다.

- 리프노드에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다.

자가 균형 이진 탐색 트리로 삽입과 삭제가 일어나는 경우 자동으로 그 높이를 작게 유지하는 이진 탐색 트리.

높이를 작게 유지하는 이유는 연산 과정에서 트리의 높이가 한족으로 치우치는 것을 막기 위함.

O(log n)의 시간 복잡도를 가짐.

- 삽입 연산

새로 삽입되는 노드의 색은 무조건 red.

double red가 발생하지 않기 위해 다음 2가지 전략을 통해 해결.

1. Recoloring

- 새로 삽입된 노드의 삼촌 노드(부모 노드와 형제인 노드)가 red인 경우 수행

   ㄴ 새로 삽입된 노드의 부모 노드, 삼촌 노드를 black으로 하고 조부모 노드를 red로 한다.

   ㄴ 조부모 노드가 루트 노드가 아니라면 double red가 다시 발생할 수 있다.

   ㄴ 위와 같은 상황이 발생하면 그때 다시 recoloring 또는 rotation 연산을 수행.

2. Rotation

- 새로 삽입된 노드의 삼촌 노드가 black 이거나 null인 경우 수행

   ㄴ 새로 삽입된 노드, 부모 노드, 조부모 노드를 오름차순으로 정렬.

   ㄴ 이후, 중간에 위치한 노드를 부모 노드로 하고 나머지 두 노드를 자식 노드로 만듬.

   ㄴ 부모 노드를 blakc으로 하고, 두 자식들을 red로 한다.

 

◇ 이진 탐색 트리

자신의 왼쪽 서브 트리에는 현재 노드보다 작은 값, 오른쪽 서브 트리에는 큰 값.

이 특성 때문에 이진 탐색 트리 시간복잡도는 O(log n).

 

◆ 시간 복잡도

일반적으로 최악의 경우를 고려하는 빅오 표기법이 많이 사용.

Big-O 표기법의 종류

1. O(1)

- 일정한 복잡도라고 하며, 입력값이 증가하더라도 시간이 늘지 않는다.

2. O(n)

- 선형 복잡도이며, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가.

3. O(log n)

- 로그 복잡도이며, Big-O 표기법 중 O(1) 다음으로 빠른 시간 복잡도를 가짐.

- 자료구조 중 BST(Binary Search Tree) 방법

- BST에서는 원하는 값을 탐색할 때, 노드를 이동할 때마다 경우의 수가 절반으로 줄어듬.

4. O(n2)

- 2차 복잡도이며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미.

5. O(2n)

- 기하급수적 복잡도이며, Big-O표기법 중 가장 느린 복잡도를 가짐.

- 구현 알고리즘이 O(2n)일 경우 다른 방식을 사용하는 것을 고민해야 함.

 

◆ set

key라고 불리는 원소들의 집합으로 이루어진 컨테이너.

key값은 중복이 허용되지 않는 다는 점.

set은 key값의 순서대로 정렬이 되는 특징이 있음.