Red-Black Tree: 리눅스 커널과 Java HashMap의 심장 (자가 균형 트리 완벽 해부)

프롤로그 - 알고리즘 수업에서 만난 빨강-검정의 혼돈

대학교에서 자료구조 수업을 듣던 어느 날, 교수님이 칠판에 빨간색과 검정색 분필로 트리를 그리기 시작했습니다. 노드마다 색깔을 칠하면서 "이게 Red-Black Tree입니다"라고 말씀하셨는데, 솔직히 처음엔 완전히 혼란스러웠습니다. 왜 굳이 색깔을 칠하는 거지? 이진 탐색 트리(BST)만으로는 부족한가? 그리고 왜 빨강-검정인가? 파랑-노랑은 안 되나?

그때는 그냥 암기 과목이라고 생각했습니다. "5가지 규칙을 외워라", "회전은 이렇게 한다", "삽입은 이렇게 한다"... 공부하고 나서는 깔끔하게 잊어버렸습니다. 그런데 몇 년 후 창업을 하고 직접 개발을 하면서, 이 개념이 갑자기 다시 튀어나왔습니다. Java HashMap 내부 구현을 보다가 TreeNode라는 클래스를 발견했고, 거기서 boolean red라는 필드를 봤습니다. "아, 이게 그때 배웠던 Red-Black Tree구나!"

그제야 이해했습니다. 이건 단순한 교과서 문제가 아니라, 실제로 리눅스 커널과 Java처럼 전 세계 수십억 대의 컴퓨터에서 돌아가는 시스템의 핵심 자료구조였던 겁니다. 그래서 다시 공부를 시작했고, 이번엔 "왜 이게 필요한가"부터 시작해서 차근차근 정리해본다는 마음으로 접근했습니다.

문제의 시작 - 1, 2, 3, 4, 5를 트리에 넣으면?

이진 탐색 트리(Binary Search Tree, BST)는 정말 멋진 자료구조입니다. 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큰 규칙 하나만 지키면, 데이터를 찾는 데 평균 $O(\log N)$의 시간이 걸립니다. 100만 개의 데이터에서 찾는 데 약 20번의 비교면 충분합니다. 엄청난 효율입니다.

그런데 문제는 "평균"이라는 단어입니다. 만약 데이터가 1, 2, 3, 4, 5 순서로 들어온다면 어떻게 될까요? BST의 규칙에 따라 1이 루트가 되고, 2는 1의 오른쪽 자식이 되고, 3은 2의 오른쪽 자식이 됩니다. 결국 트리는 오른쪽으로만 길게 늘어난 링크드 리스트가 되어버립니다.

이런 상황을 편향된 트리(Skewed Tree)라고 부릅니다. 이 상태에서 5를 찾으려면 1, 2, 3, 4를 다 거쳐야 합니다. $O(\log N)$이 아니라 $O(N)$입니다. 100만 개의 데이터에서 하나를 찾는 데 최악의 경우 100만 번의 비교가 필요합니다. 이건 그냥 배열을 순차 탐색하는 것과 다를 바 없습니다.

저는 이 문제를 처음 봤을 때 "그럼 데이터를 섞어서 넣으면 되잖아?"라고 생각했습니다. 하지만 현실은 그렇게 호락호락하지 않습니다. 사용자가 주문번호를 순서대로 입력한다거나, 타임스탬프 순서로 로그가 쌓인다거나, 자동 증가하는 ID 값이 들어온다거나... 실제 시스템에서는 정렬된 순서로 데이터가 들어오는 경우가 생각보다 많습니다.

그래서 필요한 게 자가 균형 이진 탐색 트리(Self-Balancing BST)입니다. 어떤 순서로 데이터가 들어오든, 트리가 스스로 균형을 맞춰서 높이를 $\log N$으로 유지하는 자료구조입니다. 그중 가장 유명하고 실제로 많이 쓰이는 게 바로 Red-Black Tree입니다.

"와, 색깔로 균형을 맞춘다고?" - 첫 번째 오해

처음엔 색깔이 단순히 시각적 표시용인 줄 알았습니다. 교수님이 칠판에 빨강과 검정으로 구분해서 그리는 게 그냥 설명을 위한 거라고 생각했습니다. 하지만 천천히 이해하면서 깨달았습니다. 색깔이 바로 균형의 핵심이었습니다.

Red-Black Tree는 각 노드에 "색깔"이라는 메타데이터를 하나 더 붙입니다. 빨강(Red) 아니면 검정(Black). 딱 두 가지입니다. 그리고 이 색깔에 대한 5가지 절대 규칙을 정의합니다. 이 규칙들이 지켜지면, 트리의 높이가 자동으로 $\log N$에 가깝게 유지됩니다.

저는 이걸 "신호등"에 비유해서 받아들였습니다. 도로에 신호등이 있으면 차들이 질서 있게 흐르잖아요? 마찬가지로 트리에 색깔 규칙이 있으면, 노드들이 "질서 있게" 배치됩니다. 한쪽으로 너무 쏠리지 않고, 적당히 퍼져서 균형을 이룹니다.

그럼 이제 그 5가지 규칙이 뭔지 정리해봅니다.

5가지 절대 규칙 - 이게 지켜지면 균형이 보장된다

Red-Black Tree의 정의는 간단합니다. 아래 5가지 규칙을 모두 만족하는 이진 탐색 트리입니다.

규칙 1 - 모든 노드는 Red 또는 Black이다

이건 당연합니다. 색깔은 딱 두 가지입니다. 노란색이나 파란색은 없습니다.

규칙 2 - 루트 노드는 무조건 Black이다

트리의 최상단 노드는 항상 검정색입니다. 이유는 나중에 설명하겠지만, 삽입/삭제 알고리즘을 단순화하기 위한 약속입니다.

규칙 3 - 모든 말단 노드(NIL)는 Black이다

트리의 끝을 나타내는 NULL 포인터를 NIL 노드라고 부릅니다. 이 NIL 노드들은 모두 검정색으로 취급합니다. 실제 메모리를 차지하지는 않지만, 개념적으로 존재한다고 생각하면 됩니다.

규칙 4 - Red 노드의 자식은 무조건 Black이다

이게 핵심입니다. 빨강 밑에 빨강이 올 수 없습니다. 즉, Red 노드가 연속으로 나타날 수 없습니다. 이 규칙을 위반한 상황을 Double Red라고 부릅니다.

규칙 5 - 임의의 노드에서 리프 노드(NIL)까지 가는 모든 경로에는 동일한 개수의 Black 노드가 있다

이게 두 번째 핵심입니다. 어떤 노드에서 출발하든, 아래로 내려가면서 만나는 검정색 노드의 개수는 항상 같아야 합니다. 이 값을 Black Height라고 부릅니다.

이 5가지 규칙을 처음 봤을 땐 "이게 왜 균형을 보장하지?"라고 의아했습니다. 그런데 수학적으로 증명이 가능합니다. 규칙 4(No Double Red)와 규칙 5(Black Height 동일) 때문에, 가장 긴 경로가 가장 짧은 경로의 2배를 넘을 수 없습니다.

예를 들어볼까요? 가장 짧은 경로는 모두 검정색 노드로만 이루어진 경로입니다. Black Height가 3이라면, 이 경로의 길이는 3입니다. 그럼 가장 긴 경로는? 빨강과 검정이 번갈아 나타나는 경로입니다. Black Height는 여전히 3이어야 하므로, 빨강 3개가 사이사이에 끼어들어서 총 길이는 6입니다. 정확히 2배입니다.

결국 이거였습니다. Red-Black Tree는 "완벽한 균형"을 추구하지 않습니다. 대신 "적당한 균형"을 보장합니다. 가장 긴 경로가 가장 짧은 경로의 2배 이하라는 것만 보장하면, 탐색 시간은 여전히 $O(\log N)$입니다. 100만 개의 데이터에서도 최악의 경우 40번 정도의 비교면 충분합니다.

그래서 AVL Tree는 뭐가 다른데?

균형 트리를 공부하다 보면 AVL Tree도 자주 나옵니다. AVL도 자가 균형 트리인데, Red-Black Tree와 뭐가 다를까요? 저는 이 두 개를 비교하면서 Red-Black Tree의 장점을 확실히 이해했습니다.

AVL Tree는 엄격한 균형을 유지합니다. 모든 노드에서, 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1을 넘으면 안 됩니다. 조금이라도 차이가 나면 즉시 회전(Rotation) 연산을 해서 균형을 맞춥니다.

반면 Red-Black Tree는 느슨한 균형을 유지합니다. 높이 차이가 2배까지는 괜찮습니다. 그래서 삽입이나 삭제를 할 때 회전 연산이 AVL보다 적게 필요합니다.

이걸 비유하자면, AVL은 "결벽증 있는 사람"이고, Red-Black은 "실용주의자"입니다. AVL은 "책이 1cm라도 삐뚤어지면 바로 고친다"는 스타일이고, Red-Black은 "어차피 찾는 데 큰 차이 없으면 그냥 둔다"는 스타일입니다.

구체적으로 비교하면:

• 조회(Search) 성능: AVL이 약간 더 빠릅니다. 트리가 더 균형 잡혀 있으니까요.
• 삽입/삭제(Insert/Delete) 성능: Red-Black이 훨씬 빠릅니다. 회전 연산이 적으니까요.
• 메모리 사용량: 비슷합니다. 둘 다 노드당 추가 정보(AVL은 높이, RB는 색깔)를 저장합니다.

그럼 어떤 걸 써야 할까요? 정답은 "상황에 따라 다르다"입니다. 만약 데이터가 한 번 저장되면 거의 변경되지 않고, 조회만 계속 일어난다면 AVL이 좋습니다. 하지만 삽입과 삭제가 빈번하게 일어난다면 Red-Black이 훨씬 유리합니다.

실제로는 어떨까요? 리눅스 커널, Java HashMap, C++ STL map 같은 핵심 시스템들은 모두 Red-Black Tree를 선택했습니다. 왜냐하면 이런 시스템들은 데이터가 계속 추가되고 삭제되는 동적인 환경이기 때문입니다. 조회 속도를 조금 희생하더라도, 삽입/삭제 속도가 빠른 게 전체 시스템 성능에 더 유리합니다.

저는 이걸 받아들였습니다. "완벽한 균형"보다 "실용적인 균형"이 더 중요하다는 걸 말입니다.

균형이 깨지면 어떻게 고치나? - Rotation과 Recoloring

자, 이제 핵심 질문입니다. 새로운 노드를 삽입했는데 규칙이 깨진다면 어떻게 고칠까요?

새 노드를 삽입할 때는 항상 Red 색깔로 삽입합니다. 왜냐하면 Black으로 삽입하면 규칙 5(Black Height 동일)가 바로 깨지기 때문입니다. 그런데 Red로 삽입하면 규칙 4(No Double Red)가 깨질 수 있습니다. 만약 부모 노드가 Red라면, Red 밑에 Red가 달리는 상황이 발생합니다.

이때 해결책은 두 가지입니다. Restructuring(회전)과 Recoloring(색칠)입니다. 어느 쪽을 선택할지는 삼촌 노드(Uncle Node)의 색깔에 달려 있습니다.

삼촌 노드가 뭔가요? 부모의 형제 노드입니다. 내가 "손자"라면, 아버지의 형제가 삼촌이죠. 트리도 마찬가지입니다.

Case 1: 삼촌이 Black이면 Restructuring (회전)

삼촌 노드가 검정색(또는 NIL)이라면, Restructuring을 합니다.

1. 나(새 노드), 부모, 할아버지를 오름차순으로 정렬합니다.
2. 가운데 값을 새로운 부모로 만들고, 나머지 둘을 자식으로 만듭니다.
3. 새로운 부모는 Black, 두 자식은 Red로 칠합니다.

이 과정을 회전(Rotation)이라고 부릅니다. 왼쪽 회전(Left Rotation) 또는 오른쪽 회전(Right Rotation)을 통해 트리의 구조를 바꿉니다. 회전 연산은 $O(1)$입니다. 포인터 몇 개만 바꾸면 되니까요.

Case 2: 삼촌이 Red면 Recoloring (색칠)

삼촌 노드가 빨간색이라면, Recoloring을 합니다.

1. 부모와 삼촌을 Black으로 칠합니다.
2. 할아버지를 Red로 칠합니다.
3. 할아버지가 루트가 아니라면, 할아버지를 새로운 "문제 노드"로 보고 다시 검사합니다.

이 과정은 재귀적으로 올라갈 수 있습니다. 최악의 경우 루트까지 올라갑니다. 하지만 시간 복잡도는 여전히 $O(\log N)$입니다.

저는 이 과정을 처음 봤을 때 "왜 이렇게 복잡하게 만들었지?"라고 생각했습니다. 하지만 직접 손으로 그려보니까 이해가 됐습니다. 이 두 가지 경우 분류가, 규칙 5(Black Height 동일)을 유지하면서 규칙 4(No Double Red)를 해결하는 가장 단순한 방법이었습니다.

삽입 예제 - 10, 20, 30을 차례로 넣으면?

이론만 봐서는 와닿지 않아서, 직접 예제를 그려봤습니다. 10, 20, 30을 순서대로 삽입하는 과정입니다.

Step 1: 10 삽입

• 10이 루트가 됩니다.
• 규칙 2(루트는 Black)에 따라 10을 Black으로 칠합니다.

     10(B)

Step 2: 20 삽입

• 20은 10의 오른쪽 자식이 됩니다.
• 새 노드는 Red로 삽입합니다.
• 부모(10)가 Black이므로 규칙 위반 없습니다.

     10(B)
        \
        20(R)

Step 3: 30 삽입

• 30은 20의 오른쪽 자식이 됩니다.
• 새 노드는 Red로 삽입합니다.
• 문제 발생! 20(R) 밑에 30(R)이 달렸습니다. Double Red!

     10(B)
        \
        20(R)
           \
           30(R)  <- Double Red!

Step 4: 문제 해결

• 삼촌 노드를 확인합니다. 20의 삼촌은 10의 왼쪽 자식인데, 없습니다(NIL, 즉 Black).
• 삼촌이 Black이므로 Restructuring을 합니다.
• 10, 20, 30을 오름차순 정렬하면 10 < 20 < 30입니다.
• 가운데 값인 20을 새 루트로 만들고, 10과 30을 자식으로 만듭니다.
• 20은 Black, 10과 30은 Red로 칠합니다.

       20(B)
      /    \
   10(R)  30(R)

완벽한 균형입니다! 일반 BST였다면 10 -> 20 -> 30으로 일직선이 됐을 텐데, Red-Black Tree는 자동으로 균형을 맞췄습니다.

이 예제를 직접 그려보면서 정리해봤습니다. "아, 이래서 회전이 필요하구나. 색깔 규칙이 회전 타이밍을 결정하는구나."

삭제는 더 복잡하다 - 간략히만 정리

삽입도 복잡한데, 삭제는 더 복잡합니다. 솔직히 삭제 알고리즘은 처음 봤을 때 완전히 포기했습니다. 경우의 수가 너무 많았습니다.

간단히 요약하면:

1. 일반 BST처럼 노드를 삭제합니다.
2. 삭제된 노드가 Black이었다면, Black Height가 깨집니다.
3. 이를 고치기 위해 형제 노드의 색깔과 자식 색깔을 보고 여러 경우로 분류합니다.
4. 회전과 색칠을 통해 규칙을 복구합니다.

삭제는 삽입보다 경우의 수가 많지만, 시간 복잡도는 역시 $O(\log N)$입니다. 실제 구현은 리눅스 커널 코드나 Java 소스코드를 보면 나오는데, 수백 줄에 달합니다.

저는 삭제 알고리즘을 완벽하게 이해하려고 며칠을 씨름했지만, 결국 "개념만 알고 넘어가자"고 결정했습니다. 실제로 직접 Red-Black Tree를 구현할 일은 거의 없으니까요. 대신 "왜 이게 필요한가"와 "어디에 쓰이는가"를 이해하는 데 집중했습니다.

실제 사용 사례 1 - Java HashMap의 비밀

Java를 쓰는 개발자라면 HashMap을 모르는 사람은 없을 겁니다. Key-Value 쌍을 저장하는 가장 기본적인 자료구조죠. 평균 $O(1)$에 데이터를 찾을 수 있어서 엄청나게 빠릅니다.

그런데 HashMap의 내부를 들여다보면 Red-Black Tree가 숨어 있습니다. 정확히는 Java 8부터입니다.

HashMap은 내부적으로 배열을 사용합니다. Key의 해시값을 배열 인덱스로 변환해서 저장합니다. 그런데 문제는 해시 충돌(Hash Collision)입니다. 서로 다른 Key가 같은 인덱스로 매핑될 수 있습니다.

Java 7까지는 충돌이 발생하면 Linked List로 연결했습니다. 같은 인덱스에 여러 개의 데이터가 들어오면, 리스트로 이어서 저장합니다. 하지만 이 방식은 최악의 경우 $O(N)$이 됩니다. 만약 악의적인 공격자가 의도적으로 같은 해시값을 가지는 Key들을 계속 넣으면, 하나의 버킷이 엄청나게 길어지고, 서버가 느려집니다.

Java 8은 이 문제를 해결했습니다. 한 버킷에 데이터가 8개 이상 쌓이면, Linked List를 Red-Black Tree로 변환합니다. 이를 Treeify라고 부릅니다.

실제 코드를 봅시다:

// Java 8 HashMap 소스코드 (simplified)
static final int TREEIFY_THRESHOLD = 8;

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;
    boolean red;  // Red-Black Tree의 색깔!

    // rotateLeft, rotateRight, balanceInsertion, balanceDeletion 등의 메서드
}

핵심은 boolean red 필드입니다. 이게 바로 Red-Black Tree의 색깔 정보입니다. 그리고 rotateLeft, rotateRight 같은 메서드들이 회전 연산을 구현합니다.

이 변화로 인해, 해시 충돌이 발생해도 탐색 시간은 $O(\log N)$으로 보장됩니다. 악의적인 공격에도 방어할 수 있게 된 겁니다.

저는 이 코드를 보면서 "아, 이래서 Red-Black Tree를 배운 거구나"라고 받아들였습니다. 단순한 이론이 아니라, 실제로 수십억 대의 서버에서 돌아가는 코드였습니다.

실제 사용 사례 2 - Linux CFS 스케줄러

리눅스를 쓰는 사람이라면 CFS(Completely Fair Scheduler)를 한 번쯤 들어봤을 겁니다. 리눅스 커널 2.6.23부터 기본 프로세스 스케줄러로 채택된 알고리즘입니다.

CFS의 목표는 간단합니다. "모든 프로세스에게 공평하게 CPU 시간을 주자." 그래서 각 프로세스의 실행 시간(vruntime, virtual runtime)을 추적합니다. CPU를 덜 쓴 프로세스에게 우선권을 주는 방식입니다.

문제는 이걸 어떻게 구현하느냐입니다. 수백 개의 프로세스 중에서 "vruntime이 가장 작은 프로세스"를 빠르게 찾아야 합니다. 그리고 프로세스가 실행되고 나면 vruntime이 증가하므로, 트리에서 제거하고 다시 삽입해야 합니다.

리눅스는 이를 Red-Black Tree로 해결했습니다. vruntime을 Key로 하는 RB Tree를 만들고, 가장 왼쪽 노드(최솟값)를 캐싱합니다.

• 다음 실행할 프로세스 찾기: 트리의 가장 왼쪽 노드를 반환. $O(1)$ (캐싱되어 있으므로).
• 프로세스 삽입/삭제: RB Tree의 삽입/삭제 연산. $O(\log N)$.
• 범위 검색: 특정 vruntime 범위의 프로세스들을 순회. $O(K + \log N)$ (K는 결과 개수).

리눅스 커널 코드를 보면:

// kernel/sched/fair.c (simplified)
struct cfs_rq {
    struct rb_root_cached tasks_timeline;  // Red-Black Tree
    struct rb_node *rb_leftmost;           // 가장 왼쪽 노드 (캐시)
};

static void enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags) {
    // ...
    __enqueue_entity(cfs_rq, se);  // RB Tree에 삽입
}

static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se) {
    struct rb_node **link = &cfs_rq->tasks_timeline.rb_root.rb_node;
    struct rb_node *parent = NULL;
    struct sched_entity *entry;
    bool leftmost = true;

    while (*link) {
        parent = *link;
        entry = rb_entry(parent, struct sched_entity, run_node);
        if (entity_before(se, entry)) {
            link = &parent->rb_left;
        } else {
            link = &parent->rb_right;
            leftmost = false;
        }
    }

    rb_link_node(&se->run_node, parent, link);
    rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline.rb_root);
    // ...
}

rb_insert_color 함수가 바로 Red-Black Tree의 삽입 후 색칠 및 회전 연산을 처리하는 함수입니다.

CFS는 왜 RB Tree를 선택했을까요? 힙(Heap)을 쓸 수도 있었을 텐데요. 이유는 범위 검색 때문입니다. RB Tree는 정렬된 상태를 유지하므로, 특정 vruntime 범위의 프로세스들을 순회하기 쉽습니다. 또한 삽입/삭제가 빈번한 환경에서 AVL보다 빠르기 때문입니다.

저는 이 사례를 보면서 "아, 이래서 운영체제 수업에서 Red-Black Tree를 강조했구나"라고 이해했습니다.

Red-Black Tree vs Hash Table - 왜 해시를 안 쓰나?

여기서 의문이 생깁니다. "해시 테이블이 평균 $O(1)$인데, 왜 굳이 $O(\log N)$인 RB Tree를 쓰나요?"

좋은 질문입니다. 저도 똑같이 생각했습니다. HashMap이 있는데 왜 TreeMap을 쓰지? 그런데 실제로 써보니까 답이 나왔습니다.

Hash Table의 한계

1. 범위 검색 불가: "ID가 100~200인 사용자"를 찾으려면? Hash Table에서는 전체를 순회해야 합니다. $O(N)$.
2. 정렬 불가: 데이터를 정렬된 순서로 순회할 수 없습니다.
3. 최악의 경우 $O(N)$: 해시 충돌이 심하면 느려집니다.
4. 메모리 낭비: 충돌을 줄이려면 배열 크기를 크게 잡아야 합니다. Load Factor가 낮아지면 공간 낭비가 심합니다.

Red-Black Tree의 장점

1. 범위 검색 가능: "ID가 100~200인 사용자"를 $O(K + \log N)$에 찾을 수 있습니다 (K는 결과 개수).
2. 정렬 보장: In-order traversal로 정렬된 순서로 순회 가능.
3. 안정적인 성능: 항상 $O(\log N)$ 보장. 최악의 경우가 없습니다.
4. 메모리 효율: 노드당 추가 메모리는 색깔(1 bit) + 포인터 2개뿐입니다.

결국 선택의 기준은 "무엇을 자주 하는가"입니다.

• Key로 하나만 찾는다 → Hash Table
• 범위 검색이나 정렬된 순회가 필요하다 → Red-Black Tree

Java에서도 이 차이를 반영해서, HashMap과 TreeMap을 둘 다 제공합니다. 저는 이제 상황에 맞게 선택할 수 있게 됐습니다.

Red-Black Tree와 2-3-4 Tree의 관계

Red-Black Tree를 더 깊이 이해하려면, 2-3-4 Tree와의 관계를 알아야 합니다. 사실 Red-Black Tree는 2-3-4 Tree를 이진 트리로 표현한 것입니다.

2-3-4 Tree는 B-Tree의 일종입니다. 하나의 노드에 최대 3개의 Key를 담을 수 있고, 최대 4개의 자식을 가질 수 있습니다. 이 트리도 자가 균형 트리입니다.

Red-Black Tree의 색깔 규칙을 2-3-4 Tree로 변환하면:

• Black 노드: 2-3-4 Tree의 실제 노드.
• Red 노드: 부모 Black 노드와 합쳐서 하나의 큰 노드로 봅니다.

예를 들어:

    10(B)
   /    \
5(R)    15(R)

이건 2-3-4 Tree로 보면 [5, 10, 15]라는 하나의 3-노드입니다.

이 관계를 알고 나니까, 왜 Red-Black Tree의 규칙이 그렇게 정의됐는지 이해가 됐습니다. "Red 노드가 연속으로 나올 수 없다"는 규칙은, 2-3-4 Tree에서 "하나의 노드에 최대 3개의 Key만 들어간다"는 규칙과 같습니다.

이 관점에서 보면, Red-Black Tree는 B-Tree 계열의 일원입니다. 그래서 데이터베이스에서 쓰는 B-Tree와 비슷한 성질을 많이 공유합니다.

직접 구현해보기 - Red-Black Tree Node 구조

이론만 봐서는 머릿속에 남지 않아서, 간단하게 노드 구조만이라도 직접 코드로 작성해봤습니다.

// Java로 구현한 Red-Black Tree 노드 구조
enum Color {
    RED, BLACK
}

class RBNode<T extends Comparable<T>> {
    T data;
    Color color;
    RBNode<T> left;
    RBNode<T> right;
    RBNode<T> parent;

    public RBNode(T data) {
        this.data = data;
        this.color = Color.RED;  // 새 노드는 항상 Red로 삽입
        this.left = null;
        this.right = null;
        this.parent = null;
    }

    public boolean isRed() {
        return color == Color.RED;
    }

    public boolean isBlack() {
        return color == Color.BLACK;
    }

    public RBNode<T> getGrandparent() {
        if (parent == null) return null;
        return parent.parent;
    }

    public RBNode<T> getUncle() {
        RBNode<T> grandparent = getGrandparent();
        if (grandparent == null) return null;
        if (parent == grandparent.left) {
            return grandparent.right;
        } else {
            return grandparent.left;
        }
    }

    public RBNode<T> getSibling() {
        if (parent == null) return null;
        if (this == parent.left) {
            return parent.right;
        } else {
            return parent.left;
        }
    }
}

이 코드를 직접 작성하면서, Red-Black Tree의 구조가 생각보다 단순하다는 걸 깨달았습니다. 일반 BST 노드에 Color 필드 하나와 parent 포인터 하나만 추가하면 됩니다. 복잡한 건 삽입/삭제 로직이지, 데이터 구조 자체는 간단합니다.

회전 연산도 한번 작성해봤습니다:

class RBTree<T extends Comparable<T>> {
    private RBNode<T> root;

    // 왼쪽 회전: x의 오른쪽 자식 y를 x의 부모로 만들기
    private void rotateLeft(RBNode<T> x) {
        RBNode<T> y = x.right;
        x.right = y.left;

        if (y.left != null) {
            y.left.parent = x;
        }

        y.parent = x.parent;

        if (x.parent == null) {
            root = y;
        } else if (x == x.parent.left) {
            x.parent.left = y;
        } else {
            x.parent.right = y;
        }

        y.left = x;
        x.parent = y;
    }

    // 오른쪽 회전: x의 왼쪽 자식 y를 x의 부모로 만들기
    private void rotateRight(RBNode<T> x) {
        RBNode<T> y = x.left;
        x.left = y.right;

        if (y.right != null) {
            y.right.parent = x;
        }

        y.parent = x.parent;

        if (x.parent == null) {
            root = y;
        } else if (x == x.parent.right) {
            x.parent.right = y;
        } else {
            x.parent.left = y;
        }

        y.right = x;
        x.parent = y;
    }
}

회전 연산도 포인터 몇 개만 바꾸면 됩니다. 정말로 $O(1)$입니다. 이 코드를 직접 손으로 그려가면서 따라해보니까, "아, 이래서 회전이라고 부르는구나"라고 와닿았습니다. 트리가 정말로 회전하듯이 돌아갑니다.

정리 - Red-Black Tree는 "실용적인 균형"이다

Red-Black Tree를 처음 배웠을 때는 "왜 이렇게 복잡하게 만들었을까?"라고 생각했습니다. 색깔 규칙, 회전, 경우의 수... 머리가 아팠습니다.

하지만 실제로 써보고, 리눅스 커널과 Java 소스코드를 보면서 이해했습니다. 이건 단순한 "이론"이 아니라, 수십 년간 실제로 검증된 공학적 타협점이었습니다.

핵심을 정리해봅니다:

1. 이진 탐색 트리는 편향될 수 있다: 순서대로 데이터가 들어오면 링크드 리스트가 되어 $O(N)$이 된다.
2. 균형을 맞춰야 한다: 트리의 높이를 $\log N$으로 유지하면 탐색이 빠르다.
3. 완벽한 균형은 비싸다: AVL처럼 엄격하게 균형을 맞추면 삽입/삭제 비용이 크다.
4. 적당한 균형이 실용적이다: Red-Black Tree는 "가장 긴 경로가 가장 짧은 경로의 2배 이하"만 보장한다. 이 정도면 충분히 빠르다.
5. 색깔이 균형의 핵심이다: 5가지 색깔 규칙이 높이를 자동으로 제한한다.
6. 실제로 많이 쓰인다: Java HashMap, Linux CFS, C++ STL map 등 핵심 시스템들이 모두 Red-Black Tree를 채택했다.

저는 Red-Black Tree를 배우면서, "완벽함"보다 "실용성"이 중요하다는 걸 받아들였습니다. 엔지니어링은 항상 트레이드오프입니다. 조회 속도를 조금 희생하고, 삽입/삭제 속도를 얻는다. 구현 복잡도를 조금 높이고, 안정적인 성능을 보장받는다.

결국 이거였습니다. Red-Black Tree는 "이론적으로 완벽한" 자료구조가 아니라, "실제로 가장 잘 작동하는" 자료구조였습니다. 그래서 40년이 지난 지금도 여전히 쓰이고 있습니다.