LV18 레드-블랙 트리 구현하기 (Implement Red-Black Tree)

레드-블랙 트리 소개

레드-블랙 트리(Red-Black Tree)는 자가 균형 이진 탐색 트리(BST) 로, 트리의 높이가 O(log N) 을 넘지 않도록 제한됩니다. 덕분에 일반적인 이진 탐색 트리가 최악의 경우 O(N)까지 느려질 수 있는 것과 달리, 탐색, 삽입, 삭제를 모두 O(log N) 시간에 수행할 수 있습니다.

•

각 노드는 추가 속성으로 색(Color) 을 가지며, 값은 빨강(Red) 또는 검정(Black) 입니다.

•

이 색은 삽입과 삭제 과정에서 균형을 유지하기 위한 규칙을 적용하는 데 사용되어, 데이터 조회와 수정이 효율적으로 이루어지도록 합니다.

레드-블랙 트리의 성질(규칙)

레드-블랙 트리는 다음 성질을 만족합니다.

노드 색: 각 노드는 빨강 또는 검정이다.

루트 성질: 루트는 항상 검정이다.

빨강 노드 성질: 빨강 노드는 빨강 자식을 가질 수 없다. (빨강이 연속으로 등장할 수 없다.)

검정 높이 성질: 어떤 노드에서 그 노드의 모든 리프(NIL)까지 가는 모든 경로에는 같은 개수의 검정 노드가 존재한다.

리프 성질: 모든 리프(NIL 노드)는 검정이다.

이 성질들(특히 빨강 연속 금지와 검정 높이 동일) 덕분에 루트에서 임의의 리프까지 가는 경로에서 가장 긴 경로가 가장 짧은 경로의 2배를 넘지 않게 되어, 트리의 균형과 성능이 유지됩니다.

균형(Balancing)

균형을 직관적으로 이해하는 간단한 예로, 레드-블랙 트리에서는 노드 3개가 일렬로 이어진 체인 형태가 성질을 만족하면서 유지되기 어렵습니다. 가능한 색 조합을 직접 대입해보면, 어떤 방식이든 레드-블랙 트리의 규칙을 위반하게 되는 경우를 확인할 수 있습니다.

유도되는 성질(Inferred properties)

•

루트에서 리프(NIL 포함)까지의 경로에 있는 검정 노드의 개수(Black Height) 를 blackHeight 라고 하며, 트리 높이를 h 라고 할 때 보통 blackHeight >= h/2 관계가 성립합니다.

•

노드 개수가 N인 레드-블랙 트리의 높이 h는 h <= 2log(N+1) 을 만족합니다.

•

어떤 노드의 검정 깊이(Black depth) 는 루트에서 해당 노드까지 내려오면서 만나는 검정 노드의 개수를 의미합니다.

레드-블랙 트리의 기본 연산

1. 삽입(Insertion)

새 노드를 삽입할 때는 보통 다음 2단계를 거칩니다.

•

1단계: BST 규칙으로 먼저 삽입

•

2단계: 삽입으로 레드-블랙 성질이 깨질 수 있으므로 위반을 수정(Fix-Up)

상황을 나눠 보면 다음과 같습니다.

•

새 노드의 부모가 검정이면, 성질이 깨지지 않는 경우가 많습니다.

•

새 노드의 부모가 빨강이면, “빨강이 연속으로 올 수 없다”는 성질을 위반할 수 있어서 수정이 필요합니다.

일반적으로 새 노드는 빨강으로 삽입한 뒤, 아래와 같은 케이스로 처리합니다.

•

Case 1: 삼촌(uncle)이 빨강

◦

부모와 삼촌을 검정으로 바꾸고, 조부모를 빨강으로 바꾼 뒤

◦

조부모로 올라가며 같은 과정을 반복합니다.

•

Case 2: 삼촌이 검정

◦

노드의 위치에 따라 부모 또는 조부모를 기준으로 회전을 수행하고,

◦

필요하면 색도 함께 바꿔서 성질을 복구합니다.

2. 탐색(Searching)

탐색은 일반 BST와 완전히 동일합니다.

루트에서 시작합니다.

찾는 값이 현재 노드 값과 같으면 성공입니다.

찾는 값이 더 작으면 왼쪽으로, 더 크면 오른쪽으로 이동합니다.

값을 찾거나 NIL에 도달할 때까지 반복합니다.

3. 삭제(Deletion)

삭제 역시 기본 흐름은 다음과 같습니다.

BST 규칙으로 노드를 삭제합니다.

삭제 과정에서 (특히) 검정 노드가 제거되면, "double black" 상황이 생길 수 있어 성질 복구가 필요합니다.

검정 노드를 삭제한 뒤에는, 형제(sibling) 노드의 색에 따라 보정 방법이 달라집니다.

•

형제가 빨강이면: 부모를 기준으로 회전하고 색을 재배치합니다.

•

형제가 검정이면:

◦

형제의 자식이 모두 검정이면 형제를 재색칠하고 문제를 위로 전파합니다.

◦

형제의 자식 중 빨강이 있으면, (가까운/먼 자식 위치에 따라) 회전과 재색칠을 조합해 해결합니다.

4. 회전(Rotation)

회전은 레드-블랙 트리의 균형을 유지하는 핵심 연산입니다. BST의 정렬 성질을 유지하면서 트리 구조만 바꾸어, 루트에서 리프까지의 최장 경로가 최단 경로의 2배를 넘지 않도록 만듭니다.

회전은 크게 두 가지입니다.

i. 좌회전(Left Rotation)

노드 x를 기준으로 좌회전을 하면, x의 오른쪽 자식 y가 x 자리로 올라가고 x는 y의 왼쪽 자식이 됩니다. 큰 흐름은 다음과 같습니다.

y의 왼쪽 서브트리를 떼어 x의 오른쪽 자식으로 옮깁니다.

y를 x가 있던 자리(부모 연결)에 붙입니다.

x를 y의 왼쪽 자식으로 붙이고, 부모 포인터를 정리합니다.

좌회전 의사코드(Pseudo-Code)

void leftRotate(Node* x) {
    // 올릴 노드(오른쪽 자식)
    Node* y = x.right;

    // 1) y의 왼쪽 서브트리를 x의 오른쪽으로 넘긴다
    x.right = y.left;
    if (y.left != NIL) {
        y.left.parent = x;
    }

    // 2) y를 x가 있던 위치에 연결한다
    y.parent = x.parent;

    if (x.parent == NIL) {
        root = y;               // x가 루트였던 경우
    }
    else if (x == x.parent.left) {
        x.parent.left = y;
    }
    else {
        x.parent.right = y;
    }

    // 3) x를 y의 왼쪽 자식으로 둔다
    y.left = x;
    x.parent = y;
}
C++
복사

ii. 우회전(Right Rotation)

우회전은 좌회전의 반대입니다. 노드 x를 기준으로 우회전을 하면, x의 왼쪽 자식 y가 x 자리로 올라가고 x는 y의 오른쪽 자식이 됩니다.

y의 오른쪽 서브트리를 떼어 x의 왼쪽 자식으로 옮깁니다.

y를 x가 있던 자리(부모 연결)에 붙입니다.

x를 y의 오른쪽 자식으로 붙이고, 부모 포인터를 정리합니다.

우회전 의사코드(Pseudo-Code)

void rightRotate(Node* x) {
    // 올릴 노드(왼쪽 자식)
    Node* y = x.left;

    // 1) y의 오른쪽 서브트리를 x의 왼쪽으로 넘긴다
    x.left = y.right;
    if (y.right != NIL) {
        y.right.parent = x;
    }

    // 2) y를 x가 있던 위치에 연결한다
    y.parent = x.parent;

    if (x.parent == nullptr) {
        root = y;               // x가 루트였던 경우
    }
    else if (x == x.parent.right) {
        x.parent.right = y;
    }
    else {
        x.parent.left = y;
    }

    // 3) x를 y의 오른쪽 자식으로 둔다
    y.right = x;
    x.parent = y;
}
C++
복사

아래에는 위에서 언급한 모든 연산을 포함한 레드-블랙 트리의 상세 구현 예시가 이어집니다.

삽입 (Insert)

노드를 삽입하면 처음에는 빨강(Red) 으로 색칠합니다.

이때 규칙을 어길 수 있어서 리컬러링(Recoloring) 과 리스트럭처링(Restructuring, 회전) 이 필요합니다.

1) 리컬러링(Recoloring)

•

삽입한 노드의 부모와 삼촌이 모두 빨강인 경우 → 부모와 삼촌을 검정, 조부모를 빨강으로 바꿉니다.

•

만약 루트까지 올라가서 충돌이 발생하면 다시 같은 규칙을 적용합니다.

2) 리스트럭처링(Restructuring, 회전)

•

삽입한 노드의 부모는 빨강인데, 삼촌은 검정이거나 없는 경우.

•

이때 조부모, 부모, 새 노드의 위치 관계에 따라 회전(Rotation) 을 합니다.

삽입 시 기본 규칙

•

새로운 노드는 항상 빨강(Red) 으로 삽입한다.

•

이때 부모가 빨강이면 Double Red 문제가 발생할 수 있다.

•

Double Red 해결에는 Restructuring(회전) 과 Recoloring(색변경) 두 가지 전략이 있다.

Double Red 해결 전략

(A) 삼촌(U)이 검정일 때 → Restructuring

삼촌이 검정일 때 Restructuring(회전)을 사용하는 이유:

삼촌이 검정이면 Recoloring만으로는 검정 노드 개수 균형을 맞출 수 없기 때문입니다.

구체적으로:

•

검정 높이 규칙 위반: 부모(P)와 삼촌(U) 중 하나만 검정이면, 단순히 색을 바꾸는 것만으로는 "루트에서 모든 리프까지의 경로에서 검정 노드 개수가 동일해야 한다"는 규칙을 유지할 수 없습니다.

•

구조 변경 필요: 따라서 노드들의 위치 관계 자체를 바꿔야 하며, 이때 회전(Rotation)을 사용합니다.

•

해결 방법: 새 노드(N), 부모(P), 조상(G)을 값 기준으로 오름차순 정렬하여 중간값을 새로운 부모로 두고, 새로운 부모는 검정, 자식 둘은 빨강으로 색을 바꿉니다.

반대로 삼촌이 빨강일 때는 부모와 삼촌을 모두 검정으로, 조상을 빨강으로 바꿔도 검정 노드 개수 균형이 유지되므로 간단한 Recoloring으로 해결할 수 있습니다.

구조를 바꿔서 해결한다.

새 노드(N), 부모(P), 조상(G)을 값 기준으로 오름차순 정렬한다.

중간값을 새로운 부모로 두고, 나머지 둘을 자식으로 만든다.

새로운 부모는 검정, 자식 둘은 빨강으로 색을 바꾼다.

즉, 회전 + 색상 교체로 Double Red를 해결.

(B) 삼촌(U)이 빨강일 때 → Recoloring

삼촌이 빨강일 때 Recoloring을 하는 이유는 구조 변경 없이 색상만으로 문제를 해결할 수 있기 때문입니다.

구체적으로:

•

부모(P)와 삼촌(U)이 모두 빨강이면, 둘 다 검정으로 바꾸고 조상(G)을 빨강으로 만들어도 검정 노드 개수 균형이 유지됩니다.

•

회전(Restructuring)은 트리 구조를 바꾸는 복잡한 작업인 반면, Recoloring은 단순히 색만 바꾸면 되므로 더 효율적입니다.

•

반대로 삼촌이 검정이면 색상만으로는 균형을 맞출 수 없어서 Restructuring(회전)이 필요합니다.

핵심 원리:

레드-블랙 트리는 "루트에서 모든 리프까지 경로의 검정 노드 개수가 동일해야 한다"는 규칙이 있습니다. 삼촌이 빨강일 때는 부모와 삼촌을 검정으로, 조상을 빨강으로 바꿔도 이 규칙이 깨지지 않기 때문에 간단한 Recoloring으로 해결할 수 있는 것입니다.

색을 바꿔서 해결한다.

부모(P)와 삼촌(U)을 검정으로, 조상(G)을 빨강으로 바꾼다.

만약에 G가 루트라면 반드시 검정으로 다시 바꿔준다.

Recoloring은 간단해 보이지만 문제는 조상 노드(G)가 루트 노드가 아니면서, 조상 노드(G)가 또다시 Double Red 문제가 발생하는 경우이다.

조상(G)이 빨강이 되어 또 Double Red가 생기면, 같은 방식(Restructuring/Recoloring)을 반복한다.

해결 과정

현재 상태

•

G=5가 빨강, P=9도 빨강 → Double Red 발생.

•

삼촌 U=14는 빨강.

Recoloring 수행

•

P(9)와 U(14)를 검정으로 변경.

•

G(11)을 빨강으로 변경.

문제 확인

•

이제 루트인 11이 빨강이 되었는데, 규칙상 루트는 반드시 검정이어야 한다.

최종 조정

•

루트 11을 검정으로 바꾸면 모든 규칙이 만족된다.

•

Recoloring은 단순히 색을 바꾸는 작업이지만, 조상(G)이 빨강이 되면서 새로운 Double Red를 만들 수 있다.

•

이 경우 Recoloring을 반복하거나, 상황에 따라 Restructuring(회전) 으로 넘어가야 한다.

•

루트 노드는 무조건 검정이 되도록 마지막에 조정한다.

왜 C++ STL은 레드-블랙을 선택했나?

map/set의 실제 사용 패턴:
✓ 삽입: 매우 빈번
✓ 삭제: 빈번  
✓ 탐색: 빈번 (but O(log n)이면 충분)

AVL을 선택했다면:
✓ 탐색 10% 빠름
✗ 삽입/삭제 5배 느림 ← 치명적!
✗ 실무 전체 성능 저하

레드-블랙을 선택:
✓ 삽입/삭제 5배 빠름 ← 결정적 장점!
✓ 실무 전반적 성능 우수
△ 탐색 약간 느림 (실용적으로 무시 가능)
Plain Text
복사

// ============================================================
// Red-Black Tree — 학습용 구현
// ------------------------------------------------------------
//  섹션 구성:
//    1) 기본 타입 (Color, Node)
//    2) RedBlackTree 선언
//    3) 회전 (Left/Right Rotate)
//    4) 삽입 + InsertFixup (3 Cases)
//    5) 삭제 + DeleteFixup (4 Cases)   ← 원본 코드에 빠져 있던 부분
//    6) 탐색 & 순회 (in-order, level-order)
//    7) 시각화 (ANSI 컬러 + 레벨 출력)
//    8) 속성 검증 (5가지 속성 + Black Height)
//    9) 데모 main
// ============================================================

#include <iostream>
#include <vector>
#include <queue>
#include <string>

// ============================================================
// 1. 기본 타입
// ============================================================

enum class Color { Red, Black };

struct Node
{
    int   Key;
    Color Col;
    Node* Left;
    Node* Right;
    Node* Parent;

    Node(int k, Color c = Color::Red)
        : Key(k), Col(c), Left(nullptr), Right(nullptr), Parent(nullptr) {}
};

// ============================================================
// 2. RedBlackTree 클래스
// ============================================================

class RedBlackTree
{
public:
    RedBlackTree()
    {
        // NIL 센티넬: 모든 리프를 대체하는 검정 더미 노드.
        //  - 자기참조로 초기화해 두면 어느 포인터로 접근해도 NPE 없음.
        NIL = new Node(0, Color::Black);
        NIL->Left = NIL->Right = NIL->Parent = NIL;
        mRoot = NIL;
    }

    ~RedBlackTree()
    {
        destroyRec(mRoot);
        delete NIL;
    }

    RedBlackTree(const RedBlackTree&)            = delete;
    RedBlackTree& operator=(const RedBlackTree&) = delete;

    // ----- Public API -----
    void  Insert(int key);
    bool  Remove(int key);                 // 성공 시 true
    Node* Search(int key) const;

    std::vector<int> InOrder() const;
    int   BlackHeight() const;             // -1 이면 속성 위반
    bool  Validate()    const;

    void  PrintTree()   const;             // 우측이 위, 좌측이 아래로
    void  PrintLevels() const;             // BFS 레벨 출력

    Node* GetRoot() const { return mRoot; }
    Node* GetNil()  const { return NIL; }

private:
    Node* mRoot;
    Node* NIL;

    // --- 회전 ---
    void  LeftRotate (Node* x);
    void  RightRotate(Node* y);

    // --- 삽입 ---
    void  InsertFixup(Node* z);

    // --- 삭제 ---
    void  Transplant(Node* u, Node* v);    // u 자리에 v 를 이식
    Node* Minimum(Node* x) const;
    void  DeleteFixup(Node* x);

    // --- 유틸 ---
    void  destroyRec (Node* node);
    void  inOrderRec (Node* node, std::vector<int>& out) const;
    int   validateRec(Node* node) const;
    void  printRec   (Node* node, int depth) const;
};

C++
복사

// ============================================================
// 3. 회전 (Rotation)
//   - BST 순서는 보존되고 색은 건드리지 않는 O(1) 연산.
//   - LeftRotate 와 RightRotate 는 정확히 서로의 역연산.
// ============================================================

void RedBlackTree::LeftRotate(Node* x)
{
    // y = x 의 오른쪽 자식. y 가 x 의 자리로 올라간다.
    Node* y = x->Right;

    // 1) y 의 왼쪽 서브트리(β) → x 의 오른쪽
    x->Right = y->Left;
    if (y->Left != NIL) y->Left->Parent = x;

    // 2) y 를 x 의 자리에 연결 (루트 케이스 포함)
    y->Parent = x->Parent;
    if      (x->Parent == NIL)        mRoot = y;
    else if (x == x->Parent->Left)    x->Parent->Left  = y;
    else                              x->Parent->Right = y;

    // 3) x 를 y 의 왼쪽 자식으로
    y->Left   = x;
    x->Parent = y;
}

void RedBlackTree::RightRotate(Node* y)
{
    Node* x = y->Left;

    y->Left = x->Right;
    if (x->Right != NIL) x->Right->Parent = y;

    x->Parent = y->Parent;
    if      (y->Parent == NIL)        mRoot = x;
    else if (y == y->Parent->Left)    y->Parent->Left  = x;
    else                              y->Parent->Right = x;

    x->Right  = y;
    y->Parent = x;
}

// ============================================================
// 4. 삽입
// ============================================================

void RedBlackTree::Insert(int key)
{
    Node* z = new Node(key, Color::Red);   // 새 노드는 항상 RED
    z->Left  = NIL;
    z->Right = NIL;

    // --- 표준 BST 삽입 ---
    Node* parent = NIL;
    Node* cur    = mRoot;
    while (cur != NIL)
    {
        parent = cur;
        cur = (key < cur->Key) ? cur->Left : cur->Right;
    }
    z->Parent = parent;
    if      (parent == NIL)         mRoot = z;
    else if (key < parent->Key)     parent->Left  = z;
    else                            parent->Right = z;

    // --- RB 속성 복구 ---
    InsertFixup(z);
}

// InsertFixup: 부모가 RED 일 때만 속성 4(연속 RED) 를 위반한다.
//   부모가 조부모의 "왼쪽" 자식인 경우 기준:
//     Case 1 : 삼촌 = RED
//              → 부모/삼촌 BLACK, 조부모 RED, z ← 조부모 (위로 전파)
//     Case 2 : 삼촌 = BLACK, z 가 꺾인 모양 (부모의 오른쪽)
//              → z ← 부모, LeftRotate(z)  ⇒ Case 3 모양으로 정렬
//     Case 3 : 삼촌 = BLACK, z 가 일직선   (부모의 왼쪽)
//              → 부모 BLACK, 조부모 RED, RightRotate(조부모)  (루프 종료)
//   부모가 오른쪽 자식이면 좌우 대칭.
void RedBlackTree::InsertFixup(Node* z)
{
    while (z->Parent->Col == Color::Red)
    {
        Node* gp = z->Parent->Parent;

        if (z->Parent == gp->Left)
        {
            Node* uncle = gp->Right;

            if (uncle->Col == Color::Red)                // Case 1
            {
                z->Parent->Col = Color::Black;
                uncle->Col     = Color::Black;
                gp->Col        = Color::Red;
                z = gp;
            }
            else
            {
                if (z == z->Parent->Right)               // Case 2
                {
                    z = z->Parent;
                    LeftRotate(z);
                }
                z->Parent->Col         = Color::Black;   // Case 3
                z->Parent->Parent->Col = Color::Red;
                RightRotate(z->Parent->Parent);
            }
        }
        else  // 좌우 대칭
        {
            Node* uncle = gp->Left;

            if (uncle->Col == Color::Red)                // Case 1'
            {
                z->Parent->Col = Color::Black;
                uncle->Col     = Color::Black;
                gp->Col        = Color::Red;
                z = gp;
            }
            else
            {
                if (z == z->Parent->Left)                // Case 2'
                {
                    z = z->Parent;
                    RightRotate(z);
                }
                z->Parent->Col         = Color::Black;   // Case 3'
                z->Parent->Parent->Col = Color::Red;
                LeftRotate(z->Parent->Parent);
            }
        }
    }
    mRoot->Col = Color::Black;   // 루트는 항상 BLACK
}

// ============================================================
// 5. 삭제 (CLRS 기준)
//   RB Tree 에서 가장 까다로운 부분. 학습 필수.
// ============================================================

// u 의 자리에 v 를 이식한다. v 의 자식은 호출자가 처리.
// v 가 NIL 이어도 NIL->Parent 를 세팅해 두어야 DeleteFixup 이 동작함.
void RedBlackTree::Transplant(Node* u, Node* v)
{
    if      (u->Parent == NIL)        mRoot = v;
    else if (u == u->Parent->Left)    u->Parent->Left  = v;
    else                              u->Parent->Right = v;
    v->Parent = u->Parent;
}

Node* RedBlackTree::Minimum(Node* x) const
{
    while (x->Left != NIL) x = x->Left;
    return x;
}

bool RedBlackTree::Remove(int key)
{
    Node* z = Search(key);
    if (z == NIL) return false;

    Node* y = z;                       // 실제 "이동/삭제되는" 노드
    Node* x;                           // y 자리를 대체하는 노드 (Fixup 기준점)
    Color yOrigColor = y->Col;

    if (z->Left == NIL)
    {
        x = z->Right;
        Transplant(z, z->Right);
    }
    else if (z->Right == NIL)
    {
        x = z->Left;
        Transplant(z, z->Left);
    }
    else
    {
        // 두 자식이 있으면 오른쪽 서브트리의 최솟값(= 후계자)으로 대체
        y = Minimum(z->Right);
        yOrigColor = y->Col;
        x = y->Right;
        if (y->Parent == z)
        {
            x->Parent = y;             // x 가 NIL 이어도 반드시 설정
        }
        else
        {
            Transplant(y, y->Right);
            y->Right          = z->Right;
            y->Right->Parent  = y;
        }
        Transplant(z, y);
        y->Left          = z->Left;
        y->Left->Parent  = y;
        y->Col           = z->Col;
    }
    delete z;

    // 사라진/이동한 노드가 BLACK 이었다면 Black Height 가 깨졌으므로 복구
    if (yOrigColor == Color::Black) DeleteFixup(x);
    return true;
}

// DeleteFixup: "x 쪽 경로에 검정이 하나 부족하다(doubly-black)" 는 상태 해소.
//   형제 w 의 상태에 따라 4 Case (x 가 왼쪽 자식 기준, 반대는 대칭):
//     Case 1 : w = RED
//              → w BLACK, 부모 RED, LeftRotate(부모) ⇒ Case 2/3/4 로
//     Case 2 : w BLACK, w 의 두 자식 모두 BLACK
//              → w RED, x ← 부모 (여분 검정을 위로 전파)
//     Case 3 : w BLACK, w 의 먼쪽 자식 BLACK, 가까운쪽 자식 RED
//              → 회전 + 재채색  ⇒ Case 4 로
//     Case 4 : w BLACK, w 의 먼쪽 자식 RED
//              → 회전 + 재채색 (루프 종료)
void RedBlackTree::DeleteFixup(Node* x)
{
    while (x != mRoot && x->Col == Color::Black)
    {
        if (x == x->Parent->Left)
        {
            Node* w = x->Parent->Right;

            if (w->Col == Color::Red)                         // Case 1
            {
                w->Col         = Color::Black;
                x->Parent->Col = Color::Red;
                LeftRotate(x->Parent);
                w = x->Parent->Right;
            }
            if (w->Left->Col  == Color::Black &&
                w->Right->Col == Color::Black)                // Case 2
            {
                w->Col = Color::Red;
                x = x->Parent;
            }
            else
            {
                if (w->Right->Col == Color::Black)            // Case 3
                {
                    w->Left->Col = Color::Black;
                    w->Col       = Color::Red;
                    RightRotate(w);
                    w = x->Parent->Right;
                }
                w->Col          = x->Parent->Col;             // Case 4
                x->Parent->Col  = Color::Black;
                w->Right->Col   = Color::Black;
                LeftRotate(x->Parent);
                x = mRoot;   // 루프 탈출
            }
        }
        else  // 좌우 대칭
        {
            Node* w = x->Parent->Left;

            if (w->Col == Color::Red)
            {
                w->Col         = Color::Black;
                x->Parent->Col = Color::Red;
                RightRotate(x->Parent);
                w = x->Parent->Left;
            }
            if (w->Right->Col == Color::Black &&
                w->Left->Col  == Color::Black)
            {
                w->Col = Color::Red;
                x = x->Parent;
            }
            else
            {
                if (w->Left->Col == Color::Black)
                {
                    w->Right->Col = Color::Black;
                    w->Col        = Color::Red;
                    LeftRotate(w);
                    w = x->Parent->Left;
                }
                w->Col          = x->Parent->Col;
                x->Parent->Col  = Color::Black;
                w->Left->Col    = Color::Black;
                RightRotate(x->Parent);
                x = mRoot;
            }
        }
    }
    x->Col = Color::Black;
}
C++
복사

// ============================================================
// 6. 탐색 & 순회
// ============================================================

Node* RedBlackTree::Search(int key) const
{
    Node* cur = mRoot;
    while (cur != NIL && cur->Key != key)
    {
        cur = (key < cur->Key) ? cur->Left : cur->Right;
    }
    return cur;   // 못 찾으면 NIL
}

std::vector<int> RedBlackTree::InOrder() const
{
    std::vector<int> out;
    inOrderRec(mRoot, out);
    return out;
}

void RedBlackTree::inOrderRec(Node* node, std::vector<int>& out) const
{
    if (node == NIL) return;
    inOrderRec(node->Left, out);
    out.push_back(node->Key);
    inOrderRec(node->Right, out);
}

// ============================================================
// 7. 시각화
// ============================================================

void RedBlackTree::PrintTree() const
{
    if (mRoot == NIL) { std::cout << "(empty)\n"; return; }
    printRec(mRoot, 0);
}

void RedBlackTree::printRec(Node* node, int depth) const
{
    // ANSI: 빨강 = 굵은 빨강, 검정 = 굵은 흰색(어두운 터미널 대비용)
    static const char* CLR_RED   = "\033[1;31m";
    static const char* CLR_BLACK = "\033[1;37m";
    static const char* CLR_RESET = "\033[0m";

    if (node == NIL) return;

    printRec(node->Right, depth + 1);

    for (int i = 0; i < depth; ++i) std::cout << "    ";
    std::cout << (node->Col == Color::Red ? CLR_RED : CLR_BLACK)
              << node->Key
              << (node->Col == Color::Red ? "(R)" : "(B)")
              << CLR_RESET << "\n";

    printRec(node->Left, depth + 1);
}

void RedBlackTree::PrintLevels() const
{
    if (mRoot == NIL) { std::cout << "(empty)\n"; return; }

    std::queue<std::pair<Node*, int>> q;
    q.push({mRoot, 0});
    int curLevel = -1;

    while (!q.empty())
    {
        auto [n, lvl] = q.front();
        q.pop();

        if (lvl != curLevel)
        {
            if (curLevel != -1) std::cout << "\n";
            std::cout << "L" << lvl << ": ";
            curLevel = lvl;
        }
        std::cout << n->Key
                  << (n->Col == Color::Red ? "(R) " : "(B) ");

        if (n->Left  != NIL) q.push({n->Left,  lvl + 1});
        if (n->Right != NIL) q.push({n->Right, lvl + 1});
    }
    std::cout << "\n";
}
C++
복사

// ============================================================
// 8. 검증 — 5가지 속성 모두 체크
// ============================================================

bool RedBlackTree::Validate() const
{
    // 속성 2: 루트는 BLACK
    if (mRoot != NIL && mRoot->Col != Color::Black) return false;
    // 속성 3: NIL 은 BLACK (생성자에서 보장)
    if (NIL->Col != Color::Black) return false;
    // 속성 1 은 enum 으로 보장됨. 속성 4, 5 는 재귀로 검증.
    return validateRec(mRoot) != -1;
}

// 반환값: 해당 서브트리의 Black Height (속성 4 또는 5 위반 시 -1)
int RedBlackTree::validateRec(Node* node) const
{
    if (node == NIL) return 1;   // NIL 은 BLACK 이므로 높이 1

    // 속성 4: RED 의 자식은 모두 BLACK
    if (node->Col == Color::Red)
    {
        if (node->Left->Col  == Color::Red) return -1;
        if (node->Right->Col == Color::Red) return -1;
    }

    int lh = validateRec(node->Left);
    int rh = validateRec(node->Right);
    if (lh == -1 || rh == -1 || lh != rh) return -1;   // 속성 5

    return lh + (node->Col == Color::Black ? 1 : 0);
}

int RedBlackTree::BlackHeight() const
{
    return validateRec(mRoot);
}

// ============================================================
// 9. 유틸
// ============================================================

void RedBlackTree::destroyRec(Node* node)
{
    if (node == NIL) return;
    destroyRec(node->Left);
    destroyRec(node->Right);
    delete node;
}
C++
복사

// ============================================================
// 10. 데모 main
// ============================================================

static void section(const std::string& title)
{
    std::cout << "\n===== " << title << " "
              << std::string(std::max(0, 44 - (int)title.size()), '=') << "\n";
}

int main()
{
    RedBlackTree tree;

    section("Insert demo");
    std::vector<int> inserts = { 20, 10, 30, 5, 15, 25, 35, 1, 8, 40, 50 };
    for (int v : inserts)
    {
        tree.Insert(v);
        std::cout << "[+" << v << "] valid=" << (tree.Validate() ? "O" : "X")
                  << "  bh=" << tree.BlackHeight() << "\n";
    }

    section("Tree (rotated: right=top, left=bottom)");
    tree.PrintTree();

    section("Level order");
    tree.PrintLevels();

    section("In-order (sorted result)");
    for (int v : tree.InOrder()) std::cout << v << " ";
    std::cout << "\n";

    section("Search");
    for (int v : { 15, 99, 1, 35 })
    {
        Node* n = tree.Search(v);
        if (n != tree.GetNil())
            std::cout << "found " << v << " ("
                      << (n->Col == Color::Red ? "R" : "B") << ")\n";
        else
            std::cout << "not found " << v << "\n";
    }

    section("Delete demo (루트/내부/리프 골고루)");
    for (int v : { 10, 20, 1, 50, 25 })
    {
        bool ok = tree.Remove(v);
        std::cout << "[-" << v << "] ok=" << (ok ? "O" : "X")
                  << "  valid=" << (tree.Validate() ? "O" : "X")
                  << "  bh=" << tree.BlackHeight() << "\n";
    }

    section("After deletes");
    tree.PrintTree();

    section("Final in-order");
    for (int v : tree.InOrder()) std::cout << v << " ";
    std::cout << "\n";

    return 0;
}
C++
복사