map을 구현하기 위해서는 기본적으로 값의 삽입, 탐색, 삭제에 걸리는 시간복잡도가 O(logN)을 만족하는 자료구조를 사용해야한다.
즉 이진탐색트리를 사용하는 것이 적절한데, 보너스 과제에서 Red-Black Tree를 사용할 것을 요구하고 있어 일단은 Red-Black tree를 사용하여 구현해보기로 결정했다.
참고자료 : 쉬운코드 유튜브
1부 : https://youtu.be/2MdsebfJOyM
2부 : https://youtu.be/6drLl777k-E
레드블랙 트리란?
이진 탐색 트리의 문제점인 편향된 트리의 문제점을 해결하여 자료가 삽입 된 후 스스로 균형을 잡는 트리이다.
<자가 균형 이진탐색트리(Self-balancing binary search tree)> 라고도 부른다.
예를 들어 다음과 같이 정렬된 자료를 이진 탐색 트리에 삽입할 경우 시간복잡도는 O(N)이 된다.
그러나 레드 블랙 트리에서는 삽입 후 노드의 재배치를 통해 편향된 트리를 교정해준다.
레드블랙트리의 규칙
레드블랙트리에 삽입되는 노드들은 반드시 다음과 같은 규칙을 따라야 한다.
- 모든 노드는 검은색 혹은 빨간색이다.
- 루트 노드는 반드시 검은색이다.
- 모든 종단 노드는 기본적으로 양쪽 자식으로 nil노드를 가지며, nil노드는 검은색이다.
- 빨간색 노드의 자식은 반드시 검은색이다. (즉, 빨간색 노드가 연속될 수 없다. 검은색 노드는 연속될 수 있음.)
- 임의의 노드에서 nil노드까지 가는 경로에서 만나는 Black노드의 갯수는 같다. (자기 자신은 카운트 하지 않음.)
- 삽입되는 노드는 빨간색이다.
노드가 새롭게 삽입 될 시 4번 규칙과 5번 규칙을 위반하는 경우가 생기고, 이러한 규칙 위반이 생기면 트리를 회전하거나 노드들의 색깔을 바꿔주며 트리의 균형을 맞춰주게 된다.
레드블랙트리의 노드 삽입
레드블랙트리의 삽입에서 문제가 시작되는 부분은 Double red, 즉 삽입된 노드의 부모가 빨간색이라, 빨간색 노드의 중복이 나타나는 경우이다.
이러한 경우는 총 3가지 케이스로 분류할 수 있으며, 각 케이스에 따른 해결법은 다음과 같다.
case 1 : 삽입된 노드의 부모가 RED이며 삼촌 노드도 RED인 경우
-> 부모와 삼촌을 BLACK으로 바꾸고 조부모를 RED로 바꿔 해결.
주의해야 할 점은 색상을 변경하고 난 후에 조부모노드와 고조부모 노드의 규칙 위반이 발생할 수도 있다는 것이다. 따라서 트리의 Root까지 타고 올라가며 트리가 규칙을 모두 준수하고 있는지 확인해야 한다. 이는 case2와 case3에서도 마찬가지다.
case 2 : 삽입된 노드가 부모의 오른쪽 자식 && 부모가 조부모의 왼쪽 자식 && 삼촌이 BLACK인 경우
-> 부모를 기준으로 왼쪽으로 회전한 뒤 case 3을 실행.
오른쪽 왼쪽이 서로 바뀌어도 위의 해결 방법은 성립한다.
case 3 : 삽입된 노드가 부모의 왼쪽 자식 && 부모가 조부모의 왼쪽자식 && 삼촌이 BLACK인 경우
-> 부모와 할아버지의 색을 바꾼 후 할아버지를 기준으로 오른쪽으로 회전.
마찬가지로 역의 경우에도 해결 방법은 성립한다.
레드블랙트리의 노드 삭제
사실 이게 진짜 까다로운 부분 ㅠㅠ
레드블랙트리의 노드 삭제에서 문제가 되는 부분은 BLACK 노드가 삭제가 되는 경우이다. BLACK이 삭제 될 경우 RBT 규칙의 2번, 4번, 5번을 위반할 수 있게되며, 삭제 후 조정을 통해 이러한 위반 사항을 제거해줘야 한다.
먼저 black 노드가 삭제되는 경우, 아주 특수한 경우(루트노드와 자식 하나만 있을 때 루트가 삭제되는 경우)를 제외하고는 반드시 5번규칙 <임의의 노드부터 nil노드까지 가는 경로에서 만나는 BLACK 노드의 갯수는 같다>를 위반하게 된다.
따라서 이를 조정하기 위해 삭제된 색의 위치를 대체한 노드에 EXTRA BLACK을 부여한다. 그리고 경로에서 black의 갯수를 카운트 할 때extra BLACK역시 하나의 BLACK으로 카운트 한다. 이렇게 Doubly BLACK 노드를 만들거나, RED-BLACK 노드를 만드는 식으로 먼저 5번 규칙을 다시 준수하게 만들어준다.
이렇게 생기는 doubly BLACK 노드와 RED-BLACK 노드는 트리를 조정하여 레드블랙트리의 규칙을 준수하도록 만들어줘야한다.
먼저 RED-BLACK 노드는 BLACK 노드로 바꾸어주면 문제를 해결할 수 있다.
Doubly Black이 부여된 노드라면 트리를 조정하여 EXTRA BLACK을 없애주어야 한다.
총 4가지 케이스가 있다.
case 1 : DOUBLY BLACK의 오른쪽 형제가 RED일때
-> 부모와 형제의 색을 바꾸고 부모를 기준으로 왼쪽으로 회전한 뒤 남아있는 DOUBLY BLACK을 기준으로 case 2, 3, 4 중 적절한 케이스를 실행하여 해결.
오른쪽 왼쪽이 바뀌어도 똑같은 방식으로 해결할 수 있다.
case 2 : DOUBLY BLACK의 형제가 BLACK && 형제의 두 자녀 모두 BLACK일때
-> DOUBLY BLACK과 그 형제의 BLACK을 모아서 부모에게 전달한 후(자식 노드의 색이 같을 때 부모와 자식의 색을 바꿔도 레드블랙 트리의 속성을 유지하는 특성을 이용) 부모에게 EXTRA BLACK의 해결을 위임한다.
이때 DOUBLY BLACK을 받은 부모 노드가 RED-BLACK이라면 부모노드의 색을 BLACK으로 바꿔주면 되고, DOUBLY BLACK이 되었다면 다시 케이스 1, 2, 3, 4 중 하나를 실행하여 규칙 위반을 해소해주어야 한다.
case 3 : DOUBLY BLACK의 오른쪽 형제가 BLACK && 형제의 왼쪽 자녀가 RED && 형제의 오른쪽 자녀가 BLACK
-> DOUBLY BLACK의 형제의 오른쪽 자녀를 RED로 만든 후 case 4를 적용하여 해결.
이렇게 case 4번의 조건을 만족시켜 준 후 case 4의 방법으로 해결한다.
오른쪽 왼쪽이 바뀌어있어도 동일한 방식으로 해결할 수 있다.
case 4 : DOUBLY BLACK의 오른쪽 형제가 BLACK && 형제의 오른쪽 자녀가 RED
-> 오른쪽 형제는 부모의 색으로, 오른쪽 형제의 오른쪽 자녀는 BLACK으로, 부모는 BLACK으로 바꾼 후에 부모를 기준으로 왼쪽으로 회전
오른쪽 왼쪽이 바뀌어있어도 동일한 방식으로 해결할 수 있다.
레드블랙트리의 시간복잡도
레드블랙트리는 삽입/삭제 이후해 조정 과정을 통해 트리의 균형을 유지하므로,
삽입, 삭제, 탐색 모두 O(logN)의 시간복잡도를 보장한다.
더 자세한 내용이 궁금하다면 아래의 유튜브 링크로...
참고자료 : 쉬운코드 유튜브
1부 : https://youtu.be/2MdsebfJOyM
'42 > 42cursus' 카테고리의 다른 글
| [inception] 1. VM 설치하기 (0) | 2022.10.18 |
|---|---|
| [webserv] 1. HTTP(HyperText Transfer Protocol)란? (2) | 2022.08.10 |
| [ft_containers] 4. map 이해하기 (0) | 2022.07.20 |
| [ft_containers] 3. std::allocator 사용하기 (0) | 2022.07.12 |
| [ft_containers] 2. 템플릿 메타 프로그래밍과 is_integral, enable_if (0) | 2022.07.12 |
댓글