RED / BLACK 트리 구현하기

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

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

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

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

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

#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; // 센티널 노드 (모든 리프를 대체) }

1단계: y의 왼쪽 서브트리(B)를 x의 오른쪽으로 이동 x x y / \ / \ / \ A y → A B , B C / \ B C 2단계: y를 x의 위치로 올리기 ( y의 왼쪽 자식을 x로 변경 ) y / \ x C / \ A B 최종: x와 y의 관계가 바뀜 (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; }

1단계: x의 오른쪽 서브트리(B)를 y의 왼쪽으로 이동 y y x / \ / \ / \ x C → B C , A B / \ A B 2단계: x를 y의 위치로 올리기 (x의 오른쪽 B를 Y로 변경) x / \ A y / \ B C 최종: x와 y의 관계가 바뀜 (y가 x의 오른쪽 자식)

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) 시간에 완료됨

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; y->Color = eColor::Black; z->Parent->Parent->Color = eColor::Red; z = z->Parent->Parent; } else { 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; // 루트는 항상 검은색 }

삽입 전: 삽입 후 수정: 조부모(⚫) 조부모(🔴) / \ / \ 부모(🔴) 삼촌(🔴) → 부모(⚫) 삼촌(⚫) / / z(🔴) z(🔴) 처리: 색상만 변경 (회전 없음) - 부모와 삼촌을 BLACK으로 - 조부모를 RED로 - z를 조부모로 이동하여 다시 검사

삽입 전: 좌회전 후: 조부모(⚫) 조부모(⚫) / / 부모(🔴) → z(🔴) \ / z(🔴) 부모(🔴) 처리: 좌회전으로 Case 3으로 변환 - 부모를 축으로 좌회전 - z를 부모 위치로 이동 - 이제 Case 3 상황이 됨

삽입 전: 우회전 + 색상 변경 후: 조부모(⚫) 부모(⚫) / / \ 부모(🔴) → z(🔴) 조부모(🔴) / z(🔴) 처리: 우회전 + 색상 변경 1. 부모를 BLACK으로 2. 조부모를 RED로 3. 조부모를 축으로 우회전

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