레드-블랙 트리의 특성(조건)
- 모든 노드는 적색이거나 흑색이다.
- 루트는 흑색이다.
- 모든 리프(NIL)는 흑색이다.
- 노드가 적색이면 그 노드의 자식은 모두 흑색이다.
- 각 노드로부터 그 노드의 자손인 리프로 가는 경로들은 모두 같은 수의 흑색 노드를 포함한다.
레드 블랙 트리는 자가 균형 이진 탐색트리이며, 각각의 노드는 적색 또는 흑색이다. 삽입 / 삭제 과정에서 이진 탐색트리의 특성을 보전하면서, 레드-블랙 트리의 특성 5가지를 만족할 수 있도록 트리를 구성한다.
특히, self-balncing 을 위한 과정을 크게 2가지로 볼 수 있다.
Rotation / Recolor
Rotation 을 통해 이진 탐색트리의 특성을 보전하면서 트리의 구조를 수정해 나갈 수 있고, 각각의 경우에 알맞게 Recolor 해주어 레드-블랙 트리의 특성을 만족시키도록 트리를 구성할 수 있다.
RB tree 의 삭제 과정과, 삭제 후에 delete_fix_up 과정을 거치면서 RB tree의 특성을 만족시키도록 수정하는 과정들을 확인하려고 한다.
삭제(deletion)
삭제 과정에서는 이진 탐색트리의 특성을 만족하면서 노드를 삭제할 것이다. 이후에 delete_fixup 과정에서 이진탐색트리의 특성과 RB 트리의 특성을 모두 만족시키기 위해 트리의 구조를 변형할 것이다.
삭제 과정에서 2가지 상황이 빈번하게 일어난다.
이를 함수화 시켜 놓은 것이 있는데, 슈도코드를 통해 그것을 먼저 검토하고, 삭제 과정을 살펴보겠다.
DELETE 슈도 코드
1. 이식(transplant)
삭제될 노드를 target 노드라고 하자, target 노드는 루트노드가 아니라면 parent 노드의 왼쪽 자식 혹은 오른쪽 자식일 것이다.
- 각각의 노드들은 parent, left, right, key, color 필드를 갖고있다. 이식 (transplant) 과정에서는, target 노드와 그 노드의 parent 노드의 연결관계만을 처리하는 과정이다.
- target 노드를 대체할 노드를 구했다고 가정하고, target의 parent 입장에서 왼쪽 자식이었는지, 오른쪽 자식이었는지 파악한 후에 그 자식을 대체할 노드로 지정하고 대체할 노드 또한 target의 parent를 부모노드로 지정하여 두 노드를 연결한다.
u : 삭제할 노드, v : 대체할 노드.
line 1 : if 삭제할 노드(u)의 부모노드가 nil 일 때,
-> 삭제할 노드가 루트노드라면,
line 2 : 트리의 루트노드를 대체할 노드(v)로 설정.
line 3 : else if 삭제할 노드(u)가 부모노드의 왼쪽 자식일 때,
line 4 : 삭제할 노드(u)의 왼쪽 자식을 대체할 노드(v)로 설정.
line 5 : else (삭제할 노드(u)가 부모노드의 오른쪽 자식일 때)
-> 삭제할 노드(u)의 오른쪽 자식을 대체할 노드(v)로 설정.
line 6 : 삭제할 노드(u)의 부모노드를 대체할 노드(v)의 부모노드로 설정.
2. 최소값의 노드 산출(tree_minimum)
tree_minimum 함수는 삭제할 노드의 위치를 대체할 노드를 산출한다.
키값이 10인 노드를 삭제할 때,
이진검색트리의 특성을 유지하면서 10을 대체할 수 있는 노드는 5, 14 다.
대체할 노드는 삭제될 노드10의 오른쪽 서브트리에서 가장 작은 값 또는 왼쪽 서브트리에서 가장 큰 값이다.
오른쪽 서브트리에서 가장 작은 값은 오른쪽 서브트리의 루트노드(16)에서 리프노드(nil)을 만나기 직전 노드인 14 이고,
왼쪽 서브트리에서 가장 큰 값은 왼쪽 서브트리의 루트노드(13)에서 리프노드(nil)을 만나기 직전 노드인 5이다.
둘중에 아무거나 써도 되는데, 오른쪽 서브트리의 minimum 값을 대체할 노드로 설정하였기 때문에, minimum 함수를 사용할 것이다.
step 1 : target 확인, target color 따로 저장.
target = 35노드.
- target = 35
- target-original-color = target -> color
-> 지워질 노드의 색을 변수에 저장해 놓는다.
step 2 : target의 자식 정보 확인.
- 삭제할 노드를 y에 복사하여 포인터처럼 활용하면서 쓸 것임(정보저장용, 활용성) -> 코드보면 이해됨.
- 대체할 노드를 x에 따로 저장해놓을 것임.(정보저장용)
step 3 :
- step 3 는 3가지 case 로 나뉜다.
- 예시는 case 1 에 해당한다.
case 1 : 왼쪽 자식이 없을 때 (자식이 둘다 없을 때도 해당된다)
> target의 오른쪽 자식을 x 로 설정.
> 오른쪽 자식을 target 노드에 이식한다 (transplant)
case 2 : 오른쪽 자식이 없을 때
> target의 왼쪽 자식을 x 로 설정.
> 왼쪽 자식을 target 노드에 이식한다 (transplant)
case 3 : 자식이 둘다 있을 때 (흐름을 위해 슈도코드로 대체)
삭제후 수정(delete_fix_up)
삭제과정 후에 여전히 이진 탐색트리의 특성(조건)은 만족한다. 만약 삭제과정에서 삭제된 노드가 적색이라면, 지워도 black height depth가 변화가 없기 때문에, 레드-블랙 트리 특성 5를 위반 하지 않는다. 따라서, 그 자리에 이식 과정만 거치면 된다.
-> 여기서 말하는 삭제된 노드는 case 1, case 2에만 해당.
-> case 3에서는, 대체될 노드를 target node의 색을 입히기 때문에 대체될 노드의 색이 fix_up에 들어갈 기준이 된다. (슈도코드 참고)
다시말하면, fix_up 과정은 삭제될 노드의 색이 black 일때만 해당된다.(case 3의 경우 대체될 노드, 정확히 말하면 대체될 노드의 색이 black, 대체될 노드의 오른쪽 자식색 또한 black 일 때)
fix_up 과정의 중심이 되는 노드는 x다.
case 1, case 2 에서 x 노드는 대체되는 노드이다.
case 3 에서 x 노드는 대체되는 노드의 오른쪽 자식이다.
+ 사실 delete_fix_up 과정에 처음 입력되는 노드들은 어떤 경우에도 리프노드(nil)이다.
이 사실을 발견하기 전까지 책의 내용을 받아들이는 것이 힘들었다...
이유를 잘 생각해보면 당연하다. 삭제 후 수정과정은 대체 할 노드의 색이 Black 일 때만 해당된다. 왜냐하면 대체하는 노드가 Red 라면 삭제될 노드에 키값만 바꿔준다면 대체될 노드가 Red 이기 때문에 대체될 노드가 루트 노드인 서브트리의 자식들만 잘 연결시켜주면 된다.(black height 안바뀜.)
(너무 설명하기가 어렵다..ㅠ)
case 3(차수가 2)의 간단한 예시를 생각해보면, 삭제 후 수정 과정은 대체할 노드가 흑색이고, 대체할 노드의 오른쪽 자식이 흑색일 때 실행한다. 하지만, 대체할 노드의 오른쪽 자식이 흑색인 것은 nil 을 제외하고 불가능하다.
대체할 노드는 삭제될 노드의 오른쪽 자식의 nil 노드 직전의 노드이다. 따라서 왼쪽 자식은 무저건 nil 노드 이기 때문에 오른쪽 자식이 nil 노드가 아닌 흑색이라면 레드 블랙트리의 특성을 만족하지 못한다. (대체할 노드의 왼쪽자식이 nil 이라면, black height = 0, 만약 오른쪽 자식이 검정색 노드라면 nil 노드까지의 black height 는 이미 1이상이므로, 특성을 위배)
따라서, 만약 대체될 노드의 왼쪽자식이 nil인데, 오른쪽자식이 black 이면 서브트리가 rb tree 를 이루지 못하고 있었다는 뜻이므로, 이러한 경우는 없다.
이처럼, case1,2,3 모두 하나씩 생각해보면 결국 fix_up 과정이 일어나는 경우, (루트노드의 색깔만 바꿔주는 경우 제외) delete_fix_up 과정에 제일 처음 입력되는 x 노드는 nil 노드라는 것을 확인하였다. (시간이 된다면 나중에 모든 경우에 대해 깔끔하게 정리해서 포스팅 해야겠다.)
Deletion fix up :
when : y-original color is black
while문 조건 : x 노드의 색이 블랙 또는 x가 루트가 아닐때.
while문 종료 후 : x 의 컬러를 블랙으로 칠함.
step 0 : 35를 삭제할 때!
y-original color = black, x = y-> right이므로 x = nil이며, x - color = black
delete_fix_up 에 들어간다.
Delete_fix_up 슈도 코드
step 1 : x 의 sibling 노드를 w에 저장.
w 는 60 이다.
case 1 : w (60) 가 적색 노드일 때.
(1) w 의 색깔과 x(nil)-> parent(50)의 색깔을 바꿔준다.
(2) x의 parent기준으로 좌회전!
(3) w를 x 의 parent의 오른쪽 자식으로 설정한다. (w = 55)결과 :
case 2 : w 의 왼쪽 자식과 오른쪽 자식이 모두 black일 때
(1) w색을 레드로 칠한다.
(2) x를 x의 parent 로 설정한다.(RB균형을 맞추도록 하면서 루트까지 올라갈 것임.)-> case 1 이후 w(55)의 왼쪽자식이 적색이므로 case2는 수행하지 않는다.
생각 할 것 : case 3의 경우 항상 case 4로 경유한다. (
case 3 : w의 왼쪽 자식이 red, w 의 오른쪽 자식이 black 일 때
(1) w의 왼쪽자식과 w의 색을 바꾼다.
(2) w에 대해서 우회전
(3) x 의 parent의 오른쪽 자식으로 w를 설정.
결과 :
-> x 는 nil(50->left), w는 53
case 4 : 위의 조건에 모두 해당하지 않는 경우. (w가 블랙, w의 오른쪽자식이 red)
-> case 3를 거치면 case 4의 형태로 바뀐다.
-> case 4를 거치면 fix_up 과정이 종료된다. (case 2를 거치고 종료되는 경우도 있다.)
(1) w(53) 의 색깔과 x(nil)-> parent(50)의 색깔을 바꿔준다.
(2) w의 오른쪽 자식의 색을 검정색으로 바꾼다.
(3) x의 parent 기준으로 좌회전!
(4) x를 root 로 설정(while문 탈출)결과 :
delete_fix_up 과정을 탈출하는 경우들을 간단하게 살펴보면,
- while -> case
-
case 1 :
-> case 2 -> ? (END or continue while)
-> case 3 -> case 4 (END) -
case 2 :
-> END
-> ?(while)
-
case 3 :
-> case 4 -> END
-
case 4 :
-> END
- while 해당안됨
- x 의 color 를 검정색으로 칠하고 종료.
전체 구현 코드는 다음과 같다.
#include "rbtree.h"
#include <stdlib.h>
rbtree *new_rbtree(void){
rbtree *p = (rbtree *)calloc(1, sizeof(rbtree));
node_t *NIL = (node_t *)calloc(1, sizeof(node_t));
p -> nil = NIL;
p -> root = NIL;
NIL -> color = RBTREE_BLACK;
return p;
}
void DeleteByPostOrder(node_t *root, rbtree *t){
if (root == t -> nil)
{
return;
}
DeleteByPostOrder(root -> left, t);
DeleteByPostOrder(root -> right, t);
free(root);
}
void delete_rbtree(rbtree *t){
// TODO: reclaim the tree nodes's memory
if (t == NULL)
{
return;
}
DeleteByPostOrder(t -> root, t);
free(t-> nil);
free(t);
}
void left_rotate(rbtree *t, node_t *x){
node_t *y;
y = x -> right;
x -> right = y -> left;
if (y -> left != t -> nil)
{
y -> left -> parent = x;
}
y -> parent = x -> parent;
if (x -> parent == t -> nil)
{
t -> root = y;
}
else if (x == x -> parent -> left)
{
x -> parent -> left = y;
}
else
{
x -> parent -> right = y;
}
y -> left = x;
x -> parent = y;
return;
}
void right_rotate(rbtree *t, node_t *x){
node_t *y;
y = x -> left;
x -> left = y -> right;
if (y -> right != t -> nil)
{
y -> right -> parent = x;
}
y -> parent = x -> parent;
if (x -> parent == t -> nil)
{
t -> root = y;
}
else if (x == x -> parent -> right)
{
x -> parent -> right = y;
}
else
{
x -> parent -> left = y;
}
y -> right = x;
x -> parent = y;
return;
}
void rb_insert_Fixup(rbtree *t, node_t *z){
node_t *uncle;
// while ((z != t->root) && (z->color != RBTREE_BLACK) && (z->parent->color == RBTREE_RED))
while (z->parent->color == RBTREE_RED)
{
if (z -> parent == z -> parent -> parent -> left)
{
uncle = z -> parent -> parent -> right;
//경우1
if (uncle -> color == RBTREE_RED)
{
z -> parent -> color = RBTREE_BLACK;
uncle -> color = RBTREE_BLACK;
z -> parent -> parent -> color = RBTREE_RED;
z = z -> parent -> parent;
}
//경우2
else {
if (z == z -> parent -> right)
{
z = z -> parent;
left_rotate(t, z);
}
//경우3
z -> parent -> color = RBTREE_BLACK;
z -> parent -> parent -> color = RBTREE_RED;
right_rotate(t, z -> parent -> parent);
}
}
//반대로
else
{
uncle = z -> parent -> parent -> left;
//경우1
if (uncle != t -> nil && uncle -> color == RBTREE_RED)
{
z -> parent -> color = RBTREE_BLACK;
uncle -> color = RBTREE_BLACK;
z -> parent -> parent -> color = RBTREE_RED;
z = z -> parent -> parent;
}
//경우2
else {
if (z == z -> parent -> left)
{
z = z -> parent;
right_rotate(t, z);
}
//경우3
if (z != t -> root && z -> parent != t -> root)
{
z -> parent -> color = RBTREE_BLACK;
z -> parent -> parent->color = RBTREE_RED;
left_rotate(t, z -> parent -> parent);
}
}
}
}
t -> root -> color = RBTREE_BLACK;
}
node_t *rbtree_insert(rbtree *t, const key_t key){
node_t *parent = t -> nil;
node_t *p = t -> root;
while (p != t -> nil)
{
parent = p;
if (p -> key > key)
{
p = p -> left;
}
else
{
p = p -> right;
}
}
node_t *new_node = (node_t *)calloc(1, sizeof(node_t));
new_node->parent = parent;
// 트리의 첫 노드일 때 - 루트가 된다
if (parent == t -> nil){
t -> root = new_node;
new_node -> color = RBTREE_BLACK;
}
//찾은 부모노드보다 새로운 노드가 작을때 - 왼쪽 자식으로
else if (key < parent -> key){
parent -> left = new_node;
new_node -> color = RBTREE_RED;
}
//크거나 같을때 - 오른쪽 자식으로
else{
parent -> right = new_node;
new_node -> color = RBTREE_RED;
}
//새로운 노드 설정
new_node -> key = key;
new_node -> left = t->nil;
new_node -> right = t->nil;
rb_insert_Fixup(t, new_node);
return t -> root;
}
node_t *rbtree_find(const rbtree *t, const key_t key){
// TODO: implement find
node_t *r = t -> root;
while (r != t -> nil)
{
if (r -> key == key)
return r;
else if (r -> key < key)
r = r -> right;
else
r = r -> left;
}
return NULL;
}
node_t *rbtree_min(const rbtree *t){
// TODO: implement find
node_t *r = t -> root;
if (r == t -> nil)
return r;
while (r -> left != t -> nil)
{
r = r -> left;
}
return r;
}
node_t *tree_minimum(const rbtree *t, node_t *sub_root){
// TODO: implement find
node_t *r = sub_root;
if (r == t -> nil)
return r;
while (r -> left != t -> nil)
{
r = r -> left;
}
return r;
}
node_t *rbtree_max(const rbtree *t){
// TODO: implement find
node_t *r = t -> root;
if (r == t -> nil)
return r;
while (r -> right != t -> nil)
{
r = r -> right;
}
return r;
}
void rb_transplant(rbtree *t, node_t *u, node_t *v){
if (u -> parent == t -> nil)
{
t -> root = v;
}
else if (u == u -> parent -> left)
{
u -> parent -> left = v;
}
else
u -> parent -> right = v;
v -> parent = u -> parent;
return;
}
void rb_delete_fixup(rbtree *t, node_t *x){
node_t *w;
while ((x != t -> root) && (x -> color == RBTREE_BLACK))
{
if (x == x -> parent -> left)
{
w = x -> parent -> right;
if (w -> color == RBTREE_RED)
{
w -> color = RBTREE_BLACK;
x -> parent -> color = RBTREE_RED;
left_rotate(t, x -> parent);
w = x -> parent -> right;
}
if (w -> left -> color == RBTREE_BLACK && w -> right -> color == RBTREE_BLACK)
{
w -> color = RBTREE_RED;
x = x -> parent;
}
else
{
if (w -> right -> color == RBTREE_BLACK)
{
w -> left -> color = RBTREE_BLACK;
w -> color = RBTREE_RED;
right_rotate(t, w);
w = x -> parent -> right;
}
w -> color = x -> parent -> color;
x -> parent -> color = RBTREE_BLACK;
w -> right -> color = RBTREE_BLACK;
left_rotate(t, x -> parent);
x = t->root;
}
}
else
{
w = x -> parent -> left;
if (w -> color == RBTREE_RED)
{
w -> color = RBTREE_BLACK;
x -> parent->color = RBTREE_RED;
right_rotate(t, x -> parent);
w = x -> parent->left;
}
if (w -> right -> color == RBTREE_BLACK && w -> left -> color == RBTREE_BLACK)
{
w -> color = RBTREE_RED;
x = x -> parent;
}
else
{
if (w -> left -> color == RBTREE_BLACK)
{
w -> right -> color = RBTREE_BLACK;
w -> color = RBTREE_RED;
left_rotate(t, w);
w = x -> parent -> left;
}
w -> color = x -> parent -> color;
x -> parent -> color = RBTREE_BLACK;
w -> left -> color = RBTREE_BLACK;
right_rotate(t, x -> parent);
x = t -> root;
}
}
}
x -> color = RBTREE_BLACK;
}
int rbtree_erase(rbtree *t, node_t *z){
node_t *y = z;
color_t y_orginal_color = y->color;
node_t *x;
if (z -> left == t -> nil)
{
x = z -> right;
rb_transplant(t, z, z -> right);
}
else if (z -> right == t -> nil)
{
x = z -> left;
rb_transplant(t, z, z -> left);
}
else
{
y = tree_minimum(t, z -> right);
y_orginal_color = y->color;
x = y -> right;
if (y -> parent == z)
{
x -> parent = y;
}
else
{
rb_transplant(t, y, y -> right);
y -> right = z -> right;
y -> right -> parent = y;
}
rb_transplant(t, z, y);
y -> left = z -> left;
y -> left -> parent = y;
y -> color = z -> color;
}
if (y_orginal_color == RBTREE_BLACK)
{
rb_delete_fixup(t, x);
}
free(z);
return 0;
}
int inorder_rbtree(node_t *root, key_t *res,const rbtree *t, int i){
if (root == t -> nil)
{
return i;
}
i = inorder_rbtree(root->left, res, t, i);
res[i] = root->key;
i += 1;
i = inorder_rbtree(root->right, res, t, i);
return i;
}
int rbtree_to_array(const rbtree *t, key_t *arr, const size_t n){
if (t->root == t->nil)
{
return -1;
}
inorder_rbtree(t->root, arr, t, 0);
return 0;
}느낀점
rb-tree에 대한 전반적인 이해, 메모리 할당, c언어의 자료구조에대해 전반적으로 어느정도 배우고 기초를 익힐 수 있는 계기였다. 특히, 팀워크가 얼마나 강력한 것인지 몸소 깨닫는 project 였다. 한 가지 뼈저리게 느낀 것은 블로그에 남기고 싶은 내용들이 많았는데, 구조적으로 정리해서 글을 써내려가는 것이 너무 어려웠다. 다음 프로젝트 때는 이러한 것들을 생각하고, 보완해나가야겠다.
