Red Black Tree
Red-Black Tree는 이진 검색 트리(Binary Search Tree)의 일종으로, 데이터를 저장하고 탐색하기 위한 자료구조입니다.
Red-Black Tree의 주요 특징은 다음과 같습니다.
- 각 노드는 Red 또는 Black의 색깔을 가지고 있습니다.
- Root 노드는 Black입니다.
- 모든 리프 노드(leaf node)는 Black입니다.
- Red 노드의 자식 노드들은 모두 Black입니다. 즉, Red 노드는 연속으로 나타날 수 없습니다. (Red -> Red -> Red X)
- 어떤 노드로부터 시작하는 모든 경로는 같은 수의 Black 노드를 가집니다.
이러한 특징들로 인해, Red-Black Tree는 균형잡힌 트리로서 탐색, 삽입, 삭제 연산의 최악 시간 복잡도가 O(log n)이 되도록 보장됩니다. 또한, 이진 검색 트리의 일종이기 때문에 데이터의 정렬된 저장이 가능하며, 범위 검색 등 다양한 기능을 제공할 수 있습니다.
Red-Black Tree의 삽입, 삭제 연산은 다소 복잡하지만, 적절한 알고리즘을 사용하면 비교적 빠르게 처리할 수 있습니다. 이러한 이유로, Red-Black Tree는 대용량 데이터의 검색, 정렬, 탐색 등에 널리 사용되고 있습니다.
Red Black Tree에서의 삽입 연산은 다음과 같은 과정을 거칩니다.
-
삽입할 노드를 적절한 위치에 삽입합니다. 이때, 이진 탐색 트리의 성질을 유지해야 합니다.
-
삽입된 노드를 레드 색으로 칠합니다.
-
만약 삽입된 노드의 부모 노드가 블랙 노드라면, 규칙을 위반하지 않으므로 삽입 과정을 마칩니다.
-
만약 삽입된 노드의 부모 노드가 레드 노드라면, 다음 규칙을 따릅니다.
-
삽입된 노드의 삼촌 노드가 레드 노드라면, 부모 노드와 삼촌 노드의 색을 블랙으로 변경합니다. 그리고 할아버지 노드의 색을 레드로 변경합니다. 그리고 할아버지 노드를 현재 노드로 설정하여 레드-블랙 트리 규칙을 위반하는 경우를 방지합니다.
-
삽입된 노드의 삼촌 노드가 블랙 노드이고, 현재 노드가 부모 노드의 오른쪽 자식이면, 부모 노드를 중심으로 좌회전을 수행합니다.
-
삽입된 노드의 삼촌 노드가 블랙 노드이고, 현재 노드가 부모 노드의 왼쪽 자식이면, 할아버지 노드를 블랙으로, 부모 노드를 레드로 변경한 후 할아버지 노드를 중심으로 우회전을 수행합니다.
-
Red Black Tree에서의 삭제 연산은 다음과 같은 과정을 거칩니다.
-
삭제할 노드의 자식 노드 수에 따라 삭제 방법이 달라집니다
-
자식 노드가 없는 경우 (leaf node): 노드를 그냥 삭제하면 됩니다.
-
자식 노드가 하나인 경우: 해당 노드를 삭제하고, 자식 노드를 부모 노드와 연결합니다.
-
자식 노드가 둘인 경우: 삭제할 노드의 오른쪽 서브트리에서 가장 작은 노드(successor)를 찾아 삭제할 노드와 교체합니다. 그리고 해당 successor 노드를 삭제합니다.
-
-
삭제 후에도 Red Black Tree의 규칙을 만족하도록 조정해야 합니다.
-
삭제할 노드가 블랙 노드인 경우: 블랙 노드를 삭제하면 해당 노드를 지나는 경로에서 블랙 노드의 개수가 달라지므로, Red Black Tree의 규칙이 깨집니다. 따라서, 블랙 노드를 삭제할 때는 삭제 후에 규칙을 만족하도록 트리를 재조정해야 합니다.
-
삭제할 노드가 레드 노드인 경우: 레드 노드를 삭제하면, 블랙 노드의 개수가 변하지 않으므로 규칙이 깨지지 않습니다. 따라서, 트리의 재조정이 필요하지 않습니다.
-
-
삭제 후에 규칙을 만족하도록 트리를 재조정합니다.
-
노드를 삭제한 후, 해당 노드를 지나는 경로의 블랙 노드 개수가 일정하지 않으면, Red Black Tree의 규칙이 깨집니다. 이러한 상황을 해결하기 위해 블랙 노드의 개수를 맞추는 작업이 필요합니다. 블랙 노드 개수를 맞추기 위해 노드를 재배치하거나 색상을 변경합니다.
-
삭제된 노드의 위치에 따라 노드의 부모, 조부모, 형제 노드를 이용하여 트리를 재조정합니다. 경우에 따라서는 루트 노드가 바뀔 수도 있습니다.
-
다음은 C언어로 Red Black Tree를 구현한 코드입니다
#include <stdio.h>
#include <stdlib.h>
enum Color {
RED,
BLACK
};
struct Node {
int data;
struct Node *parent, *left, *right;
enum Color color;
};
typedef struct Node Node;
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->parent = NULL;
newNode->left = newNode->right = NULL;
newNode->color = RED;
return newNode;
}
void swapColors(Node* a, Node* b) {
enum Color temp;
temp = a->color;
a->color = b->color;
b->color = temp;
}
void rotateLeft(Node** root, Node* node) {
Node* rightChild = node->right;
node->right = rightChild->left;
if (node->right != NULL)
node->right->parent = node;
rightChild->parent = node->parent;
if (node->parent == NULL)
*root = rightChild;
else if (node == node->parent->left)
node->parent->left = rightChild;
else
node->parent->right = rightChild;
rightChild->left = node;
node->parent = rightChild;
}
void rotateRight(Node** root, Node* node) {
Node* leftChild = node->left;
node->left = leftChild->right;
if (node->left != NULL)
node->left->parent = node;
leftChild->parent = node->parent;
if (node->parent == NULL)
*root = leftChild;
else if (node == node->parent->left)
node->parent->left = leftChild;
else
node->parent->right = leftChild;
leftChild->right = node;
node->parent = leftChild;
}
void fixViolation(Node** root, Node* node) {
Node* parent = NULL;
Node* grandparent = NULL;
while (node != *root && node->color != BLACK && node->parent->color == RED) {
parent = node->parent;
grandparent = parent->parent;
if (parent == grandparent->left) {
Node* uncle = grandparent->right;
if (uncle != NULL && uncle->color == RED) {
grandparent->color = RED;
parent->color = BLACK;
uncle->color = BLACK;
node = grandparent;
} else {
if (node == parent->right) {
rotateLeft(root, parent);
node = parent;
parent = node->parent;
}
rotateRight(root, grandparent);
swapColors(parent, grandparent);
node = parent;
}
} else {
Node* uncle = grandparent->left;
if (uncle != NULL && uncle->color == RED) {
grandparent->color = RED;
parent->color = BLACK;
uncle->color = BLACK;
node = grandparent;
} else {
if (node == parent->left) {
rotateRight(root, parent);
node = parent;
parent = node->parent;
}
rotateLeft(root, grandparent);
swapColors(parent, grandparent);
node = parent;
}
}
}
Red Black Tree를 공부하면서 어려웠던 점은, 이진 탐색 트리의 구조를 이해하고 그 위에 더해지는 Red Black Tree의 복잡한 규칙과 조건들이었습니다. 특히, 노드 삽입과 삭제의 경우에는 여러 가지 경우의 수를 고려해야 하며, 규칙에 어긋나는 경우에는 회전 연산을 통해 균형을 맞추어 주어야 했습니다. 이런 과정에서 많은 에러와 디버깅이 필요했고, 이 과정에서 얻은 지식과 경험은 저에게 큰 도움이 되었습니다.
또한, Red Black Tree를 구현하면서 자료구조가 매우 유용하고 효율적이라는 것입니다. 이진 탐색 트리에서 발생하는 불균형성을 보완하고, 탐색, 삽입, 삭제 연산의 시간 복잡도를 O(log n)으로 유지할 수 있기 때문입니다. 이러한 이점을 활용하여, Red Black Tree를 적절하게 적용하면 데이터 구조의 성능을 향상시킬 수 있습니다.
