RB-Tree 구현하기 (C언어) - Part.3 삽입 이론 설명

RB-Tree의 주요 속성 (5가지 규칙)

1. 모든 노드는 레드 또는 블랙이다.
2. 루트 노드는 항상 블랙이다.
3. 모든 리프 노드(NIL 노드)는 블랙이다.
4. 레드 노드의 자식은 반드시 블랙이다.
   → 즉, Red 노드는 연속해서 올 수 없다.
5. 어떤 노드에서 리프 노드까지 가는 모든 경로에는 동일한 개수의 Black 노드가 있다.
   → 이를 black-height라고 한다.

이 규칙을 다시 작성해 두는 이유는 이 규칙이 매우 중요하기 때문이다.

삽입 연산의 개요

RB-Tree의 삽입은 기본적으로 이진 탐색 트리(BST)의 삽입과 유사하다. 하지만 삽입 후에는 RB-Tree의 규칙을 깨뜨릴 수 있으므로, 삽입 후 Fix-Up(재조정) 과정을 통해 트리를 다시 균형 있게 만든다.

삽입 기본 과정

1. 새 노드 생성: 새 노드는 항상 Red 색으로 생성한다.
2. BST 삽입: 일반적인 이진 탐색 트리 규칙에 따라 위치를 찾아 삽입한다.
3. Fix-Up 수행: 삽입 후 RB-Tree의 속성이 깨졌을 경우, 색 변경 및 회전(Rotation) 을 통해 트리를 수정한다.

Fix-Up (삽입 후 재조정)의 세 가지 주요 경우

Fix-Up 과정은 부모가 Red일 때만 문제가 된다. 삼촌 노드의 색깔에 따라 다음 세 가지 경우로 나뉜다:

▶ Case 1: 삼촌 노드가 Red인 경우

• 해결 방법: 부모와 삼촌을 Black으로 바꾸고, 조부모를 Red로 변경한 후 조부모를 기준으로 다시 Fix-Up을 반복한다.

▶ Case 2: 삼촌 노드가 Black이고, 삽입 노드가 "삼각형" 구조인 경우 (예: 왼쪽-오른쪽 또는 오른쪽-왼쪽)

• 해결 방법: 부모를 기준으로 회전(Rotation)을 통해 "직선 구조"로 바꿔 Case 3으로 전환한다.

case 2 예시

▶ Case 3: 삼촌 노드가 Black이고, 삽입 노드가 "직선 구조"인 경우 (예: 왼쪽-왼쪽 또는 오른쪽-오른쪽)

• 해결 방법: 조부모를 기준으로 회전(Rotation)을 하고, 색상을 재조정하여 속성을 복구한다.

회전

• 회전 연산에서는 서브트리의 노드 위치가 바뀐다.
• 회전 연산은 삽입, 삭제 등의 다른 연산으로 인해 레드-블랙 트리의 속성이 침해될 때 레드-블랙 트리의 속성을 유지하기 위해 사용된다.
• 회전에는 두 가지 유형이 있다.

왼쪽 회전

왼쪽 회전 예시

오른쪽 회전 예시

오른쪽 회전 예시

 

왜 삽입 노드는 Red인가?

새로 삽입된 노드를 Red로 설정하는 이유는 다음과 같다:

• Black 노드를 추가하면 경로의 black-height가 달라져 속성 5를 바로 위반한다.
• 반면 Red 노드를 추가하면, 부모가 Black이면 바로 속성을 만족하고, 부모가 Red일 경우에만 재조정이 필요하다.

즉, 삽입 후 조정 비용을 최소화하기 위해 Red로 삽입한다.

---

출처

이미지 출처: https://www.programiz.com/dsa/red-black-tree