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

map/set의 실제 사용 패턴: ✓ 삽입: 매우 빈번 ✓ 삭제: 빈번 ✓ 탐색: 빈번 (but O(log n)이면 충분) AVL을 선택했다면: ✓ 탐색 10% 빠름 ✗ 삽입/삭제 5배 느림 ← 치명적! ✗ 실무 전체 성능 저하 레드-블랙을 선택: ✓ 삽입/삭제 5배 빠름 ← 결정적 장점! ✓ 실무 전반적 성능 우수 △ 탐색 약간 느림 (실용적으로 무시 가능)

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; }

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; }

#include <iostream> #include <initializer_list> #include <string> using namespace std; // ===================================================== // 1. 기본 자료구조 // ===================================================== enum class Color { Red, Black }; enum class RotationCase { LL, LR, RR, RL }; struct Node { int key; Color color; Node* left; Node* right; Node* parent; }; class RedBlackTree { private: Node* root; Node* nil; public: RedBlackTree() { nil = new Node{ 0, Color::Black, nullptr, nullptr, nullptr }; nil->left = nil->right = nil->parent = nil; root = nil; } ~RedBlackTree() { Destroy(root); delete nil; } RedBlackTree(const RedBlackTree&) = delete; RedBlackTree& operator=(const RedBlackTree&) = delete; // ================================================= // 2. 삽입 (재귀 방식) // ================================================= void Insert(int key) { Node* inserted = nullptr; // STEP 1. BST 방식으로 삽입 root = InsertBST(root, nil, key, inserted); // 중복 키는 복구할 필요 없음 if (!inserted) return; // STEP 2. Double Red 복구 InsertFixup(inserted); } private: // 일반 BST 재귀 삽입 Node* InsertBST(Node* current, Node* parent, int key, Node*& inserted) { // 삽입 위치 발견 if (current == nil) { inserted = new Node{ key, Color::Red, nil, nil, parent }; return inserted; } // 왼쪽 또는 오른쪽으로 재귀 탐색 if (key < current->key) { current->left = InsertBST( current->left, current, key, inserted ); } else if (key > current->key) { current->right = InsertBST( current->right, current, key, inserted ); } return current; } // ================================================= // 3. Double Red 복구 (재귀 방식) // ================================================= void InsertFixup(Node* node) { // CASE 0. 루트는 항상 BLACK if (node == root) { node->color = Color::Black; return; } // 부모가 BLACK이면 정상 if (!IsRed(node->parent)) return; Node* parent = node->parent; Node* grand = parent->parent; Node* uncle = GetUncle(node); // CASE 1. 삼촌 RED -> 색상 변경 if (IsRed(uncle)) { Recolor(parent, uncle, grand); // 조부모에서 Double Red 재검사 InsertFixup(grand); return; } // CASE 2. 삼촌 BLACK -> 회전 switch (GetRotationCase(node)) { case RotationCase::LL: RotateLL(grand); break; case RotationCase::LR: RotateLR(parent, grand); break; case RotationCase::RR: RotateRR(grand); break; case RotationCase::RL: RotateRL(parent, grand); break; } } // ================================================= // 4. 삼촌 RED -> 색상 변경 // ================================================= void Recolor(Node* parent, Node* uncle, Node* grand) { parent->color = Color::Black; uncle->color = Color::Black; grand->color = Color::Red; } // ================================================= // 5. 삼촌 BLACK -> 회전 유형 판단 // ================================================= RotationCase GetRotationCase(Node* node) const { bool parentLeft = IsLeft(node->parent); bool nodeLeft = IsLeft(node); if (parentLeft) return nodeLeft ? RotationCase::LL : RotationCase::LR; return nodeLeft ? RotationCase::RL : RotationCase::RR; } // ================================================= // 6. LL / LR / RR / RL 회전 // ================================================= // LL: 조부모 오른쪽 회전 void RotateLL(Node* grand) { Node* parent = grand->left; parent->color = Color::Black; grand->color = Color::Red; RotateRight(grand); } // LR: 부모 왼쪽 회전 -> LL 처리 void RotateLR(Node* parent, Node* grand) { RotateLeft(parent); RotateLL(grand); } // RR: 조부모 왼쪽 회전 void RotateRR(Node* grand) { Node* parent = grand->right; parent->color = Color::Black; grand->color = Color::Red; RotateLeft(grand); } // RL: 부모 오른쪽 회전 -> RR 처리 void RotateRL(Node* parent, Node* grand) { RotateRight(parent); RotateRR(grand); } // ================================================= // 7. 실제 포인터 회전 // ================================================= // 왼쪽 회전: 오른쪽 자식이 부모로 올라옴 void RotateLeft(Node* L1) { Node* L2 = L1->right; // L2의 왼쪽 서브트리를 L1에 연결 L1->right = L2->left; if (L2->left != nil) L2->left->parent = L1; // 상위 부모와 L2 연결 ReplaceParent(L1, L2); // L1을 L2의 왼쪽 자식으로 L2->left = L1; L1->parent = L2; } // 오른쪽 회전: 왼쪽 자식이 부모로 올라옴 void RotateRight(Node* L1) { Node* L2 = L1->left; // L2의 오른쪽 서브트리를 L1에 연결 L1->left = L2->right; if (L2->right != nil) L2->right->parent = L1; // 상위 부모와 L2 연결 ReplaceParent(L1, L2); // L1을 L2의 오른쪽 자식으로 L2->right = L1; L1->parent = L2; } // 회전 후 상위 부모 연결 변경 void ReplaceParent(Node* oldNode, Node* newNode) { Node* parent = oldNode->parent; newNode->parent = parent; if (parent == nil) root = newNode; else if (IsLeft(oldNode)) parent->left = newNode; else parent->right = newNode; } // ================================================= // 8. 보조 함수 // ================================================= bool IsRed(Node* node) const { return node->color == Color::Red; } bool IsLeft(Node* node) const { return node == node->parent->left; } Node* GetUncle(Node* node) const { Node* parent = node->parent; Node* grand = parent->parent; return IsLeft(parent) ? grand->right : grand->left; } void Destroy(Node* node) { if (node == nil) return; Destroy(node->left); Destroy(node->right); delete node; } // ================================================= // 9. 학습용 트리 출력 (재귀) // ================================================= void PrintNode(Node* node, int depth) const { if (node == nil) return; PrintNode(node->right, depth + 1); cout << string(depth * 4, ' ') << node->key << (IsRed(node) ? "(R)" : "(B)") << '\n'; PrintNode(node->left, depth + 1); } public: void Print() const { PrintNode(root, 0); cout << "--------------------\n"; } }; // ===================================================== // 10. 실습 // ===================================================== int main() { const initializer_list<int> cases[] = { { 20, 10, 30, 5 }, // 삼촌 RED { 30, 20, 10 }, // LL { 30, 10, 20 }, // LR { 10, 20, 30 }, // RR { 10, 30, 20 } // RL }; const char* names[] = { "Uncle RED", "LL Rotation", "LR Rotation", "RR Rotation", "RL Rotation" }; for (int i = 0; i < 5; ++i) { cout << "\n=== " << names[i] << " ===\n"; RedBlackTree tree; for (int key : cases[i]) { cout << "Insert: " << key << '\n'; tree.Insert(key); tree.Print(); } } return 0; }