ft_containers[Map]

Map을 구현하기 전 cplusplus에서 어떻게 생겨먹은 놈인지 확인해야 한다.

설명을 보자 하니 듣던 대로 암 걸리는 놈이긴 한 듯하다.

---

기본 설정

Map은 key, value로 이루어져 저장되는 컨테이너이다.

또한, 매핑된 값은 해당 key와 관련된 내용을 저장한다.

key와 매핑된 값의 타입은 다를 수 있고, 이 둘은 member type으로 그룹화되는데 그룹화의 방식은 pair이다.

typedef pair<const Key, T> value_type;

 

내부적으로는 항상 정렬되어 있는데, 이는 내부의 비교 object(key_comp)를 따라 key를 기준으로 정렬된다.

기본 Map과는 다르기 Unordered_map이 있는데 Unordered_map은 정렬을 해주지 않기 때문에 기존 Map보다 더 빠르다.

Map은 bracket operator(operator [])로 key값을 통해 접근할 수 있다. (이것으로 보아 key는 중복이 허용되지 않는다.)

Map은 전형적으로 BST(binary Search Tree)로서 작동한다.

 

---

BST(Binary Search Tree)[이진 탐색 트리]

BST는 여러 가지 규칙을 가진 노드 기반 이진트리 데이터이다.

1. 노드의 왼쪽은 해당 노드의 key보다 작은 key들의 모임이다.
2. 노드의 오른쪽은 해당 노드의 key보다 큰 key들의 모임이다.
3. 왼쪽, 오른쪽 트리는 똑같은 형태를 갖고 있다.

BST는 빠른 탐색, 삽입, 삭제가 가능한 자료구조이다.

그리고 구현 방식은 매우 많다.

ex) AA, AVL, Red-Black, splay, etc....

 

많은 방식들이 존재하지만 몇 가지만 들춰볼 것이다.

 

---

AVL Tree

 

AVL Tree는 발명자(Adelson-Velsky and Landis)에서 따온 자가 균형 이진 탐색 트리이다.

자가 균형 이진 탐색 트리는 스스로 균형을 잡는 데이터 구조인데 지금은 여러 가지 방식이 있지만 AVL이 그 첫 발자국이다.

균형을 잡는 기준은 높이이다.

한 노드의 두 자식 서브 트리의 높이는 항상 최대 1만큼 차이가 나는데, 만약에 높이 차이가 1보다 커지면 속성을 유지하기 위해 스스로 균형을 잡는다.(높이 균형 성질)

검색, 삽입, 삭제는 모두 평균과 최악의 경우 O(log n)을 갖는다.

삽입과 삭제는 한 번 이상의 트리 회전을 통해 균형을 잡을 수 있다.

 

일반적인 BST처럼 삽입, 삭제를 동작하면 높이 균형 성질을 만족하지 못하니 동작할 때 회전을 통해 트리를 재구성하여 높이 균형 성질을 만족시킨다.

 

---

Red-Black Tree

 

Red-Black Tree는 이진 트리의 특수한 형태로서, 컴퓨터 공학 분야에서 숫자 등의 비교 가능한 자료를 정리하는 데 쓰이는 자료구조이다.

Red-Black Tree는 자료의 삽입과 삭제, 검색에서 최악의 경우에도 일정한 실행 시간을 보장한다.

AVL은 RB보다 엄격하게 균형이 잡혀있기 때문에 삽입, 삭제를 할 때 더 많은 회전이 발생한다.

RB Tree는 함수형 프로그래밍에서 특히 유용한데, 연관 배열이나 set 등을 내부적으로 RB Tree로 구현해 놓은 경우가 많다.

RB Tree는 몇가지 특징들을 갖고 있는 아래와 같다.

1. 노드는 Red or Black이다.
2. 루트 노드는 Black이다.
3. 모든 리프 노드들은(NIL)은 Black이다.
4. Red 노드의 자식 노드들은 Black이다.(즉, Red 노드는 연달아 나타날 수 없다.)
5. 어떤 노드로 부터 시작되어 그에 속한 하위 리프 노드에 도달하는 모든 경로에는 리프 노드를 제외하면 모두 같은 개수의 Black노드가 있다.

 

---

AA Tree

 

AA Tree는 RB Tree를 응용한 Tree로 RB Tree의 많은 조건을 일부 제거하여 구현을 더 간단하게 만든 트리로 균형을 맞추기 위해 레벨의 개념을 사용한 Tree이다.

부모와 레벨이 같은 자식 노드의 견결을 수평 링크라 하며, 이 노드를 구분하기 위해 Red라는 개념을 이용한다.

AA Tree는 몇 가지 특징들을 갖고 있는 아래와 같다.

1. 왼쪽 자식은 Red가 될 수 없다.
2. 연속으로 Red가 올 수 없다.(이중 Red 불가 == 이중 수평 링크)
3. 루트 노드에서 리프 노드까지의 경로에는 동일한 개수의 Black 노드가 존재한다.(RB Tree)
4. 모든 리프 노드의 레벨은 1이다.
5. 모든 왼쪽 자식의 레벨은 부모의 레벨보다 1 낮다.
6. 모든 오른쪽 자식의 레벨은 부모의 레벨과 같거나 1 낮다.
7. 모든 오른쪽 손자의 레벨은 할아버지 노드보다 낮다.
8. 1보다 큰 레벨의 모든 노드들은 2개의 자식을 갖는다.

 

---

다 어려워 보이는데... 이래서 map부터 막막하다고 들었던 것 같다.

또한, 보너스에서 set을 구현하는데 위에서 말했듯이 set은 내부적으로 RB Tree로 구현해 놓은 경우가 많으니 map도 RB Tree로 구현한 느낌이다.

나도 보너스를 포기할 수 없으니 RB Tree로 구현해보고 나중에 AVL, AA를 따로 구현해보도록 하겠다.