[자료구조] 레드블랙트리란?

1. 레드-블랙 트리란?

레드-블랙 트리는 자가 균형 이진 탐색 트리이다.
이진 탐색 트리는 균형이 안맞을 경우, 최악 시간 복잡도는 O(N) 이다.
하지만, RB Tree는 삽입, 삭제 동안 트리의 모양이 균형 잡히도록 각 노드들은 Red 혹은 Black의 색상을 가지고 모든 경우에서 O(lonN)의 시간 복잡도를 보장받는다.

2. 사용 용도

• 각종 기하학 계산
• 함수형 프로그래밍에서의 연관 배열, 집합
• C++의 map의 자료구조
• 자바의 TreeMap의 자료구조

3. RB Tree의 조건

1. 모든 노드는 빨간색 혹은 검은색이다.
2. 루트 노드는 검은색이다.
3. 모든 리프 노드(NIL)들은 검은색이다.

   NIL : null leaf, 자료를 갖지 않고 트리의 끝을 나타내는 노드

4. 빨간색 노드의 자식은 검은색이다.
   👉 No Double Red. 빨간색 노드가 연속으로 나올 수 없다
5. 모든 리프 노드에서 Black Depth는 같다.
   👉 리프노드에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다.

4. 삽입 과정

RB Tree는 새로운 노드를 삽입할 때 항상 빨간색으로 삽입한다.

이 때, Double Red가 발생할 수 있고 2가지 전략을 사용할 수 있다.

앞으로 새로 삽입할 노드를 N(New), 부모 노드를 P(Parent), 조상 노드를 G(Grand Parent), 삼촌 노드를 U(Uncle)라고 하자.

Double Red가 발생했을 때

• 삼촌 노드가 검은색이라면 -> Restructuring
• 삼촌 노드가 빨간색이라면 -> Recoloring

1) Restructuring

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

여기서 많이들 헷갈리는 게 완성된 트리가 규칙 3(모든 리프 노드는 검은색)을 만족하지 않는 것처럼 보일 수 있다.
값이 2인 노드는 자식 노드 NIL 2개를 가지고 있고 그 NIL들이 검은색이라고 생각하면 된다.

2) Recoloring

1. 새로운 노드(N)의 부모(P)와 삼촌(U)을 검은색으로 바꾸고 조상(G)을 빨간색으로 바꾼다.
1-1. 조상(G)이 루트 노드라면 검은색으로 바꾼다.
1-2. 조상(G)을 빨간색으로 바꿨을 때 또다시 Double Red가 발생한다면 또다시 Restructuring 혹은 Recoloring을 진행해서 Double Red 문제가 발생하지 않을 때까지 반복한다.

검은색 노드는 2번 나와도 된다. 빨간색 노드가 2번 나오면 안 되는 것이다. 

Recoloring은 간단해 보이지만 문제는 조상 노드(G)가 루트 노드가 아니면서, 조상 노드(G)가 또다시 Double Red 문제가 발생하는 경우이다. 이런 경우 1-2에 따라 Restructuring 혹은 Recoloring을 반복해서 실행한다.

원문(Reference)

https://code-lab1.tistory.com/62