Red-Black 트리

1. 레드 블랙 트리

레드-블랙 트리(Red-Black Tree, RBT)는 컴퓨터 과학에서 가장 널리 사용되는 자가 균형 이진 탐색 트리(Self-Balancing Binary Search Tree) 중 하나다. 일반적인 이진 탐색 트리(BST)가 데이터의 삽입 순서에 따라 최악의 경우 O(n)의 성능을 보이는 치명적 단점을 갖는 반면, 레드-블랙 트리는 트리 스스로 구조를 재조정하여 삽입, 삭제, 탐색 연산에 대해 항상 O(log n)의 시간 복잡도를 보장한다.

2. 이론

2.1. 이진 탐색 트리와 균형의 문제

이진 탐색 트리는 '왼쪽 자식 < 부모 < 오른쪽 자식' 이라는 속성을 만족하는 트리다. 이 속성 덕분에 평균적으로 O(log n)의 빠른 탐색이 가능하지만, 데이터가 정렬된 순서로 삽입되면 한쪽으로 치우쳐진(skewed) 연결 리스트 형태가 되어 성능이 O(n)으로 저하된다. 이 문제를 해결하기 위해 '균형'을 유지하는 개념이 등장했으며, 레드-블랙 트리는 그 대표적인 해법이다.

2.2. 레드-블랙 트리의 5가지 규칙

레드-블랙 트리는 BST의 속성을 모두 가지며, 추가적으로 다음 5가지 규칙을 반드시 만족해야 한다.

1. 색상: 모든 노드는 '레드(Red)' 혹은 '블랙(Black)' 중 하나의 색을 갖는다.
2. 루트: 루트 노드는 항상 '블랙'이다.
3. 리프: 모든 리프(leaf) 노드는 '블랙'이다. (여기서 리프는 실제 데이터가 없는 NIL 노드를 의미하며, 구현 시 모든 외부 노드를 가리키는 단일 센티널(sentinel) 노드로 표현한다.)
4. 레드: '레드' 노드의 자식은 반드시 '블랙'이다. (즉, 레드 노드가 연속으로 두 번 나타날 수 없다.)
5. 블랙-높이: 임의의 노드 x로부터 그 자손인 리프 노드까지 내려가는 모든 단순 경로에는 동일한 개수의 '블랙' 노드가 존재한다. 이 개수를 노드 x의 블랙-높이(black-height, bh(x)) 라고 한다.

2.3. O(log n) 높이의 수학적 증명

4번과 5번은 트리의 높이가 n개의 노드에 대해 O(log n)임을 보장하는 핵심이다.

보조정리: 루트가 x인 임의의 서브트리는 2^(bh(x)) - 1개 이상의 내부 노드를 갖는다.

• 증명 (수학적 귀납법):
  • bh(x) = 0일 때, x는 리프(NIL)이므로 내부 노드는 0개다. 2^0 - 1 = 0이므로 성립.
  • bh(x) > 0일 때, x의 자식 노드들의 블랙-높이는 bh(x) 또는 bh(x)-1이다. (자식이 레드면 bh(x), 블랙이면 bh(x)-1). 따라서 각 자식 서브트리는 최소 2^(bh(x)-1) - 1개의 내부 노드를 갖는다.
  • 따라서 x를 루트로 하는 서브트리의 내부 노드 수는 (2^(bh(x)-1) - 1) + (2^(bh(x)-1) - 1) + 1(x 자신) = 2 * (2^(bh(x)-1)) - 1 = 2^(bh(x)) - 1 이상이다.

정리: n개의 내부 노드를 갖는 레드-블랙 트리의 높이 h는 2 * log₂(n + 1) 이하이다.

• 증명:
  • 루트에서 가장 먼 리프까지의 경로에서, 레드 공리(4번)에 의해 레드 노드는 연속될 수 없으므로, 노드의 최대 절반만이 레드일 수 있다. 즉, 블랙 노드는 최소 h/2개 존재한다.
  • 따라서 루트의 블랙-높이는 bh(root) >= h/2 이다.
  • 위 보조정리에 의해, n >= 2^(bh(root)) - 1 이다.
  • n >= 2^(h/2) - 1 => n + 1 >= 2^(h/2) => log₂(n + 1) >= h/2
  • 결론적으로, h <= 2 * log₂(n + 1) 이므로 높이는 O(log n)임이 증명된다.

3. 내부 구조 및 구현 방식

3.1. 노드 구조와 센티널 노드

enum Color { RED, BLACK };

struct Node {
    int key;
    Color color;
    Node *parent, *left, *right;
};

• parent 포인터: 부모 노드를 가리키는 포인터는 재조정 과정(특히 회전)에서 필수적이다.
• 센티널 노드 (T.nil): 모든 리프 노드(외부 노드)와 루트의 부모를 표현하기 위해 단 하나의 특수한 노드(센티널)를 사용한다. 이 노드의 색상은 항상 BLACK이다. 센티널을 사용하면 경계 조건(boundary condition) 처리가 매우 깔끔해진다.

3.2. 회전 (Rotation)

회전은 BST 속성을 유지하면서 트리 구조를 변경하는 O(1) 연산이다.

• Left-Rotate(T, x): x를 중심으로 x와 오른쪽 자식 y를 회전시킨다. y가 x의 자리로 올라오고, x는 y의 왼쪽 자식이 된다. y의 원래 왼쪽 자식은 x의 오른쪽 자식이 된다.
• Right-Rotate(T, y): Left-Rotate의 반대 연산.

3.3. 삽입 (Insertion)

1. BST 삽입: 새로운 노드 z를 일반적인 BST처럼 삽입하고, 색상을 RED로 지정한다. (만약 BLACK으로 삽입하면 블랙-높이 공리(5)가 거의 항상 깨지기 때문).
2. 재조정 (Fixup): z를 RED로 칠하면 레드 공리(4)가 위반될 수 있다 (부모 p가 RED일 경우). RB-Insert-Fixup 함수를 통해 이를 해결한다.
   • z의 삼촌(uncle) 노드의 색상에 따라 3가지 경우로 나뉜다.
   • Case 1: 삼촌이 RED인 경우
     • 부모와 삼촌을 BLACK으로, 조부모를 RED로 바꾼다.
     • 이제 문제는 조부모에서 발생할 수 있으므로, z를 조부모로 설정하고 루프를 계속한다. 이 과정은 루트까지 전파될 수 있다.
   • Case 2: 삼촌이 BLACK이고, z가 '안쪽' 자식인 경우 (꺾인 형태)
     • 부모를 기준으로 회전하여 Case 3의 '직선' 형태로 만든다.
   • Case 3: 삼촌이 BLACK이고, z가 '바깥쪽' 자식인 경우 (직선 형태)
     • 부모를 BLACK, 조부모를 RED로 바꾸고, 조부모를 기준으로 회전한다.
     • 이 연산으로 레드-블랙 트리 속성이 모두 만족되므로 루프가 종료된다.

삽입 시 회전은 최대 2번만 발생한다.

3.4. 삭제 (Deletion)

삭제는 레드-블랙 트리에서 가장 복잡한 연산이다.

1. 삭제할 노드를 찾고, BST 규칙에 따라 후계자(successor)로 대체한다.
2. 실제로 트리에서 제거되는 노드 y의 색상이 RED라면, 어떤 규칙도 위반하지 않으므로 모든 것이 간단히 끝난다.
3. y의 색상이 BLACK이라면, y가 있던 경로의 블랙-높이가 1 감소하여 블랙-높이 공리(5)가 깨진다. 이 경로에 '가상의' extra black을 부여했다고 생각하고, 이 extra black을 트리 위쪽으로 이동시키거나 흡수시켜 해결해야 한다. (RB-Delete-Fixup)
   • x의 형제(sibling) w의 색상과, 그 형제의 자식들의 색상에 따라 4가지 복잡한 경우로 나뉜다.
   • 각 경우는 색상 변경과 회전을 조합하여 extra black을 해결한다. 삭제 시 회전은 최대 3번 발생한다.

4. 심층 비교 분석

4.1. Red-Black Tree vs. AVL Tree

구분	Red-Black Tree	AVL Tree
균형 조건	5가지 색상 공리 (느슨함)	노드의 좌우 서브트리 높이 차가 1 이하 (엄격함)
최대 높이	~2 * log₂(n)	~1.44 * log₂(n)
탐색 성능	매우 좋음 (O(log n))	이론적으로 더 좋음 (트리가 더 빽빽함)
삽입/삭제	더 빠름. 삽입 시 최대 2회, 삭제 시 최대 3회 회전.	더 느림. 재조정이 루트까지 전파될 수 있어 O(log n) 회전 가능.
메모리	노드당 1비트(색상) 추가 공간 필요	노드당 log(높이) 비트(balance factor) 추가 공간 필요

결론: 탐색이 압도적으로 많고 데이터 변경이 드물다면 AVL 트리, 삽입/삭제가 빈번한 동적 환경이라면 레드-블랙 트리가 더 효율적이다. C++ std::map, Java TreeMap 등이 RBT를 선택한 이유다.

4.2. Red-Black Tree vs. B-Tree

구분	Red-Black Tree	B-Tree / B+ Tree
기본 구조	이진 트리	다진(multi-way) 트리 (자식이 2개 이상)
주 사용처	메인 메모리(In-memory) 자료구조	디스크(On-disk) 자료구조 (데이터베이스, 파일 시스템)
노드당 키	1개	여러 개 (m개)
성능 목표	CPU 연산 최소화	디스크 I/O 최소화
캐시 효율성	상대적으로 낮음 (포인터 추적이 많음)	매우 높음. 한 노드(디스크 블록)에 많은 키가 있어 지역성(locality)이 좋음.

결론: B-트리는 노드의 크기를 디스크 블록 크기에 맞춰, 한 번의 I/O로 최대한 많은 데이터를 메모리에 올리는 데 최적화되어 있다. RBT는 포인터 기반으로 메모리 내에서 유연하게 동작하는 데 최적화되어 있다. 둘은 경쟁 관계가 아닌, 서로 다른 환경을 위한 자료구조이다.

5. 소프트웨어 계층 구조에서의 동작

std::map<int, string> my_map; my_map[10] = "hello"; 코드가 실행될 때의 계층적 흐름이다.

1. 사용자 코드 계층: std::map의 operator[]가 호출된다.
2. C++ 표준 라이브러리 계층:
   • std::map은 내부적으로 레드-블랙 트리(_Rb_tree)를 사용한다.
   • operator[]는 먼저 키 10을 find한다.
   • 키가 없으면, insert 연산을 수행한다. insert는 _Rb_tree의 삽입 메서드를 호출한다.
3. RBT 구현 계층 (_Rb_tree):
   • 노드 할당: new _Rb_tree_node<...>를 통해 힙에 새 노드를 할당한다.
   • BST 삽입: 일반적인 BST 규칙에 따라 새 노드를 트리에 연결한다.
   • 재조정: _Rb_tree_rebalance_for_insert와 같은 내부 함수를 호출하여, 위에서 설명한 Case 1, 2, 3에 따라 색상 변경과 회전을 수행하여 RBT 속성을 복원한다.
4. 메모리 관리자 계층:
   • 노드 할당(new)은 C++ 메모리 관리자를 통해 malloc을 호출하고, 이는 다시 커널의 brk나 mmap을 호출하여 메모리를 얻는다. (자세한 내용은 malloc/new 문서 참조)
5. 하드웨어 계층 (CPU & Memory):
   • 트리 순회(node->left, node->parent 등)는 포인터 추적을 유발한다. 만약 다음 노드가 CPU 캐시에 없다면 캐시 미스(Cache Miss)가 발생하여 메인 메모리 접근이 필요해지고, 이는 상당한 지연을 초래한다.
   • RBT의 실제 성능은 이론적 복잡도뿐만 아니라, 이러한 메모리 접근 패턴과 캐시 효율성에 크게 좌우된다.

6. 요약

 레드-블랙 트리는 한마디로 'O(log n) 성능을 보장하는 똑똑한 자가 균형 이진 탐색 트리' 입니다. 일반 이진 탐색 트리는 데이터가 순서대로 들어오면 연결 리스트처럼 일자로 늘어져서 성능이 O(n)까지 떨어질 수 있는데, 레드-블랙 트리는 이런 상황을 막기 위해 스스로 균형을 잡습니다.

 균형을 잡는 핵심 아이디어는 모든 노드에 '레드' 또는 '블랙' 색상을 칠하고, 5가지의 간단한 규칙을 지키도록 하는 겁니다. 가장 중요한 규칙은 '어떤 노드에서부터 잎 노드까지 가는 모든 경로의 블랙 노드 개수는 같다'는 '블랙-높이' 규칙입니다. 이 규칙들 덕분에 트리의 높이가 항상 log n에 비례하도록 보장됩니다.

 내부적으로는 데이터를 삽입할 때 일단 '레드' 노드로 추가한 뒤, 규칙에 위배되는 상황이 생기면 '색상 변경'이나 '회전' 이라는 작업을 통해 균형을 맞춥니다. 회전은 O(1)의 매우 빠른 연산으로, 트리의 구조를 살짝 비틀어서 BST 속성은 유지하면서 높이 균형을 맞추는 기술입니다. 삭제는 경우가 더 복잡하지만 비슷한 원리로 동작합니다.

 AVL 트리와 비교하면, AVL 트리는 더 엄격하게 균형을 맞춰서 탐색 성능은 약간 더 좋지만, 그만큼 삽입/삭제할 때 회전이 더 많이 일어나서 느립니다. 반면 레드-블랙 트리는 균형을 좀 더 느슨하게 관리해서 삽입/삭제가 더 빠릅니다. 그래서 C++의 std::map이나 std::set, 자바의 TreeMap처럼 데이터 변경이 잦은 곳에서 널리 쓰입니다. 반면 B-트리는 디스크 기반의 데이터베이스 인덱스에 사용되는데, 노드 하나에 많은 데이터를 저장해서 디스크 I/O를 줄이는 데 최적화되어 있다는 점에서 레드-블랙 트리와 목적이 다릅니다.

 소프트웨어 계층에서 보면, 우리가 std::map을 쓸 때 내부적으로는 이 레드-블랙 트리 구현체가 동작합니다. map에 원소를 추가하면, 힙 메모리에서 노드를 할당하고(이때 new->malloc->커널 과정이 일어나겠죠), 트리에 연결한 뒤, 색상 규칙에 따라 균형을 맞추는 작업이 일어납니다.