RB(RED-BLACK) TREE

#레드-블랙 트리(Red-Black Tree)

레드-블랙 트리에 대해 알아보자. 일단 가장 중요한 키워트는 자가 군형 이진 트리.라는거다. 또한 레드-블랙 트리는 아래와 같은 조건들을 만족한다.

1. 모든 노드는 Red 혹은 Black이다.

2. 루트 노드는 Black이다.

3. 모든 리프 노드(NIL : 자료가 없이, 트리의 끝만을 나타내는 노드)는 검은 색이다.

4. 붉은 색(Red) 노드의 자식은 검은색이다.

5. 모든 리프 노드에서 Black Depth는 같다. -> 리프 노드에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 수는 모두 같다.

레드 - 블랙 트리 삽입 과정

일단 레드-블랙 트리에 새로운 노드를 삽입할 때 새로운 노드는 항상 Red로 삽입한다. 그러면 4번 규칙. Red의 자식은 검은 색이라는 규칙에 위배된다. 이를 (Double Red)라고 하는데, 이를 해결하기 위해 2가지 방법을 사용한다고 한다.

그것을 알아보기 전에, 새로 삽입하는 노드를 N(New), 부모 노드를 P(Parent), 조상 노드를 G(Grand Parent, 2차 부모), 친척 노드를 U(Uncle), 친척 노드는 부모의 형제라고 생각하자.

1. Uncle Node가 검은색이면 Restructuring을 수행하고.
2. Uncle Node가 빨간색이면 Recoloring을 수행한다.

Restructuring

Uncle Node가 검은색일 때, 부모 노드의 새로운 자식 노드로 새로운 노드를 끼워넣는 시나리오다.

1. 새로운 노드, 부모 노드, 조상 노드를 오름차 순으로 정렬한다.(Uncle Node는 제외된다.)
2. 셋 중 중간값을 부모로 만들고, 나머지 둘을 자식으로 만든다.
3. 새로 부모가 된 노드를 검은색으로 만들고, 나머지 자식들을 붉은 색으로 만든다.

일단 Double Red가 발생했는데, Uncle Node가 검은 색이다. 그러면 이 소주제처럼 Restructuring을 한다.

새로운 노드, 부모 노드, 조상 노드를 오름차 순으로 정렬한다. 그러면 2,3,5가 남을텐데 그 중에 중간값은 3이다.

3을 부모로 바꾸고, 나머지 2,5를 자식으로 바꾼다. 5의 자식 노드인 7인 자연스레 옮겨가게 된다.

그러면 일단 그림상으로 2,3은 Double Red이다.

그래서 부모인 3을 Black으로 바꿔주고, 새로 자식으로 정의된 2,5를 Red로 바꿔주면 트리가 완성된다.

Recoloring

Uncle Node가 붉은색일 때, 부모 노드의 새로운 자식 노드로 새로운 노드를 끼워넣는 시나리오다.

1. 새로운 노드의 부모와 삼촌을 검은색으로 바꾸고, 조상을 붉은색으로 바꾼다. 1-1. 조상이 루트라면 또 검은색으로 바꾼다. 1-2. 조상을 붉은 색으로 바꿨을 때, Double Red가 발생한다면 또 다시, Restructuring이나 Recoloring을 사용하여 Double Red 문제가 발생하지 않을 때까지 반복한다.

자, Double Red가 발생했는데 삼촌 노드가 빨간색이니, Recoloring을 한다.

부모와 삼촌을 검은색으로 전부 바꿔주고… 조상님을 붉은 색으로 바꿔준다.

그런데, 조상님은 루트 노드다. 따라서 검은색으로 다시 바꿔준다. 이러면 Double Red문제가 해결된다. 검은색은 2연속 나와도 상관없는게 Red-Black Tree이다.

다만 이 경우가 아니라 다른 문제가 있을 수 있다.

우리는 N으로 3을 넣는다. P는 2이며, G는 5이다. U는 7이다. 여기서 Recoloring을 진행하면 오른쪽 트리가 된단다.

조상님을 붉은색으로 바꾸면, 또 조상님이 N인 기준에서 Double Red 이슈가 발생한다. 그러면 그 위로 거슬러 올라가야 한다.

조상님의 Uncle Node가 붉은 색이므로, 다시 ReColoring을 진행하면 Double Red문제가 해결된다. 만약 Uncle Node가 검은색이라면 Restructuring을 해줘서 색을 맞춰주면 된다.

C++의 STL인 Map과 Set

unordered가 아닌 Map과 Set은 RB-TREE로 구현되어 있다. 따라서 항상 정렬된 상태를 유지하고 있으며, RB TREE는 높이가 균형을 유지하도록 보장하기 때문에 삽입, 삭제, 탐색, 연산 모두 평균 및 최악의 경우 O(log n)시간 복잡도를 가진다. <- 아마 이 부분에서 성능을 예측하기 쉽고 편차가 적은 장점이 있어 Map과 Set에서 RB-TREE를 선택한 게 아닌가 한다.

레드-블랙 트리 시뮬레이터

https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

레퍼런스

https://code-lab1.com/red-black-tree/

사실상 내가 공부하며 옮겨 적은 느낌이다.

Algorithm 카테고리 내 다른 글 보러가기