Red-Black 트리는 red-black properties를 모두 만족하는 이중 탐색 트리이다.
<red-black properties>
1. 모든 노드는 빨간색 혹은 검은색이다.
2. 루트노드는 검은색이다.
3. 모든 리프노드(NIL 노드)는 검은색이다.
4. 빨간색 노드의 자식은 검은색이다. (빨간색 노드가 연속적으로 존재할 수 없다.)
5. 임의의 노드에서 자손 NIL노드까지 가는 경로들의 black 수는 같다. (자기 자신은 카운트에서 제외)
Red-Black 트리도 BST의 한 종류이므로,
먼저 BST를 기본적으로 구현하되
(1) rbNode 구조체 멤버로 color와 parent를 추가한다.
(2) rbTree 구조체를 새롭게 도입하여 NIL 노드를 활용할 수 있도록 한다. (t->NIL->color = Black)
다음은 Insertion / Deletion 과정에서 노드의 색깔을 확인하고 조정하는 과정을 생략하고
기본 BST 구조대로 구현한 코드이다.
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
enum Color {Red, Black, DoubleBlack};
typedef struct rbNode{
int item;
int color;
struct rbNode* parent;
struct rbNode* left;
struct rbNode* right;
}rbNode;
typedef struct rbTree{
rbNode* root;
rbNode* NIL;
}rbTree;
rbTree* createTree(){
rbTree* newTree = (rbTree*)malloc(sizeof(rbTree));
if(newTree == NULL)
return NULL;
rbNode* NIL = (rbNode*)malloc(sizeof(rbNode));
if(NIL == NULL)
return NULL;
NIL->item = INT_MAX;
NIL->color = Black;
NIL->parent = NULL;
NIL->left = NULL;
NIL->right = NULL;
newTree->NIL = NIL;
newTree->root = NIL;
return newTree;
}
rbNode* createNode(rbTree* t, int data){
rbNode* newNode = (rbNode*)malloc(sizeof(rbNode));
if(newNode == NULL)
return NULL;
newNode->item = data;
newNode->color = Red;
newNode->parent = t->NIL;
newNode->left = t->NIL;
newNode->right = t->NIL;
return newNode;
}
// traverse
void traverse(rbTree* t, rbNode* root, int type){
// -1 : preorder, 0: inorder, 1: postorder
if(root == t->NIL)
return;
if(type == -1){
printf("item : %d \n", root->item);
printf("left : %d \n", root->left->item);
printf("right : %d \n", root->right->item);
root->parent != NULL ? printf("parent : %d\n", root->parent->item) : printf("parent : NULL\n");
printf("color : %d\n", root->color);
printf("------------\n");
traverse(t, root->left, -1);
traverse(t, root->right, -1);
}
else if(type == 0){
traverse(t, root->left, 0);
printf("item : %d \n", root->item);
printf("left : %d \n", root->left->item);
printf("right : %d \n", root->right->item);
root->parent != NULL ? printf("parent : %d\n", root->parent->item) : printf("parent : NULL\n");
printf("color : %d\n", root->color);
printf("------------\n");
traverse(t, root->right, 0);
}
else if(type == 1){
traverse(t, root->left, 1);
traverse(t, root->right, 1);
printf("item : %d \n", root->item);
printf("left : %d \n", root->left->item);
printf("right : %d \n", root->right->item);
root->parent != NULL ? printf("parent : %d\n", root->parent->item) : printf("parent : NULL\n");
printf("color : %d\n", root->color);
printf("------------\n");
}
}
// search
rbNode* findMin(rbTree* t, rbNode* root){
rbNode* curr = root;
if(curr == t->NIL)
return NULL;
while(curr->left != t->NIL){
curr = curr->left;
}
return curr;
}
rbNode* findMax(rbTree* t, rbNode* root){
rbNode* curr = root;
if(curr == t->NIL)
return NULL;
while(curr->right != t->NIL){
curr = curr->right;
}
return curr;
}
// rotate
// 기존 bst와 달리 parent를 신경써야 한다.
void rotateLeft(rbTree* t, rbNode* n){
rbNode* nR = n->right;
rbNode* nRL = nR->left;
// (1)
n->right = nRL;
if(nRL != t->NIL)
nRL->parent = n;
// (2)
nR->parent = n->parent;
if(n->parent == t->NIL)
t->root = nR;
else if(n->parent->left == n)
n->parent->left = nR;
else if(n->parent->right == n)
n->parent->right = nR;
// (3)
nR->left = n;
n->parent = nR;
}
void rotateRight(rbTree* t, rbNode* n){
rbNode* nL = n->left;
rbNode* nLR = nL->right;
// (1)
n->left = nLR;
if(nLR != t->NIL)
nLR->parent = n;
// (2)
nL->parent = n->parent;
if(n->parent == t->NIL)
t->root = nL;
else if(n->parent->right == n)
n->parent->right = nL;
else if(n->parent->left == n)
n->parent->left = nL;
// (3)
nL->right = n;
n->parent = nL;
}
int main(int argc, char* argv[]){
rbTree* t = createTree();
insert(t,7);
insert(t,3);
insert(t,18);
insert(t,10);
insert(t,22);
insert(t,8);
insert(t,11);
insert(t,26);
insert(t,2);
insert(t,6);
insert(t,13);
traverse(t, t->root, 0);
return 0;
}
Red-Black 트리 삽입
BST 삽입과정과 동일하게 진행하고, 새로 삽입되는 노드의 색깔은 빨간색으로 한다.
(Red-Black properties를 깨뜨리지 않게 하기 위해서이다.)
만약 새로 삽입되는 노드가 루트노드라면 검정색으로 바꾸어 준다.
- p가 Black인 경우 : 아무 것도 하지 않는다.
- p가 Red인 경우
- u가 Red인 경우 : g와 p,u의 색깔을 반대로 바꾸어 준다.
- u가 Black인 경우 : LL, LR, RR, RL -> 회전 후 색깔을 바꾸어 준다(p자리와 u자리의 색깔이 같도록).
// insert (iterative한 방식)
// recursive하게 구현하려면 파라미터가 너무 많이 필요하다.
void insertFixup(rbTree* t, rbNode* c){
rbNode *p, *g, *u;
// p가 red (p가 black인 경우:do nothing)
while(c->parent->color == Red){
p = c->parent;
g = p->parent;
// L-case
if(p == g->left){
u = g->right;
if(u->color == Red){
p->color = Black;
u->color = Black;
g->color = Red;
c = g;
}
else{
if(c == p->right){
// LR-Case
c = c->parent;
rotateLeft(t, c);
p = c->parent;
g = p->parent;
}
// LL-case
p->color = Black;
g->color = Red;
rotateRight(t, g);
c = p;
}
}
// R case
else if(p == g->right){
u = g->left;
if(u->color == Red){
p->color = Black;
u->color = Black;
g->color = Red;
c = g;
}
else{
if(c == p->left){
c = c->parent;
rotateRight(t, c);
p = c->parent;
g = p->parent;
}
p->color = Black;
g->color = Red;
rotateLeft(t, g);
c = p;
}
}
}
t->root->color = Black;
}
void insert(rbTree* t, int item){
rbNode* prev = t->NIL;
rbNode* curr = t->root;
rbNode* new = createNode(t, item);
while(curr != t->NIL){
prev = curr;
if(curr->item > item)
curr = curr->left;
else
curr = curr->right;
}
new->parent = prev;
if(prev == t->NIL)
t->root = new;
else if(prev->item > item)
prev->left = new;
else
prev->right = new;
insertFixup(t, new);
}
Red-Black 트리 삭제
삭제하려는 노드의 자녀 중 NIL노드가 하나 이상이라면
삭제되는 색 = 삭제되는 노드의 색
삭제하려는 노드의 자녀에 NIL노드가 없다면
삭제되는 색 = 삭제되는 노드의 최근접노드의 색
삭제되는 색이 Red라면 어떠한 속성도 위반하지 않는다.
삭제되는 색이 Black일 때만 확인해 주면 된다.
//delete (iterative)
void delete(rbTree* t, int data){
if(t->root == t->NIL)
return;
rbNode* prev = t->NIL;
rbNode* curr = t->root;
while(curr->item != data && curr != t->NIL){
prev = curr;
if(curr->item > data)
curr = curr->left;
else
curr = curr->right;
}
if(curr == t->NIL)
return;
else{
// curr->item == data
if(curr->left == t->NIL && curr->right == t->NIL){
if(prev->item > data){
prev->left = t->NIL;
free(curr);
}
else{
prev->right = t->NIL;
free(curr);
}
}
else if(curr->left == t->NIL){
if(prev->item > data){
prev->left = curr->right;
curr->right->parent = prev;
free(curr);
}
else{
prev->right = curr->right;
curr->right->parent = prev;
free(curr);
}
}
else if(curr->right == t->NIL){
if(prev->item > data){
prev->left = curr->left;
curr->left->parent = prev;
free(curr);
}
else{
prev->right = curr->left;
curr->left->parent = prev;
free(curr);
}
}
else{
// curr의 자식이 모두 NIL노드가 아닌 경우
rbNode* target = findMin(t, curr->right);
curr->item = target->item;
if(target->left == t->NIL && target->right == t->NIL){
if(target->parent->item > data){
target->parent->left = t->NIL;
free(target);
}
else{
target->parent->right = t->NIL;
free(target);
}
}
else if(target->left == t->NIL){
if(target->parent->item > data){
target->parent->left = target->right;
target->right->parent = target->parent;
free(target);
}
else{
target->parent->right = target->right;
target->right->parent = target->parent;
free(target);
}
}
else if(target->right == t->NIL){
if(target->parent->item > data){
target->parent->left = target->left;
target->left->parent = target->parent;
free(target);
}
else{
target->parent->right = target->left;
target->left->parent = target->parent;
free(target);
}
}
}
}
}