레드-블랙 트리 소개

이진 검색 트리 근본적인 데이터 구조, 그러나 트리의 균형이 맞지 않으면 성능이 저하될 수 있습니다. 레드 블랙 트리 은 일종의 균형 이진 검색 트리 균형을 유지하기 위해 일련의 규칙을 사용하여 다음과 같은 작업에 대한 로그 시간 복잡성을 보장합니다. 삽입, 삭제, 검색 , 나무의 초기 모양에 관계없이. 레드 블랙 트리 각 수정 후 트리를 조정하기 위해 간단한 색상 코딩 방식을 사용하여 자체 균형을 유지합니다.

레드-블랙 트리

내용의 테이블

레드-블랙 트리란 무엇입니까?
레드-블랙 트리의 속성
레드-블랙 트리의 예
왜 레드-블랙 트리인가?
AVL 트리와의 비교:
Red-Black Tree의 흥미로운 점:
레드-블랙 트리의 기본 작업:
1. 삽입
2. 검색
3. 삭제
4. 회전

왼쪽 회전
오른쪽 회전

언제 회전을 수행해야 합니까?
레드-블랙 트리 구현:
레드-블랙 트리의 장점:
레드-블랙 트리의 단점:
레드-블랙 트리의 응용:

레드-블랙 트리란 무엇입니까?

ㅏ 레드-블랙 트리 자기 균형이다 이진 검색 트리 여기서 각 노드에는 추가 속성인 색상이 있습니다. 빨간색 또는 검은색 . 이러한 트리의 주요 목적은 삽입 및 삭제 중에 균형을 유지하여 효율적인 데이터 검색 및 조작을 보장하는 것입니다.

레드-블랙 트리의 속성

ㅏ 레드-블랙 트리 다음과 같은 속성을 가지고 있습니다:

노드 색상 : 각 노드는 빨간색이거나 검은색 .
루트 속성 : 트리의 루트는 항상 검은색 .
레드 프로퍼티 : 레드 노드는 레드 자식을 가질 수 없습니다(어떤 경로에도 두 개의 연속된 레드 노드는 없습니다).
블랙 프로퍼티 : 노드에서 그 하위 널 노드(리프)까지의 모든 경로는 동일한 수의 널 노드를 가집니다. 검은색 노드.
리프 속성 : 모든 리프(NIL 노드)는 검은색 .

이러한 속성은 루트에서 리프까지의 가장 긴 경로가 최단 경로의 두 배를 넘지 않도록 하여 트리의 균형과 효율적인 성능을 유지합니다.

레드-블랙 트리의 예

그만큼 올바른 레드-블랙 트리 위 이미지에서는 루트에서 리프 노드까지의 모든 경로에 동일한 수의 검정색 노드가 있음을 보장합니다. 이 경우 1개가 있습니다(루트 노드 제외).

그만큼 잘못된 레드 블랙 트리 빨간색-검정색 속성을 따르지 않습니다. 두 개의 빨간색 노드 서로 인접해 있습니다. 또 다른 문제는 리프 노드로 향하는 경로 중 하나에는 블랙 노드가 없고 나머지 두 개에는 블랙 노드가 있다는 것입니다.

왜 레드-블랙 트리인가?

대부분의 BST 작업(예: 검색, 최대값, 최소값, 삽입, 삭제 등)에는 오) h가 높이인 시간 BST . 이러한 작업의 비용은 다음과 같습니다. 에) 비뚤어진 이진 트리. 나무의 높이가 그대로 유지되는지 확인하면 O(로그 n) 모든 삽입 및 삭제 후에는 다음의 상한을 보장할 수 있습니다. O(로그 n) 이 모든 작업에 대해. 레드-블랙 트리의 높이는 항상 O(로그 n) 여기서 n은 트리의 노드 수입니다.

아니요.	연산	시간 복잡도
1.	찾다	O(로그 n)
2.	끼워 넣다	O(로그 n)
삼.	삭제	O(로그 n)

비교 AVL 트리 :

AVL 트리는 Red-Black 트리에 비해 균형이 더 잘 잡혀 있지만 삽입 및 삭제 중에 더 많은 회전이 발생할 수 있습니다. 따라서 애플리케이션에 삽입과 삭제가 자주 발생하는 경우 Red-Black 트리가 선호됩니다. 삽입 및 삭제 빈도가 낮고 검색 작업이 더 빈번한 경우 AVL 트리 Red-Black Tree보다 선호되어야 합니다.

Red-Black Tree는 어떻게 균형을 보장합니까?

균형을 이해하는 간단한 예는 Red-Black 트리에서 3개 노드의 체인이 불가능하다는 것입니다. 우리는 어떤 색상 조합이라도 시도해 보고 모든 색상이 Red-Black 트리 속성을 위반하는지 확인할 수 있습니다.

마지막 커밋 실행 취소

3개 노드로 구성된 레드-블랙 트리의 올바른 구조

Red-Black Tree의 흥미로운 점:

그만큼 검은색 레드-블랙 트리의 높이는 루트 노드에서 리프 노드까지의 경로에 있는 블랙 노드의 수입니다. 리프 노드도 다음과 같이 계산됩니다. 검은색 노드. 그래서, 높이가 높은 레드-블랙 트리 시간 가지다 검정색 높이>= h/2 .
레드-블랙 트리의 높이 N 노드는 h<= 2 로그 ₂ (n + 1) .
모든 리프(NIL)는 검은색 .
그만큼 검은색 노드의 깊이는 루트에서 해당 노드까지의 검은색 노드 수, 즉 검은색 조상의 수로 정의됩니다.

레드-블랙 트리의 기본 작업:

Red-Black Tree의 기본 작업은 다음과 같습니다.

삽입
찾다
삭제
회전

1. 삽입

레드-블랙 트리에 새 노드를 삽입하려면 두 단계 프로세스가 필요합니다. BST(이진 검색 트리) 삽입 , Red-Black 속성 위반을 수정합니다.

삽입 단계

BST 삽입 : 표준 BST처럼 새 노드를 삽입합니다.
위반 수정 :
- 새 노드의 부모가 검은색 , 위반된 속성은 없습니다.
- 부모가 빨간색 , 나무가 빨간색 속성을 위반하여 수정이 필요할 수 있습니다.

삽입 중 위반 수정

새 노드를 삽입한 후 빨간색 노드의 부모와 삼촌(부모의 형제)의 색상에 따라 여러 가지 경우가 발생할 수 있습니다.

사례 1: 삼촌은 빨간색이다 : 부모와 삼촌을 다시 칠해 보세요. 검은색 , 그리고 조부모님은 빨간색 . 그런 다음 트리 위로 이동하여 추가 위반 사항을 확인합니다.
사례 2: 삼촌은 흑인이다 :
- 하위 사례 2.1: 노드는 오른쪽 자식입니다. : 상위 항목에 대해 왼쪽 회전을 수행합니다.
- 하위 사례 2.2: 노드는 왼쪽 자식입니다. : 조부모에 대해 오른쪽 회전을 수행하고 적절하게 다시 칠합니다.

2. 검색

Red-Black Tree에서 노드를 검색하는 것은 표준에서 검색하는 것과 유사합니다. 이진 검색 트리(BST) . 검색 작업은 다음에서 간단한 경로를 따릅니다. 뿌리 에 잎 , 목표 값을 현재 노드의 값과 비교하고 그에 따라 왼쪽 또는 오른쪽으로 이동합니다.

검색 단계

루트에서 시작 : 루트 노드에서 검색을 시작합니다.
트리 탐색 :
- 대상 값이 현재 노드의 값과 같으면 해당 노드를 찾습니다.
- 대상 값이 현재 노드의 값보다 작으면 왼쪽 자식으로 이동합니다.
- 대상 값이 현재 노드의 값보다 크면 오른쪽 자식으로 이동합니다.
반복하다 : 목표 값을 찾거나 NIL 노드에 도달할 때까지(값이 트리에 없음을 나타냄) 이 프로세스를 계속합니다.

삼. 삭제

Red-Black Tree에서 노드를 삭제하려면 BST 삭제를 수행한 다음 발생하는 모든 위반 사항을 수정하는 2단계 프로세스가 필요합니다.

삭제 단계

BST 삭제 : 표준 BST 규칙을 사용하여 노드를 제거합니다.
더블 블랙 수정 :
- 블랙 노드가 삭제되면 이중 블랙 상태가 발생할 수 있으며, 이에 대한 특정 수정이 필요합니다.

삭제 중 위반 사항 수정

검정색 노드가 삭제되면 형제의 색상과 자식의 색상을 기반으로 이중 검정색 문제를 처리합니다.

사례 1: 형제는 빨간색입니다. : 부모를 회전하고 형제와 부모의 색상을 다시 지정합니다.
사례 2: 형제자매가 흑인이다 :
- 하위 사례 2.1: 형제자매의 자녀는 흑인입니다. : 형제를 다시 색칠하고 이중 검정색을 위쪽으로 전파합니다.
- 하위 사례 2.2: 형제자매의 자녀 중 적어도 한 명은 빨간색입니다. :
  - 형제의 먼 아이가 빨간색인 경우 : 부모와 형제에 대해 회전을 수행하고 적절하게 다시 칠합니다.
  - 형제자매의 가까운 아이가 빨간색인 경우 : 형제와 그 자식을 회전시킨 후 위와 같이 처리합니다.

4. 회전

회전은 RBT(Red-Black Tree)의 균형 잡힌 구조를 유지하는 기본 작업입니다. 이는 루트에서 리프까지의 가장 긴 경로가 가장 짧은 경로 길이의 두 배를 넘지 않도록 하여 트리의 속성을 보존하는 데 도움이 됩니다. 회전에는 두 가지 유형이 있습니다. 왼쪽 회전 그리고 오른쪽 회전.

1. 왼쪽 회전

노드 𝑥에서 왼쪽 회전 엑스 움직여 𝑥 엑스 왼쪽 아래로, 오른쪽으로 자식 𝑦 그리고 𝑥까지 가져가세요 엑스 의 장소.

왼쪽 회전 시각화

 Before Rotation:  x      y   /    a b  After Left Rotation:  y  /   x b  /  a>

왼쪽 회전 단계:

세트 그리고 올바른 자녀가 되려면 엑스 .
이동하다 그리고 의 왼쪽 하위 트리 엑스 의 오른쪽 하위 트리입니다.
상위 업데이트 엑스 그리고 그리고 .
업데이트 엑스 의 부모가 가리킬 그리고 대신에 엑스 .
세트 그리고 의 왼쪽 아이는 엑스 .
업데이트 엑스 의 부모는 그리고 .

왼쪽 회전의 의사 코드:

왼쪽 회전

 // Utility function to perform left rotation void leftRotate(Node* x) {  Node* y = x->오른쪽;  x->오른쪽 = y->왼쪽;  if (y->왼쪽 != NIL) { y->왼쪽->부모 = x;  } y->부모 = x->부모;  if (x->parent == nullptr) { 루트 = y;  } else if (x == x->부모->왼쪽) { x->부모->왼쪽 = y;  } else { x->부모->오른쪽 = y;  } y->왼쪽 = x;  x->부모 = y; }>

2. 오른쪽 회전

노드 𝑥에서 오른쪽 회전 엑스 움직여 𝑥 엑스 오른쪽 아래로, 왼쪽으로 𝑦 그리고 𝑥까지 가져가세요 엑스 의 장소.

오른쪽 회전 시각화:

 Befor Right Rotation:   x  /  y  /   a b After Right Rotation:  y  /   a x  /  b>

오른쪽 회전 단계:

세트 그리고 의 왼쪽 자식이 되다 엑스 .
이동하다 그리고 의 오른쪽 하위 트리 엑스 의 왼쪽 하위 트리.
상위 업데이트 엑스 그리고 그리고 .
업데이트 엑스 의 부모가 가리킬 그리고 대신에 엑스 .
세트 그리고 의 올바른 아이 엑스 .
업데이트 엑스 의 부모는 그리고 .

오른쪽 회전의 의사 코드:

C++

 // Utility function to perform right rotation void rightRotate(Node* x) {  Node* y = x->왼쪽;  x->왼쪽 = y->오른쪽;  if (y->right != NIL) { y->right->parent = x;  } y->부모 = x->부모;  if (x->parent == nullptr) { 루트 = y;  } else if (x == x->부모->오른쪽) { x->부모->오른쪽 = y;  } else { x->부모->왼쪽 = y;  } y->오른쪽 = x;  x->부모 = y; }>

언제 회전을 수행해야 합니까?

레드-블랙 트리의 회전은 일반적으로 트리의 속성을 유지하기 위해 삽입 및 삭제 중에 수행됩니다. 다음은 순환에 대한 시나리오입니다.

1. 삽입 후 위반 수정

새 노드가 삽입되면 항상 빨간색으로 표시됩니다. 이로 인해 특히 다음과 같은 Red-Black Tree 속성 위반이 발생할 수 있습니다.

xd xd 의미

루트는 다음과 같아야 합니다. 검은색 .
빨간색 노드는 가질 수 없습니다 빨간색 어린이들.

삽입 수정 사례 분석:

사례 1: 다시 칠하기 및 위쪽으로 전파
- 새 노드의 부모와 삼촌이 모두인 경우 빨간색 , 부모와 삼촌을 다시 칠해 보세요. 검은색 , 그리고 조부모님은 빨간색 . 그런 다음 수정 사항을 조부모에게 재귀적으로 적용합니다.
사례 2: 회전 및 다시 칠하기
- 새 노드의 삼촌이 검은색 새 노드가 왼쪽 자식의 오른쪽 자식이면(또는 그 반대) 회전을 수행하여 새 노드를 위로 이동하고 정렬합니다.
- 새 노드의 삼촌이 검은색 새 노드는 왼쪽 자식의 왼쪽 자식(또는 오른쪽의 오른쪽)인 경우 회전을 수행하고 부모와 조부모의 색상을 다시 지정하여 위반을 수정합니다.

2. 삭제 후 위반사항 수정

삭제 후 속성을 복원하려면 트리를 수정해야 할 수 있습니다.

블랙 노드가 제거되거나 레드 노드가 블랙 노드로 교체되면 이중 블랙 상황이 발생할 수 있습니다.

삭제 수정을 위한 사례 분석:

사례 1: 형제는 빨간색입니다.
- 형제와 부모의 색상을 다시 지정하고 회전을 수행합니다.
사례 2: 형제자매는 흑인 자녀를 둔 흑인이다
- 형제를 빨간색으로 다시 칠하고 문제를 부모에게로 옮깁니다.
사례 3: 형제자매는 적어도 한 명의 빨간색 자녀를 둔 흑인입니다.
- 이중 검정색 문제를 해결하려면 회전하고 다시 칠해 보세요.

레드-블랙 트리 구현:

삽입, 검색, 회전 기능을 포함한 Red-Black Tree의 상세한 구현은 다음과 같습니다.

C++

 #include  using namespace std; // Node structure for the Red-Black Tree struct Node {  int data;  string color;  Node *left, *right, *parent;  Node(int data)  : data(data)  , color('RED')  , left(nullptr)  , right(nullptr)  , parent(nullptr)  {  } }; // Red-Black Tree class class RedBlackTree { private:  Node* root;  Node* NIL;  // Utility function to perform left rotation  void leftRotate(Node* x)  {  Node* y = x->오른쪽;  x->오른쪽 = y->왼쪽;  if (y->왼쪽 != NIL) { y->왼쪽->부모 = x;  } y->부모 = x->부모;  if (x->parent == nullptr) { 루트 = y;  } else if (x == x->부모->왼쪽) { x->부모->왼쪽 = y;  } else { x->부모->오른쪽 = y;  } y->왼쪽 = x;  x->부모 = y;  } // 오른쪽 회전을 수행하는 유틸리티 함수 void rightRotate(Node* x) { Node* y = x->left;  x->왼쪽 = y->오른쪽;  if (y->right != NIL) { y->right->parent = x;  } y->부모 = x->부모;  if (x->parent == nullptr) { 루트 = y;  } else if (x == x->부모->오른쪽) { x->부모->오른쪽 = y;  } else { x->부모->왼쪽 = y;  } y->오른쪽 = x;  x->부모 = y;  } // 삽입 후 레드-블랙 트리 속성을 수정하는 함수 // 삽입 void fixInsert(Node* k) { while (k != root && k->parent->color == 'RED') { if (k->parent == k->부모->부모->왼쪽) { 노드* u = k->부모->부모->오른쪽; // 삼촌 if (u->color == 'RED') { k->parent->color = 'BLACK';  u->색상 = '검정색';  k->부모->부모->색상 = '빨간색';  k = k->부모->부모;  } else { if (k == k->부모->오른쪽) { k = k->부모;  왼쪽회전(k);  } k->부모->색상 = 'BLACK';  k->부모->부모->색상 = '빨간색';  rightRotate(k->부모->부모);  } } else { 노드* u = k->부모->부모->왼쪽; // 삼촌 if (u->color == 'RED') { k->parent->color = 'BLACK';  u->색상 = '검정색';  k->부모->부모->색상 = '빨간색';  k = k->부모->부모;  } else { if (k == k->부모->왼쪽) { k = k->부모;  오른쪽회전(k);  } k->부모->색상 = 'BLACK';  k->부모->부모->색상 = '빨간색';  leftRotate(k->부모->부모);  } } } 루트->색상 = 'BLACK';  } // 중위 순회 도우미 함수 void inorderHelper(Node* node) { if (node != NIL) { inorderHelper(node->left);  시합<< node->데이터<< ' ';  inorderHelper(node->오른쪽);  } } // 검색 도우미 함수 Node* searchHelper(Node* node, int data) { if (node == NIL || data == node->data) { return node;  } if(데이터< node->data) { return searchHelper(node->left, data);  } return searchHelper(node->right, data);  } 공개: // 생성자 RedBlackTree() { NIL = new Node(0);  NIL->색상 = 'BLACK';  NIL->왼쪽 = NIL->오른쪽 = NIL;  루트 = NIL;  } // 함수 삽입 void insert(int data) { Node* new_node = new Node(data);  new_node->left = NIL;  new_node->right = NIL;  노드* 상위 = nullptr;  노드* 현재 = 루트;  // BST 삽입 while (current != NIL) { parent = current;  if(new_node->데이터< current->데이터) { 현재 = 현재->왼쪽;  } else { 현재 = 현재->오른쪽;  } } new_node->parent = 부모;  if (부모 == nullptr) { 루트 = new_node;  } else if(new_node->데이터< parent->데이터) { 부모->왼쪽 = new_node;  } else { 부모->오른쪽 = new_node;  } if (new_node->parent == nullptr) { new_node->color = 'BLACK';  반품;  } if (new_node->parent->parent == nullptr) { return;  } fixInsert(new_node);  } // 중위순회 void inorder() { inorderHelper(root); } // 검색 함수 Node* search(int data) { return searchHelper(root, data);  } }; int main() { RedBlackTree rbt;  // 요소 삽입 rbt.insert(10);  rbt.insert(20);  rbt.insert(30);  rbt.insert(15);  // 중위 순회 cout<< 'Inorder traversal:' << endl;  rbt.inorder(); // Output: 10 15 20 30  // Search for a node  cout << '
Search for 15: '  << (rbt.search(15) != rbt.search(0))  << endl; // Output: 1 (true)  cout << 'Search for 25: '  << (rbt.search(25) != rbt.search(0))  << endl; // Output: 0 (false)  return 0; }>

레드-블랙 트리의 장점:

균형이 잡힌: 레드-블랙 트리는 자체 균형을 유지합니다. 즉, 왼쪽 하위 트리와 오른쪽 하위 트리 높이 간의 균형을 자동으로 유지합니다. 이는 최악의 경우 검색, 삽입 및 삭제 작업에 O(log n) 시간이 걸리는 것을 보장합니다.
효율적인 검색, 삽입, 삭제: 균형 잡힌 구조로 인해 Red-Black Tree는 효율적인 운영을 제공합니다. 최악의 경우 검색, 삽입, 삭제 모두 O(log n) 시간이 소요됩니다.
구현이 간단함: 레드-블랙 트리 속성을 유지하기 위한 규칙은 비교적 간단하고 구현하기 쉽습니다.
광대하게 사용 된: 레드-블랙 트리는 맵, 세트, 우선순위 큐와 같은 다양한 데이터 구조를 구현하는 데 널리 사용됩니다.

레드-블랙 트리의 단점:

다른 균형 트리보다 더 복잡합니다. AVL 트리와 같은 단순한 균형 트리에 비해 Red-Black 트리는 삽입 및 삭제 규칙이 더 복잡합니다.
지속적인 오버헤드: 레드-블랙 트리 속성을 유지하면 모든 삽입 및 삭제 작업에 약간의 오버헤드가 추가됩니다.
모든 사용 사례에 최적이지는 않습니다. Red-Black Tree는 대부분의 작업에 효율적이지만 지속적인 오버헤드가 커질 수 있으므로 자주 삽입하고 삭제해야 하는 응용 프로그램에는 최선의 선택이 아닐 수 있습니다.

레드-블랙 트리의 응용:

맵 및 세트 구현: 레드-블랙 트리는 효율적인 검색, 삽입 및 삭제가 중요한 맵과 세트를 구현하는 데 자주 사용됩니다.
우선순위 대기열: Red-Black Tree는 우선순위에 따라 요소가 정렬되는 우선순위 대기열을 구현하는 데 사용할 수 있습니다.
파일 시스템: 레드-블랙 트리는 일부 파일 시스템에서 파일 및 디렉터리 구조를 관리하는 데 사용됩니다.
인메모리 데이터베이스: 레드-블랙 트리는 때때로 데이터를 효율적으로 저장하고 검색하기 위해 메모리 내 데이터베이스에서 사용됩니다.
그래픽 및 게임 개발: Red-Black Trees는 그래픽과 게임에 사용될 수 있습니다. 개발 충돌 감지 및 경로 찾기와 같은 작업에 사용됩니다.

레드-블랙 트리에 대한 자주 묻는 질문(FAQ):

1. 레드-블랙 트리란 무엇입니까?

레드-블랙 트리(Red-Black Tree)는 왼쪽과 오른쪽 하위 트리의 높이 사이의 균형을 유지하는 자체 균형 이진 검색 트리입니다. 이는 최악의 경우 검색, 삽입 및 삭제 작업에 O(log n) 시간이 걸리는 것을 보장합니다. 레드-블랙 트리는 효율적인 데이터 구조가 필요한 다양한 애플리케이션에 널리 사용됩니다.

2. 레드-블랙 트리는 어떻게 균형을 유지합니까?

레드-블랙 트리는 노드 색상(RED 또는 BLACK)과 노드 간의 관계에 특정 규칙을 적용하여 균형을 유지합니다. 이러한 규칙은 트리가 균형을 유지하고 왼쪽 및 오른쪽 하위 트리 간의 높이 차이가 최대 1이 되도록 보장합니다.

3. 레드-블랙 트리를 사용하면 어떤 이점이 있나요?

균형이 잡힌: 레드-블랙 트리는 자체 균형을 유지하여 효율적인 검색, 삽입 및 삭제 작업을 보장합니다.
효율적인: 대부분의 작업에 대해 O(log n) 시간 복잡도를 제공합니다.
구현이 간단함: 레드-블랙 트리 속성을 유지하는 규칙은 비교적 간단합니다.
광대하게 사용 된: 다양한 데이터 구조와 알고리즘을 구현하는 데 널리 사용됩니다.

4. 레드-블랙 트리를 사용하면 어떤 단점이 있나요?

AVL 트리와 같은 단순한 균형 트리에 비해 Red-Black 트리는 삽입 및 삭제 규칙이 더 복잡합니다.
레드-블랙 트리 속성을 유지하면 모든 삽입 및 삭제 작업에 약간의 오버헤드가 추가됩니다.
삽입과 삭제가 자주 발생하는 애플리케이션의 경우 다른 균형 트리 구조가 더 적합할 수 있습니다.

5. 레드-블랙 트리의 일반적인 응용 분야는 무엇입니까?

맵 및 세트 구현
우선순위 대기열
파일 시스템
인메모리 데이터베이스
그래픽 및 게임 개발(충돌 감지, 경로 찾기)

DSA의 레드-블랙 트리 정의 및 의미
자체 균형 이진 검색 트리
레드 블랙 트리와 AVL 트리
힙과 레드-블랙 트리의 차이점은 무엇입니까?
레드-블랙 트리에 삽입
레드-블랙 트리에서 삭제
레드-블랙 나무 | 하향식 삽입