레드 블랙 트리

📌 레드-블랙 트리란?

레드-블랙 트리(Red-Black Tree, RBT)는 균형 잡힌 이진 탐색 트리(BST)의 일종으로, 삽입과 삭제 시 스스로 균형을 유지하여 항상 O(log N) 시간 복잡도를 보장합니다.

---

📚 왜 레드-블랙 트리가 필요한가?

기본적인 BST는 삽입 순서에 따라 한쪽으로 치우친 구조가 될 수 있으며, 이 경우 시간 복잡도는 최악의 경우 O(N)까지 증가합니다. 이러한 문제를 해결하기 위해 등장한 것이 바로 자가 균형 트리(Self-Balancing Tree)이며, 그 대표적인 예가 AVL Tree와 레드-블랙 트리입니다.

---

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

1. 모든 노드는 Red 또는 Black이다.
2. 루트 노드는 항상 Black이다.
3. 모든 Leaf 노드(NIL)는 Black이다.
4. Red 노드의 자식은 모두 Black이다.
   → Red-Red 관계는 금지 (Double Red 금지)
5. 루트에서 리프까지의 모든 경로에는 동일한 수의 Black 노드가 있어야 한다.
   → 이를 Black Height라고 부른다.

이 규칙들 덕분에 레드-블랙 트리는 삽입/삭제가 일어나도 트리의 균형이 극단적으로 무너지지 않음을 보장합니다.

---

🧱 레드-블랙 트리의 구조

enum class Color { Red, Black };

struct Node {
    Node* parent = nullptr;
    Node* left = nullptr;
    Node* right = nullptr;
    int key = {};
    Color color = Color::Black;
};

• key: 노드에 저장된 값
• color: Red or Black
• left, right, parent: 트리 탐색 및 회전에서 핵심이 되는 포인터

또한, 모든 자식이 없는 노드는 NIL 노드라는 더미 노드를 가리키며, 이는 항상 Black입니다.

---

🛠️ 삽입(Insert) 알고리즘

1. 새 노드는 항상 Red로 삽입된다.
2. BST 삽입 방식으로 위치를 정한다.
3. 삽입 후, Red-Black Tree 규칙에 위배되는 경우 회전(Rotate) 또는 색 변경(Color Flipping)을 통해 복구한다.

🎯 삽입 시 위반 가능성 있는 규칙

• 대부분 규칙 4 (Red의 자식은 Black)이 위반된다.
• 새 노드와 부모가 모두 Red인 경우 → Double Red 발생

🔄 삽입 후 균형 복구 (InsertFixup)

void InsertFixup(Node* node) {
    while (node->parent->color == Color::Red) {
        Node* uncle = (node->parent == node->parent->parent->left)
                        ? node->parent->parent->right
                        : node->parent->parent->left;

        if (uncle->color == Color::Red) {
            // Case 1: 부모와 삼촌이 Red
            node->parent->color = Color::Black;
            uncle->color = Color::Black;
            node->parent->parent->color = Color::Red;
            node = node->parent->parent;
        }
        else {
            if (node == node->parent->right && node->parent == node->parent->parent->left) {
                // Case 2: Triangle (왼쪽-오른쪽)
                node = node->parent;
                LeftRotate(node);
            }
            else if (node == node->parent->left && node->parent == node->parent->parent->right) {
                // Case 2 (대칭): 오른쪽-왼쪽
                node = node->parent;
                RightRotate(node);
            }

            // Case 3: Line
            node->parent->color = Color::Black;
            node->parent->parent->color = Color::Red;

            if (node == node->parent->left)
                RightRotate(node->parent->parent);
            else
                LeftRotate(node->parent->parent);
        }
    }

    _root->color = Color::Black; // 루트는 항상 Black
}

🔁 회전 함수

void LeftRotate(Node* x) {
    Node* y = x->right;
    x->right = y->left;
    if (y->left != _nil) y->left->parent = x;
    y->parent = x->parent;

    if (x->parent == _nil)
        _root = y;
    else if (x == x->parent->left)
        x->parent->left = y;
    else
        x->parent->right = y;

    y->left = x;
    x->parent = y;
}

→ RightRotate는 반대 방향으로 동일하게 작동

---

🗑️ 삭제(Delete) 알고리즘

1. BST 방식으로 노드를 삭제
2. 삭제된 노드 또는 그 자리를 대체하는 노드가 Black이면 Double Black 문제 발생
3. DeleteFixup 함수를 통해 균형 복구

---

❗ Double Black이란?

Black 노드를 삭제하거나 대체했을 때, 트리의 한 경로에 Black이 하나 부족해진 상태를 말합니다.

---

🔁 삭제 후 균형 복구 (DeleteFixup)

void DeleteFixup(Node* x) {
    while (x != _root && x->color == Color::Black) {
        if (x == x->parent->left) {
            Node* s = x->parent->right;

            if (s->color == Color::Red) {
                // Case 1: 형제가 Red
                s->color = Color::Black;
                x->parent->color = Color::Red;
                LeftRotate(x->parent);
                s = x->parent->right;
            }

            if (s->left->color == Color::Black && s->right->color == Color::Black) {
                // Case 2: 형제와 자식들 모두 Black
                s->color = Color::Red;
                x = x->parent;
            }
            else {
                if (s->right->color == Color::Black) {
                    // Case 3: 형제의 Near Child가 Red
                    s->left->color = Color::Black;
                    s->color = Color::Red;
                    RightRotate(s);
                    s = x->parent->right;
                }

                // Case 4: 형제의 Far Child가 Red
                s->color = x->parent->color;
                x->parent->color = Color::Black;
                s->right->color = Color::Black;
                LeftRotate(x->parent);
                x = _root;
            }
        }
        else {
            // 대칭적인 오른쪽 자식 케이스
            // 동일한 로직, 방향만 반대로 작성
        }
    }
    x->color = Color::Black;
}

---

⚖️ 레드-블랙 트리 vs AVL 트리

구분	레드-블랙 트리	AVL 트리
삽입/삭제 성능	빠름 (덜 엄격한 균형)	느림 (균형 유지가 까다로움)
탐색 성능	보통	더 빠름
회전 횟수	적음	많음
사용 예	STL map, set	고속 탐색이 필요한 경우

---