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

1. 개요 (Introduction)

• Red-Black Tree (레드-블랙 트리): 노드에 Red/Black 색상을 부여해 균형을 유지하는 Self-Balancing BST (자가 균형 이진 탐색 트리).
• 일반 BST의 최악 시간 복잡도 O(N)을 O(log N)으로 개선.
• 삽입·삭제 시 Recoloring (색상 변경)과 Rotation (회전)으로 균형 유지.

2. Properties (핵심 규칙)

1. Node Color: 모든 노드는 Red 또는 Black.
2. Root Property: 루트는 반드시 Black.
3. Red Property: Red 노드의 자식은 반드시 Black. (연속 Red 금지)
4. Black Property: 임의의 노드에서 모든 하위 NIL 리프까지 Black 노드 수가 동일.
5. Leaf Property: 모든 NIL Leaf (빈 리프)는 Black.

3. Balancing (균형 유지)

• Red 연속 금지 + 동일한 Black 노드 수로 균형 보장.
• 가장 긴 루트-리프 경로는 가장 짧은 경로의 최대 2배.
• 따라서 일렬로 연결된 3개의 실제 노드만으로 이루어진 트리는 불가능.

Inferred Properties (파생 속성)

• Black Height (흑색 높이): 노드에서 하위 NIL 리프까지의 Black 노드 수.
• Black Depth (흑색 깊이): 루트부터 해당 노드까지의 Black 노드 수.
• 경로상 Red가 연속되지 않으므로 Black 노드가 적어도 절반을 차지.
• 트리 높이: h ≤ 2log₂(N+1) → O(log N).

4. Basic Operations (기본 연산)

Rotation (회전)

BST의 정렬 순서(Inorder)를 유지하면서 트리 구조 변경.

• Left Rotation (좌회전): 오른쪽 자식이 부모 자리로 상승.

  1. 오른쪽 자식의 왼쪽 서브트리 → 기존 노드의 오른쪽.
  2. 오른쪽 자식 → 기존 노드의 부모 위치.
  3. 기존 노드 → 오른쪽 자식의 왼쪽.

• Right Rotation (우회전): 좌회전의 반대.

  1. 왼쪽 자식의 오른쪽 서브트리 → 기존 노드의 왼쪽.
  2. 왼쪽 자식 → 기존 노드의 부모 위치.
  3. 기존 노드 → 왼쪽 자식의 오른쪽.

• 회전 시 부모 포인터와 루트 연결도 갱신해야 함.

Insertion (삽입)

1. 일반 BST 방식으로 새 노드를 Red로 삽입.
2. 부모가 Black이면 종료.
3. 부모가 Red면 Double Red (연속 Red) 해결.

조건	해결
Uncle (삼촌) Red	부모·삼촌 → Black, 조부모 → Red, 위쪽으로 재검사
Uncle Black, Triangle (삼각형)	부모 기준 회전 → 일직선 형태
Uncle Black, Line (일직선)	조부모 기준 회전 + 색상 변경

• 좌우 대칭 상황은 회전 방향만 반대.
• 마지막에 루트를 Black으로 설정.

Searching (탐색)

• 일반 BST와 동일.
• 현재 노드와 비교해 작으면 왼쪽, 크면 오른쪽으로 이동.
• 일치하는 노드 또는 NIL에 도달하면 종료.

Deletion (삭제)

1. 일반 BST 방식으로 삭제.
2. Black 노드가 제거되어 Black Height가 달라지면 수정.
3. Double Black (이중 흑색) 상태를 형제 노드 기준으로 처리.

Sibling (형제) 상태	해결
Red	부모 기준 회전 + 색상 변경
Black, 자식 모두 Black	형제 → Red, 부족한 Black을 부모로 전파
Black, 먼 자식 Red	부모 기준 회전 + 색상 변경
Black, 가까운 자식 Red	형제 기준 회전으로 먼 자식 Red 형태로 변환 후 처리

※ Near/Far는 부모 기준으로 가까운 쪽과 먼 쪽을 의미.

5. Implementation (구현)

• Node: data, color, left, right, parent.
• NIL Sentinel (센티널 노드): Black인 가상 리프로 빈 자식을 표현.
• leftRotate / rightRotate: 트리 구조 변경.
• fixInsert: 부모·삼촌·조부모 색상을 확인하고 색상 변경 및 회전 반복.
• insert: BST 삽입 → Red-Black 규칙 복구.
• inorder: 정렬된 키와 노드 색상 출력.

예시: 10, 20, 30, 15 순서로 삽입.

10(B), 15(R), 20(B), 30(B) 순서로 Inorder 출력.

6. Advantages (장점)

• 탐색·삽입·삭제의 최악 시간 복잡도 O(log N) 보장.
• 자동 균형 유지로 안정적인 성능.
• Map, Set 등 정렬 기반 자료구조 구현에 적합.

7. Disadvantages (단점)

• 일반 BST나 AVL Tree에 비해 삽입·삭제의 색상 처리 및 회전 규칙이 복잡할 수 있음.
• 균형 유지를 위한 추가 연산 비용 발생.

8. Applications (활용)

• Containers (컨테이너): C++ std::map, std::set, Java TreeMap.
• Operating System (운영체제): 프로세스 스케줄링, 가상 메모리 영역 관리.
• File System (파일 시스템): 디렉터리·디스크 블록 관리.
• Networking (네트워크): 패킷 필터링, 라우팅 테이블 탐색.
• Database (데이터베이스): 인메모리 인덱싱 및 빠른 데이터 검색.

9. Also Check (관련 개념)

• Self-Balancing BST (자가 균형 이진 탐색 트리)
• Red-Black Tree vs AVL Tree
• Heap vs Red-Black Tree
• Top-Down Insertion (하향식 삽입)

10. 시간 복잡도 정리

연산	시간 복잡도
Search	O(log N)
Insert	O(log N)
Delete	O(log N)
Rotation (단일 회전)	O(1)

핵심: Red-Black Tree는 색상 규칙을 통해 높이를 O(log N)으로 제한하고, 삽입·삭제 시 Recoloring과 Rotation으로 균형을 복구하는 BST이다.