Red-Black Tree 구조와 원리 완전 분석

개요

Red-Black Tree(적흑 트리)는 자가 균형 이진 탐색 트리입니다. 각 노드에 색(빨강/검정)을 부여하고 색 속성을 유지하여 트리 높이를 O(log N)으로 보장합니다. C++의 std::map, std::set의 내부 구현 자료구조입니다.

1. 5가지 속성

1. 모든 노드는 빨간색 또는 검은색
2. 루트 노드는 검은색
3. 모든 리프(NIL) 노드는 검은색
4. 빨간 노드의 자식은 반드시 검은색 (연속 빨강 금지)
5. 루트에서 모든 NIL 리프까지 경로상 검은 노드 수가 동일

이 속성으로 최장 경로 ≤ 최단 경로 × 2 → 높이 ≤ 2log(N+1)

2. 삽입 과정

// 개념적 구현 (핵심 케이스)
struct Node {
    int key;
    bool isRed;  // true = 빨강, false = 검정
    Node *left, *right, *parent;
};

// 삽입 후 불균형 수정
void FixInsert(Node* z) {
    // z: 새로 삽입된 빨간 노드
    while (z->parent && z->parent->isRed) {
        if (z->parent == z->parent->parent->left) {
            Node* uncle = z->parent->parent->right;

            if (uncle && uncle->isRed) {
                // Case 1: 삼촌이 빨강 → 재색칠
                z->parent->isRed = false;
                uncle->isRed = false;
                z->parent->parent->isRed = true;
                z = z->parent->parent; // 위로 이동
            } else {
                if (z == z->parent->right) {
                    // Case 2: 삼촌이 검정, z가 오른쪽 자식 → 좌회전
                    z = z->parent;
                    RotateLeft(z);
                }
                // Case 3: 삼촌이 검정, z가 왼쪽 자식 → 우회전
                z->parent->isRed = false;
                z->parent->parent->isRed = true;
                RotateRight(z->parent->parent);
            }
        }
        // 대칭 케이스 (else 분기)
    }
    root->isRed = false; // 속성 2 유지
}

3. 회전 연산

//    y              x
//   / \            / \
//  x   C  →      A   y
// / \                / \
//A   B              B   C
void RotateRight(Node* y) {
    Node* x = y->left;
    y->left = x->right;
    if (x->right) x->right->parent = y;
    x->parent = y->parent;
    if (!y->parent) root = x;
    else if (y == y->parent->left) y->parent->left = x;
    else y->parent->right = x;
    x->right = y;
    y->parent = x;
}

// RotateLeft는 대칭 구현

4. 복잡도 분석

연산	복잡도
탐색	O(log N)
삽입	O(log N)
삭제	O(log N)
최소/최대	O(log N)
순회	O(N)

5. Red-Black Tree vs AVL Tree

항목	Red-Black Tree	AVL Tree
균형 기준	색 속성	높이 차이 ≤ 1
삽입 회전	최대 2회	최대 2회
삭제 회전	최대 3회	O(log N)
검색 성능	약간 낮음	약간 높음
삽입/삭제	빠름	느림
사용 사례	map, set, epoll	데이터베이스

결론: 삽입/삭제가 잦으면 Red-Black, 탐색이 압도적으로 많으면 AVL 선택.

6. std::map 활용

#include <map>
#include <string>

std::map<std::string, int> scores; // 내부적으로 Red-Black Tree

// 삽입 O(log N)
scores["Alice"] = 95;
scores.emplace("Bob", 87);

// 탐색 O(log N)
auto it = scores.find("Alice");
if (it != scores.end())
    std::cout << it->second << "\n"; // 95

// 범위 탐색
auto range = scores.equal_range("A");

// 정렬된 순서 보장 (in-order 순회)
for (const auto& [name, score] : scores)
    std::cout << name << ": " << score << "\n";

7. 실전 활용 — 게임 랭킹 시스템

#include <map>
#include <set>

// 점수로 정렬된 플레이어 집합
// multiset: 같은 점수 허용
std::multiset<std::pair<int, std::string>,
    std::greater<>> leaderboard; // 내림차순

// 점수 추가 O(log N)
leaderboard.insert({1500, "Alice"});
leaderboard.insert({2000, "Bob"});
leaderboard.insert({1500, "Charlie"});

// 상위 K명 O(K log N)
int K = 3;
auto it = leaderboard.begin();
for (int i = 0; i < K && it != leaderboard.end(); i++, it++)
    std::cout << i+1 << ". " << it->second << ": " << it->first << "\n";

// 특정 점수 이상인 플레이어 수
int threshold = 1600;
auto lower = leaderboard.lower_bound({threshold, ""});
int count = std::distance(leaderboard.begin(), lower);

정리

Red-Black Tree = 자가 균형 BST, 색 속성으로 O(log N) 보장
5가지 속성 중 빨간 노드는 연속 불가, 검정 높이 균일이 핵심
삽입/삭제 시 회전(최대 3회)과 재색칠로 속성 복원
std::map, std::set, Linux epoll의 내부 구현 자료구조
삽입/삭제 빈번한 시나리오에서 AVL보다 성능 우수