RED / BLACK 트리 구현하기

💡 언제 어떤 트리를 선택할까? AVL 선택: ✓ 탐색이 매우 빈번하고 삽입/삭제가 드문 경우 ✓ 데이터베이스 인덱스처럼 조회 성능이 최우선인 경우 레드-블랙 선택: ✓ 삽입/삭제/탐색이 고르게 발생하는 경우 (대부분의 실무) ✓ 범용적인 자료구조가 필요한 경우 ✓ C++ STL과 호환이 중요한 경우

모든 노드는 빨강(RED) 또는 검정(BLACK)이다.

루트 노드는 항상 검정(BLACK)이다.

모든 리프 노드(NIL)는 검정(BLACK)이다.

빨강(RED) 노드의 자식은 반드시 검정(BLACK)이다. (연속으로 빨강 노드가 올 수 없다)

만약 빨강이 연속된다면? 최악의 경우: 검정-빨강-빨강-검정-빨강-빨강... → 검정 노드 사이에 빨강이 여러 개 끼어들 수 있음 → 트리 높이가 무한정 커질 수 있음! 빨강 연속 금지 시: 검정-빨강-검정-빨강-검정... → 빨강은 검정 사이에만 1개씩만 가능 → 최악의 경우도 "검정 높이 × 2" 이하로 제한!

루트에서 모든 리프까지의 경로에서 검정 노드의 개수는 동일해야 한다.

만약 검정 높이가 다르다면? 경로 A: 검정 3개 → 최소 3단계 경로 B: 검정 10개 → 최소 10단계 → 심각한 불균형! 검정 높이 동일 시: 모든 경로의 검정 노드 수가 같음 → 규칙 4와 결합하여 모든 경로가 2배 이내 → 균형 보장!

규칙 4 (빨강 연속 금지) + 규칙 5 (검정 높이 동일) ↓ 최단 경로 : 최장 경로 = 1 : 2 이내로 제한 ↓ 트리 높이 ≤ 2 log n ↓ O(log n) 보장!

❌ 잘못된 트리 (규칙 5 위반): ⚫10 / \ ⚫5 ⚫30 ← 검정 2개 / \ ⚫2 ⚫7 / ⚫1 ← 검정 4개! 불균형! ✅ 올바른 레드-블랙 트리: ⚫10 / \ ⚫5 ⚫30 ← 모든 경로 검정 2개 / \ / \ 🔴2 🔴7 🔴25 🔴35 → 검정 높이 = 2 → 최대 높이 ≤ 4 (검정 2 × 2) → O(log n) 보장!

#include <iostream> #include <vector> enum class eColor { Red, Black, End, }; struct Node { int Data; eColor Color; Node* Left; Node* Right; Node* Parent; Node(int data) : Data(data) , Color(eColor::Red) , Left(nullptr) , Right(nullptr) , Parent(nullptr) { } }; class RedBlackTree { public: RedBlackTree() { NIL = new Node(0); NIL->Color = eColor::Black; mRoot = NIL; } private: Node* mRoot; Node* NIL; // 센티널 노드 (모든 리프를 대체) }

회전 없이 삽입만 한다면? 10 \ 20 ← 한쪽으로 치우침 \ 30 ← O(n) 성능으로 퇴화! 회전으로 균형 맞춘 결과: 20 ← 균형 잡힘 / \ 10 30 ← O(log n) 보장!

초기 상태: x / \ A y / \ B C 1단계: y의 왼쪽 서브트리(B)를 x의 오른쪽으로 이동 x y / \ / \ A B B C 2단계: y를 x의 위치로 올리고, x를 y의 왼쪽 자식으로 y / \ x C / \ A B 최종: x와 y의 부모-자식 관계가 바뀜

void LeftRotate(Node* x) { Node* y = x->Right; // y는 x의 오른쪽 자식 // 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; // x가 루트였다면 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; }

초기 상태: y / \ x C / \ A B 1단계: x의 오른쪽 서브트리(B)를 y의 왼쪽으로 이동 y x / \ / \ B C A B 2단계: x를 y의 위치로 올리고, y를 x의 오른쪽 자식으로 x / \ A y / \ B C 최종: x와 y의 부모-자식 관계가 바뀜

void RightRotate(Node* y) { Node* x = y->Left; // x는 y의 왼쪽 자식 // 1단계: x의 오른쪽 서브트리를 y의 왼쪽으로 이동 y->Left = x->Right; if (x->Right != NIL) { x->Right->Parent = y; } // 2단계: x의 부모를 y의 부모로 설정 x->Parent = y->Parent; if (y->Parent == NIL) { mRoot = x; // y가 루트였다면 x가 새 루트 } else if (y == y->Parent->Left) { y->Parent->Left = x; } else { y->Parent->Right = x; } // 3단계: y를 x의 오른쪽 자식으로 설정 x->Right = y; y->Parent = x; }

📌 핵심 개념: - 좌회전: 오른쪽 자식이 부모가 됨 - 우회전: 왼쪽 자식이 부모가 됨 📌 중요 속성: ✓ 회전 후에도 BST 속성 유지 (왼쪽 < 부모 < 오른쪽) ✓ 시간 복잡도: O(1) (포인터 조작만) ✓ 트리 균형 복원의 핵심 도구 ✓ 중위 순회 결과는 회전 전후가 동일 📌 회전의 역관계: - LeftRotate(x) 후 RightRotate(y) → 원상복구 - RightRotate(y) 후 LeftRotate(x) → 원상복구

void Insert(int data) { Node* newNode = new Node(data); newNode->Left = NIL; newNode->Right = NIL; Node* y = NIL; Node* x = mRoot; // 새로운 노드를 삽입할 위치를 찾음 // 재귀 함수로 대체 가능 while (x != NIL) { y = x; if (newNode->Data < x->Data) { x = x->Left; } else { x = x->Right; } } // 부모노드 설정 newNode->Parent = y; // 트리가 비어있다면 새 노드가 루트 if (y == NIL) { mRoot = newNode; } else if (newNode->Data < y->Data) { y->Left = newNode; } else { y->Right = newNode; } newNode->Color = eColor::Red; // 새 노드는 빨간색으로 삽입 InsertFixup(newNode); // 삽입 후 균형 맞추기 }

// 모든 노드는 빨강(RED) 또는 검정(BLACK)이다. // 루트 노드는 항상 검정(BLACK)이다. // 모든 리프 노드(NIL)는 검정(BLACK)이다. // 빨강(RED) 노드의 자식은 반드시 검정(BLACK)이다. // (연속으로 빨강 노드가 올 수 없다) // 루트에서 모든 리프까지의 경로에서 // 검정 노드의 개수는 동일해야 한다. void InsertFixup(Node* z) { while (z->Parent->Color == eColor::Red) { if (z->Parent == z->Parent->Parent->Left) { Node* y = z->Parent->Parent->Right; // 삼촌 노드 if (y->Color == eColor::Red) // Case 1: 삼촌이 빨간색 { z->Parent->Color = eColor::Black; //recoloring y->Color = eColor::Black; z->Parent->Parent->Color = eColor::Red; z = z->Parent->Parent; } else { // restruturing if (z == z->Parent->Right) // Case 2: 삼촌이 검은색이고, z가 오른쪽 자식 { z = z->Parent; LeftRotate(z); } // Case 3: 삼촌이 검은색이고, z가 왼쪽 자식 z->Parent->Color = eColor::Black; z->Parent->Parent->Color = eColor::Red; RightRotate(z->Parent->Parent); } } else { Node* y = z->Parent->Parent->Left; // 삼촌 노드 if (y->Color == eColor::Red) // Case 1: 삼촌이 빨간색 { // recoloring z->Parent->Color = eColor::Black; y->Color = eColor::Black; z->Parent->Parent->Color = eColor::Red; z = z->Parent->Parent; } else { //restruturing if (z == z->Parent->Left) // Case 2: 삼촌이 검은색이고, z가 왼쪽 자식 { z = z->Parent; RightRotate(z); } // Case 3: 삼촌이 검은색이고, z가 오른쪽 자식 z->Parent->Color = eColor::Black; z->Parent->Parent->Color = eColor::Red; LeftRotate(z->Parent->Parent); } } } mRoot->Color = eColor::Black; // 루트는 항상 검은색 }

1. 20 삽입: ⚫20 ← 루트는 항상 BLACK 2. 10 삽입: ⚫20 / 🔴10 ← 문제없음 3. 30 삽입: ⚫20 / \ 🔴10 🔴30 ← 문제없음 4. 5 삽입: ⚫20 / \ 🔴10 🔴30 / 🔴5 ← RED-RED 위반! (부모 10도 RED) 삼촌 30이 RED이므로 Case 1: 🔴20 / \ ⚫10 ⚫30 / 🔴5 루트를 BLACK으로: ⚫20 5. 15 삽입: ⚫20 / \ ⚫10 ⚫30 / 🔴5 15는 10의 오른쪽에 삽입: ⚫20 / \ ⚫10 ⚫30 / \ 🔴5 🔴15 ← 문제없음 (부모 10이 BLACK) 최종 결과: ⚫20 / \ ⚫10 ⚫30 / \ 🔴5 🔴15

Node* Search(int data) { Node* current = mRoot; while (current != NIL && data != current->Data) { if (data < current->Data) { current = current->Left; } else { current = current->Right; } } return current; // 찾으면 해당 노드, 못 찾으면 NIL 반환 }

void InOrderTraversal(Node* node) { if (node != NIL) { InOrderTraversal(node->Left); std::cout << node->Data << " "; InOrderTraversal(node->Right); } }

void PrintColorTree(Node* node, int depth = 0) { // ANSI 색상 코드 정의 const std::string RED_COLOR = "\033[31m"; // 빨강 const std::string BLACK_COLOR = "\033[30m"; // 검정 (기본) const std::string RESET_COLOR = "\033[0m"; // 색상 리셋 const std::string BOLD = "\033[1m"; // 굵게 if (node != NIL) { PrintColorTree(node->Right, depth + 1); for (int i = 0; i < depth; ++i) std::cout << " "; std::cout << (node->Color == eColor::Red ? RED_COLOR : BLACK_COLOR) << BOLD << node->Data << "(" << (node->Color == eColor::Red ? "R" : "B") << ")" << RESET_COLOR << "\n"; PrintColorTree(node->Left, depth + 1); } } void DisplayColorTree() { PrintColorTree(mRoot); }

void printUnicodeColorTree(RBNode* node, int depth = 0) { if (node != NIL) { printUnicodeColorTree(node->right, depth + 1); for (int i = 0; i < depth; i++) { std::cout << " "; } // 유니코드 색상 원과 함께 출력 if (node->color == RED) { std::cout << "🔴 " << node->data << std::endl; } else { std::cout << "⚫ " << node->data << std::endl; } printUnicodeColorTree(node->left, depth + 1); } } void displayUnicodeTree() { std::cout << "🔴⚫ Red-Black Tree (유니코드 버전):" << std::endl; if (root == NIL) { std::cout << "Empty tree" << std::endl; } else { printUnicodeColorTree(root); } std::cout << std::endl; }

int main() { RedBlackTree rbt; std::cout << "🔴⚫ Red-Black Tree 완전 정복!" << std::endl; std::cout << "==============================\n" << std::endl; // 데이터 삽입 std::vector<int> data = { 20, 10, 30, 5, 15, 25, 35 }; std::cout << "\n=== 레드-블랙 트리 삽입 과정 ===" << std::endl; for (int value : data) { std::cout << "\n🔄 삽입: " << value << std::endl; rbt.Insert(value); // 기본 출력 (R/B 표기) std::cout << "기본 출력:" << std::endl; rbt.DisplayColorTree(); // 이모지 출력 (🔴⚫) //std::cout << "이모지 출력:" << std::endl; //rbt.displayUnicodeTree(); std::cout << "------------------------" << std::endl; } // 정렬된 결과 출력 //std::cout << "\n=== 🎯 정렬된 결과 (중위 순회) ===" << std::endl; //std::vector<int> sorted = rbt.getSortedArray(); //for (int i = 0; i < sorted.size(); i++) //{ // std::cout << sorted[i]; // if (i < sorted.size() - 1) std::cout << " → "; //} //std::cout << std::endl; // 탐색 테스트 std::cout << "\n=== 🔍 탐색 테스트 ===" << std::endl; std::vector<int> targets = { 15, 40, 25, 1, 30 }; for (int target : targets) { Node* result = rbt.Search(target); if (result != rbt.GetNIL()) { std::cout << "✅ 값 " << target << " 발견! (색상: " << (result->Color == eColor::Red ? "Red" : "Black") << ")" << std::endl; } else { std::cout << "❌ 값 " << target << " 없음!" << std::endl; } } //// 트리 속성 검증 //std::cout << "\n=== ✅ 트리 검증 ===" << std::endl; //if (rbt.validateRedBlackTree()) //{ // std::cout << "✅ Red-Black 트리 속성 모두 만족!" << std::endl; //} //else //{ // std::cout << "❌ Red-Black 트리 속성 위반!" << std::endl; //} //int blackHeight = rbt.getBlackHeight(rbt.root); //if (blackHeight != -1) //{ // std::cout << "✅ 검정 높이: " << blackHeight << " (모든 경로 동일)" << std::endl; //} //else //{ // std::cout << "❌ 검정 높이 불일치!" << std::endl; //} //std::cout << "\n🎉 Red-Black Tree 학습 완료!" << std::endl; //std::cout << "💡 🔴⚫ 이모지로 색상을 구분할 수 있습니다." << std::endl; return 0; }

=== 🔴⚫ 레드-블랙 트리 삽입 과정 === 삽입: 20 Red-Black Tree: ⚫ 20 삽입: 10 Red-Black Tree: ⚫ 20 / 🔴 10 삽입: 30 Red-Black Tree: ⚫ 20 / \ 🔴 10 🔴 30 삽입: 5 (🔴-🔴 위반 발생! → 색상 조정) Red-Black Tree: ⚫ 20 / \ ⚫ 10 ⚫ 30 ← 자동 색상 조정! / 🔴 5 삽입: 15 Red-Black Tree: ⚫ 20 / \ ⚫ 10 ⚫ 30 / \ 🔴 5 🔴 15 삽입: 25 Red-Black Tree: ⚫ 20 / \ ⚫ 10 ⚫ 30 / \ / 🔴 5 🔴 15 🔴 25 삽입: 35 Red-Black Tree: ⚫ 20 / \ ⚫ 10 ⚫ 30 / \ / \ 🔴 5 🔴 15 🔴 25 🔴 35 === 정렬된 결과 (중위 순회) === 5 10 15 20 25 30 35 === 탐색 테스트 === 15: 발견 🔴 40: 없음 ❌ 25: 발견 🔴

void testColorDisplay() { std::cout << "\n=== 🎨 이모지 색상 테스트 ===" << std::endl; // 이모지 테스트 std::cout << "🔴 RED 노드" << std::endl; std::cout << "⚫ BLACK 노드" << std::endl; // 실제 트리에서 색상 확인 RedBlackTree colorTest; colorTest.insert(10); colorTest.insert(5); colorTest.insert(15); std::cout << "\n실제 트리 색상 예시:" << std::endl; colorTest.displayUnicodeTree(); }

// 회전 테스트를 위한 간단한 함수 void demonstrateRotation() { std::cout << "\n=== 🔄 회전 연산 데모 ===\n" << std::endl; RedBlackTree demo; // 좌회전을 유발하는 패턴 std::cout << "좌회전 유발 패턴: 10 → 20 → 30" << std::endl; demo.insert(10); demo.insert(20); demo.insert(30); std::cout << "결과 (자동으로 균형 조정됨):" << std::endl; demo.displayUnicodeTree(); // 우회전을 유발하는 패턴 RedBlackTree demo2; std::cout << "\n우회전 유발 패턴: 30 → 20 → 10" << std::endl; demo2.insert(30); demo2.insert(20); demo2.insert(10); std::cout << "결과 (자동으로 균형 조정됨):" << std::endl; demo2.displayUnicodeTree(); }

std::vector<int> getSortedArray() { std::vector<int> result; InOrderCollect(mRoot, result); return result; } void InOrderCollect(Node* node, std::vector<int>& arr) { if (node != NIL) { InOrderCollect(node->Left, arr); arr.push_back(node->Data); InOrderCollect(node->Right, arr); } } int getBlackHeight(Node* node) { if (node == NIL) { return 1; // NIL 노드는 검정색이므로 높이 1 } int leftBlackHeight = getBlackHeight(node->Left); int rightBlackHeight = getBlackHeight(node->Right); if (leftBlackHeight == -1 || rightBlackHeight == -1 || leftBlackHeight != rightBlackHeight) { return -1; // 불일치 또는 오류 } return leftBlackHeight + (node->Color == eColor::Black ? 1 : 0); } bool validateRedBlackTree() { return validateProperties(mRoot) != -1; } int validateProperties(Node* node) { if (node == NIL) { return 1; // NIL 노드는 검정색이므로 높이 1 } // 속성 4: 빨강 노드의 자식은 반드시 검정 if (node->Color == eColor::Red) { if (node->Left->Color == eColor::Red || node->Right->Color == eColor::Red) { return -1; // 위반 } } int leftBlackHeight = validateProperties(node->Left); int rightBlackHeight = validateProperties(node->Right); if (leftBlackHeight == -1 || rightBlackHeight == -1 || leftBlackHeight != rightBlackHeight) { return -1; // 불일치 또는 오류 } return leftBlackHeight + (node->Color == eColor::Black ? 1 : 0); }

삽입 예시: 1, 2, 3, 4, 5 순서대로 1 삽입: 1 2 삽입: 1 → 회전! → 2 \ / \ 2 1 3 삽입: 2 → 회전! → 2 / \ / \ 1 3 1 3 4 삽입: 연쇄 회전 발생... → 최악의 경우 log n번 회전 필요

같은 삽입: 1, 2, 3, 4, 5 1 삽입: ⚫1 2 삽입: ⚫2 (1회 회전 + 색상 변경) / \ 🔴1 3 삽입: ⚫2 (색상 변경만!) / \ 🔴1 🔴3 → 각 삽입마다 최대 2회 회전

AVL 트리: - 평균 회전: ~50회 - 최악 회전: ~664회 - 높이: ~7 - 탐색: ⭐⭐⭐⭐⭐ 레드-블랙 트리: - 평균 회전: ~10회 ✓ 5배 빠름! - 최악 회전: ~200회 ✓ 3배 빠름! - 높이: ~10 - 탐색: ⭐⭐⭐⭐ 결론: 삽입/삭제 빈번하면 레드-블랙이 압도적!

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

AVL이든 레드-블랙이든: 1. 둘 다 이진 탐색 트리 (BST) → 왼쪽 < 부모 < 오른쪽 유지 2. 중위 순회 = 오름차순 정렬 → 자동 정렬! 예시: 20, 10, 30, 5, 15 삽입 후 AVL: 레드-블랙: 20 20 / \ / \ 10 30 10 30 / \ / \ 5 15 🔴5 🔴15 중위 순회: 5→10→15→20→30 (동일!) 차이는 밸런싱 방식일 뿐, BST 속성은 둘 다 유지!