RB Tree

RB 트리란?

기본적인 '이진 탐색 트리(BST)'는 평균적으로 O(log n)의 빠른 탐색, 삽입, 삭제 성능을 보여준다. 하지만 이는 트리가 균형 잡혀 있을 때의 이야기다. 만약 데이터가 정렬된 순서(예: 1, 2, 3, 4, 5)로 들어오면 트리는 다음과 같이 한쪽으로 치우친, '편향 트리(skewed tree)'가 된다.

1
 \
  2
   \
    3
     \
      4
       \
        5

이런 최악의 경우, 트리의 높이가 데이터의 수(n)와 같아져 탐색 성능이 'O(n)'으로 저하된다. 이는 연결 리스트(linked list)와 다를 바 없는 비효율적인 구조다.

이 문제를 해결하기 위해 등장한 것이 '자가 균형 이진 탐색 트리(Self-Balancing BST)'다. 데이터의 삽입, 삭제가 발생할 때마다 트리 스스로 구조를 재조정하여 높이를 항상 O(log n) 수준으로 유지하는 자료구조다.

레드-블랙 트리는 그중 가장 널리 쓰이는 자가 균형 이진 탐색 트리로, 몇 가지 간단한 색깔 규칙(Red/Black)과 회전(Rotation) 연산을 통해 효율적으로 트리의 균형을 맞춘다.

정의 및 목표

• 정의: 이진 탐색 트리의 한 종류로, 삽입/삭제가 잦아도 항상 O(log n) 높이를 유지하도록 색깔(레드, 블랙) 규칙을 덧붙인 자가 균형 자료구조.
• 목표 1: 검색, 삽입, 삭제 연산을 최악의 경우에도 O(log n) 시간 복잡도 안에 끝낸다.
• 목표 2: 균형을 잡기 위한 코드는 간단한 “색 변경 + 회전” 연산만 사용한다.

5가지 필수 속성

레드-블랙 트리는 다음 5가지 속성을 항상 만족해야 한다.

속성	설명
(1)	모든 노드는 🔴RED 또는 ⚫️BLACK이다.
(2)	루트 노드는 항상 ⚫️BLACK이다.
(3)	모든 리프(NIL 노드)는 ⚫️BLACK이다.
(4)	🔴RED 노드의 자식은 반드시 ⚫️BLACK이다. (즉, RED가 연속으로 나올 수 없다.)
(5)	임의의 노드에서 리프까지 가는 모든 경로는 동일한 수의 ⚫️BLACK 노드를 지나야 한다. (이 수를 black-height라 한다.)

핵심 연산: 회전(Rotation)

회전은 이진 탐색 트리의 특성(왼쪽 < 부모 < 오른쪽)을 유지하면서 노드들의 부모-자식 관계를 재조정하는 국소적인 연산이다. 포인터 몇 개만 바꾸므로 'O(1)'의 매우 빠른 작업이다.

이름	설명
왼쪽 회전	특정 노드(x)를 기준으로, x의 오른쪽 자식(y)을 위로 올리고 x는 y의 왼쪽 자식이 되도록 내린다.
오른쪽 회전	왼쪽 회전과 대칭. x의 왼쪽 자식(y)을 위로 올리고 x는 y의 오른쪽 자식이 되도록 내린다.

삽입(Insertion) 연산과 속성 복구

1. 기본 삽입: 먼저 일반적인 이진 탐색 트리 규칙에 따라 노드를 삽입한다. 이때 새 노드의 색은 항상 🔴RED로 지정한다.
2. 위반 검사: 만약 삽입된 노드의 부모도 🔴RED라면 '속성 (4) - "RED 노드의 자식은 BLACK"' 를 위반하게 된다. (RED-RED 충돌)
3. 복구 (Fix-up): insert_fixup 함수를 통해 위반된 속성을 복구한다. 복구는 삼촌 노드의 색에 따라 세 가지 경우로 나뉜다.

Case	조건	해결 방법
1	삼촌이 🔴RED	'(색상 변경)' 부모와 삼촌을 ⚫️BLACK으로, 조부모를 🔴RED로 바꾼다. 그 후 조부모를 기준으로 다시 위반 여부를 검사한다.
2	삼촌이 ⚫️BLACK이고, 내가 "안쪽" 자식일 때	'(회전)' 부모를 기준으로 회전하여 Case 3 모양으로 바꾼다.
3	삼촌이 ⚫️BLACK이고, 내가 "바깥쪽" 자식일 때	'(회전 + 색상 변경)' 조부모를 기준으로 회전하고, 부모와 조부모의 색을 바꾼다.

4. 루트 색 고정: 모든 복구 과정이 끝난 후, '속성 (2)'를 만족시키기 위해 루트 노드의 색을 항상 ⚫️BLACK으로 강제한다.

삭제(Deletion) 연산과 속성 복구

1. 기본 삭제: 이진 탐색 트리 규칙에 따라 노드를 삭제한다.
2. 위반 검사:
   • 삭제된 노드가 🔴RED이면 아무 속성도 위반하지 않으므로 작업이 끝난다.
   • 삭제된 노드가 ⚫️BLACK이면, 그 노드를 지나던 경로의 black-height가 1 줄어들어 '속성 (5)'를 위반하게 된다. 이를 "double black" 또는 "extra black" 상태라고 부른다.
3. 복구 (Fix-up): delete_fixup 함수를 통해 위반된 속성을 복구한다. 복구는 형제 노드(w)와 그 자식들의 색에 따라 네 가지 경우로 나뉜다.

Case	조건	해결 방법
1	형제(w)가 🔴RED	형제와 부모의 색을 바꾸고 부모 기준으로 회전한다. 그러면 형제가 ⚫️BLACK인 Case 2, 3, 4 중 하나로 바뀐다.
2	형제(w)와 그 두 자식이 모두 ⚫️BLACK	형제를 🔴RED로 바꾸고, 부족한 black-height를 부모에게 전파하여 부모를 기준으로 다시 복구를 시작한다.
3	형제(w)는 ⚫️BLACK, 안쪽 자식만 🔴RED	형제와 그 안쪽 자식의 색을 바꾸고 형제 기준으로 회전한다. 그러면 Case 4 모양으로 바뀐다.
4	형제(w)는 ⚫️BLACK, 바깥쪽 자식이 🔴RED	부모 기준으로 회전하고 관련된 노드들의 색을 변경하여 black-height 불균형을 완전히 해소하고 종료한다.

기타 속성 위반과 복구

속성	위반 가능성 및 해결
(1) RED 또는 BLACK	새 노드 생성 시 색을 명시적으로 초기화하면 위반되지 않는다.
(2) 루트는 BLACK	삽입/삭제 연산 마지막에 항상 루트의 색을 ⚫️BLACK으로 설정하여 해결한다.
(3) 리프(NIL)는 BLACK	모든 리프가 공유하는 센티널(sentinel) NIL 노드를 처음에 ⚫️BLACK으로 한 번만 초기화해두면 위반되지 않는다.

구현 상세 (Implementation Details)

노드 구조체

• 색깔(color): enum { RED, BLACK }으로 정의. 새 노드는 항상 RED로 삽입.
• 키(key): 노드의 값.
• 포인터(left, right, parent):
  • left, right: 두 자식 노드를 가리킴.
  • parent: 부모 노드를 가리킴. 레드-블랙 트리의 fixup 과정에서 삼촌, 조부모 노드에 O(1) 시간 안에 접근하기 위해 반드시 필요하다. 부모 포인터가 없으면 루트부터 다시 찾아 내려와야 하므로 비효율적이다.

센티널 NIL 노드

• 모든 리프 노드(자식이 없는 경우)와 루트의 부모를 표현하기 위한 공용 노드.
• 프로그램 시작 시 한 번만 생성하며 색은 ⚫️BLACK으로 고정한다. NULL 대신 이 NIL 노드를 사용하면 코드의 예외 처리가 간결해진다.

활용 사례 및 장단점

주요 활용 사례

분야	이유
C++ std::map, std::set	키-값 쌍 또는 원소를 O(log n) 시간 안에 정렬된 상태로 조작하기 위해 사용된다.
Java TreeMap, TreeSet	위 C++의 경우와 동일하다.
Linux CFS (Completely Fair Scheduler)	실행 대기 중인 프로세스들을 '가상 실행 시간' 기준으로 정렬하여, 다음 실행할 프로세스를 O(log n) 안에 효율적으로 찾아낸다.
데이터베이스 인덱스 (메모리 내)	데이터의 삽입/삭제가 빈번하면서도 빠른 범위 검색이 필요한 메모리 기반 데이터베이스의 인덱싱에 적합하다.

장점

• 최악의 경우에도 높이가 2 * log₂(n + 1) 이하로 보장되어 모든 연산이 'O(log n)' 임을 보장한다.
• AVL 트리와 비교했을 때, 삽입/삭제 시 발생하는 회전의 횟수가 더 적어(최대 2~3회) 변경 연산이 더 효율적이다.

단점

• AVL 트리보다 엄격하게 균형을 맞추지 않으므로, 평균적인 트리의 높이는 AVL 트리보다 약간 더 높을 수 있다. 따라서 삽입/삭제보다 탐색 연산이 훨씬 더 빈번한 경우에는 AVL 트리가 조금 더 유리할 수 있다.

핵심 요약

• 블랙 노드의 깊이는 항상 같다 (black-height) → 이 규칙 덕분에 트리가 한쪽으로 심하게 길어지는 것을 막는다.
• 레드 노드는 연속될 수 없다 → 이 규칙은 트리의 높이가 과도하게 늘어나는 것을 제한하는 역할을 한다.
• 문제가 생기면 "회전"과 "색 변경"으로 해결한다 → 이 두 가지 간단한 연산으로 5가지 속성을 복구하며 트리의 균형을 유지한다.
• 결론적으로 레드-블랙 트리는 "완벽한 균형"을 추구하기보다 "적당히 균형 잡힌 상태"를 빠르고 효율적으로 유지하는 실용적인 자료구조다.