앞의 RB_tree 이후에서 내용을 이어감
Nil 노드의 필요성
- Nil 은 한계조건을 간단하게 해주는 역할을 함
- Root의 parent 도 nil로 연결되고
- 가장 마지막 자식의 child도 nil로 처리됨
- 이를 이용하여 head의 정보와 끝나는 정보를 가질 수 있음
- 즉, 한계조건을 다루기 편해짐!
트리 내 각각의 NIL을 사용하지 않고 하나의 경계 노드 T->nil을 두어서 모든 NIL을 표현한다
from Introduction to Algorithms (CLRS)
Rotation
새로운 노드가 진입을 하면 RB tree의 규칙을 위반하는 경우가 있음.
이를 수정하기 위해서 트리 내의 일부 노드들의 색과 포인터를 변경한다
이 변경을 위해서 rotate를 사용
rotation을 사용할때 두 종류의 회전(좌회전, 우회전)을 보여줌
이때, 노드 x에 대해서 좌회전을 적요할 때 오른쪽 자식 y은 T->nil이 아니라고 가정
root의 부모는 T->nil 이라고 가정
// 좌 회전
void Left_Rotate(rbtree *t, node_t* x){
node_t* y=x->right; // y는 x의 오른쪽 child
x->right=y->left; // x의 오른쪽 child = y의 left child로 변경
if (y->left!= t->nil) // y 의 left child가 NULL이 아닐때
y->left->parent=x; // y의 left child의 parent를 x로 옮김
y->parent=x->parent; // y의 parent 에는 x의 parent를 넣음
if(x->parent==t->nil) // x의 parent가 NULL 이면
t->root=y; // x가 root라는거니깐 t에 y를 바로 넣음
else if(x==x->parent->left) // x가 x의 parent의 left child이면
x->parent->left=y; // 거기에 y를 넣음
else // x가 parent의 right child 이면
x->parent->right=y; // 거기에 y를 넣음
y->left=x; // y의 left child에 x를 넣음
x->parent=y; // x의 parent는 y가 됨
} // 이 순서를 통해서 x가 부모이고 y가 right child 였던게 y가 부모가 되고 x가 left child 로 변경됨
//우 회전
void right_Rotate(rbtree *t, node_t* y){ // 기준이 y node
node_t* x=y->left; // x 노드가 y의 left child이고 x를 parent로 y를 child로
y->left=x->right;
if (x->right!=t->nil)
x->right->parent=y;
x->parent=y->parent;
if(y->parent==t->nil)
t->root=x;
else if(y==y->parent->left)
y->parent->left=x;
else
y->parent->right=x;
x->right=y;
y->parent=x;
}Insert
n개의 노드로 이루어진 RB tree에서 노드 하나를 삽입하는 것은 O(log N)시간에 수행될 수 있음
insert를 사용할때 RB tree의 특성을 만족함을 보장하기 위해서 보조 프로시져를 사용함 --> RB-insert_Fixup
RB-insert_Fixup을 호출해 노드이 색을 바꾸고 회전을 수행
RB-insert를 호출하면 진입하는 노드가 RB tree에 삽입되고 이때 노드의 key는 이미 채워져있다고 가정
지켜져야할 사항
1. Tree-insert에 나타나는 모든 Nil은 T->Nil로 교체
2. 올바른 Tree 구조를 유지하기 위해 진입노드의 left, right child가 T->nil로 지정
3. 진입노드의 색은 Red
4. 진입노드의 색을 Red로 칠함으로써 RB tree 특성을 위반할 수도 있다. 이를 위해서 rb-insert-fixup을 호출해서 특성을 복구
보조 프로시저 RB-insert-fixup 동작 내용
노드가 진입하면서 RB 특성을 위반할수 있는 경우는 특성 2번과 4번
특성 2 = root는 black
특성 4 = 노드가 레드이면 자식은 모두 블랙
(진입 노드가 red이기 때문에 발생할 수 있는 위반)
insert 시 세가지 불변식
1. 진입노드는 red
2. 진입노드의 parent가 root이면 진입노드의 parent는 black이다
3. 트리가 RB 특성을 위반하는 경우 이 중 최대 한 가지만을 위반(2 or 4)
insert fixup의 while loop에서 모두 6가지가 고려되지만 3개씩 대칭이됨(조부모의 왼쪽에 위치하는지 오른쪽에 위치하는지로 구분)
case 1: 진입 노드의 삼촌 y가 red인 경우
--> 진입노드의 parent와 삼촌이 모두 Red 임
:: 진입노드의 할아버지는 black이므로 진입노드의 parent와 y를 black으로 칠해서 진입노드와 진입노드의 parent가 red라는 문제를 해결할 수 있음
:: 그 다음 진입노드의 할아버지를 red로 칠해서 특성 5도 만족할 수 있음
case 2: 진입 노드의 삼촌 y가 black이고 진입노드가 right child 인 경우
case 3: 진입 노드의 삼촌 y가 black이고 진입노드가 left child 인 경우
case 2는 좌회전을 해서 case 3으로 만들어서 해결
RB-insert
node_t *rbtree_insert(rbtree *t, const key_t key) {
// TODO: implement insert
node_t* new_node=(node_t*)calloc(1, sizeof(node_t));
new_node->key=key;
node_t* y=t->nil;
node_t* x=t->root;
while(x!=t->nil){ // 키 값의 위치를 찾는다
y=x; // y의 빈 node에 x 값을 너놓고 --> 추후에 사용한다
if(key<x->key) // inser하려는 key값이 x의 key보다 작으면 왼쪽 크면 오른쪽
x=x->left;
else
x=x->right;
}
new_node->parent=y; // 만일 while문을 안타면 root라는 의미니깐 parent가 nil이 되고
// 그게 아니면 while 문에서 가장 끝 node를 찾아가서 그 값을 넣음
if(y==t->nil) // 진입 노드가 root라면
t->root=new_node; // root에 new_node를 넣는다
else if(key < y->key) // 그게 아니면 이제 key가 y의 key값과 비교해서 어느쪽 child가 될지 정한다
y->left=new_node;
else
y->right=new_node;
new_node->left=t->nil; // 새로운 노드의 left, right child는 nil로 이어짐
new_node->right=t->nil;
new_node->color=RBTREE_RED; // 새로운 노드는 red로 칠함
RB_insert_fixup(t,new_node); // rb tree의 규칙을 지키기위해 fixup 함수 호출
return new_node; // 모든 내용이 반영된 새로운 node를 return
}RB_insert_fixup
void RB_insert_fixup(rbtree *t, node_t* n){
node_t* y; // Uncle Node
while(n->parent->color==RBTREE_RED){
if(n->parent==n->parent->parent->left){ // n의 parent가 할아버지의 왼쪽 child일때
y=n->parent->parent->right;
if(y->color==RBTREE_RED){ // case 1 삼촌이 red이면
n->parent->color=RBTREE_BLACK; // 진입노드의 부모를 black으로 칠하고
y->color=RBTREE_BLACK; // 삼촌 y도 black으로 칠하고
n->parent->parent->color=RBTREE_RED; // 진입노드의 할아버지를 red로 칠함
n=n->parent->parent;// 진입노드에 진입노드의 할아버지의 정보를 넣어줌
}
else{
if(n==n->parent->right){ // case2 진입노드가 parent의 오른쪽 child이고 삼촌 y가 black
n=n->parent;// 진입 노드에 진입노드의 부모의 정보를 넣어주고
Left_Rotate(t,n); // 좌회전 시킴
} // case3 진입 노드의 삼촌 y가 black이고 진입노드가 left child인 경우
n->parent->color=RBTREE_BLACK; // 진입노드의 parent 를 black으로
n->parent->parent->color=RBTREE_RED; // 진입 노드의 할아버지를 red로
right_Rotate(t,n->parent->parent); // 이후 우회전을해서 맞춰줌
}
}
else{ // n의 parent가 할아버지의 오른쪽 자식일때
y=n->parent->parent->left;
if(y->color==RBTREE_RED){
n->parent->color=RBTREE_BLACK;
y->color=RBTREE_BLACK;
n->parent->parent->color=RBTREE_RED;
n=n->parent->parent;
}
else{
if(n==n->parent->left){
n=n->parent;
right_Rotate(t,n);
}
n->parent->color=RBTREE_BLACK;
n->parent->parent->color=RBTREE_RED;
Left_Rotate(t,n->parent->parent);
}
}
}
t->root->color=RBTREE_BLACK;
}delete
시간복잡도 : O(logN)
delete는 insert보다 더 복잡함
delete도 sub routine을 사용한다
1. rb-transplant
--> 삭제할 node의 정보와 교환할 정보를 만들 장소
2. erase_fixup
--> RB 특성을 복구하기 위해 사용
삭제되는 노드의 색이 Black이면 하나 이상의 RB 특성 위반이 생길수 있음 (즉 red node가 삭제되면 문제 없다라는 얘기 왜냐?)
1. 흑색 높이는 그대로 유지됨
2. 적색노드는 인접하지 않음, y가 삭제노드의 위치로 이동하면서 색도 진입노드의 원래 색으로 유지되므로 진입노드의 새 위치에서 Red node가 인접하는 경우가 없음
3. 삭제노드가 Red이면 루트가 될 수 없음
삭제되는 노드가 색이 Black이면 세가지 문제가 발생할 수 있음
1. 삭제 노드가 루트이고 삭제노드의 red child 가 새로운 root가 되는 경우
2. 삭제된 노드의 자식과 부모가 둘다 적색이면 적색이 인접하는 경우
3. black height가 달라지게되서 특성 5 위반 --> 이를 해결하기 위해서 extra black 이라는 개념이 나타남
erase_fixup의 해결부분
1. 삭제 노드의 형제 노드가 red인 경우
2. 삭제 노드의 형제는 black이고 형제의 두 child가 모두 black
3. 삭제 노드의 형제는 black, 형제의 left는 red, right는 black
4. 삭제 노드의 형제는 black, 형제의 right child가 red
erase.c
int rbtree_erase(rbtree *t, node_t *remove_node) {
// TODO: implement erase
node_t* y=remove_node; // remove_node 정보를 y에 저장
color_t y_color=y->color; // remove_node의 색을 y_color에 저장
node_t* temp; // 삭제 작업을 할때 사용할 temp node 사용
if (remove_node->left==t->nil){ // remove node의 자식이 1개 (오른쪽에 있음)
temp=remove_node->right;
rb_transplant(t,remove_node,remove_node->right);
}
else if(remove_node->right==t->nil){ // remove node의 자식이 1개 (왼쪽에 있음)
temp=remove_node->left;
rb_transplant(t,remove_node,remove_node->left);
}
else{ // remove_node의 자식이 둘
y=sub_rbtree_min(remove_node->right,t->nil); // y에 삭제될 노드의 오른쪽 subtree에서 최소 값을 저장함
y_color=y->color; // 최소값의 color를 y_color에 저장함
temp=y->right; // 최소값의 오른쪽 child를 temp에 저장
if(y->parent==remove_node) // y의 parent가 삭제될 node이면
temp->parent=y; // y의 정보를 temp의 parent에 너놓음
else{ // y의 parent가 삭제될 node가 아니면
rb_transplant(t,y,y->right); // 최소값과 최소값의 right child를 넣고 최소값의 연결을 다 끊어줌
y->right=remove_node->right; // 삭제할 node 의 정보를 최소값에 넣어준다
y->right->parent=y; // right node의 정보가 바뀌었기 때문에 parent node의 정보도 일치시켜줌
}
rb_transplant(t,remove_node,y);
y->left=remove_node->left;
y->left->parent=y;
y->color=remove_node->color;
}
if (y_color==RBTREE_BLACK)// y가 Black이면 하나 이상의 RB 특성 위반이 발생할수 있음
rbtree_erase_fixup(t,temp); // 특성 위반을 해결하기 위해 함수를 호출
free(remove_node);
remove_node=NULL;
return 0;
}erase_fixup
void rbtree_erase_fixup(rbtree* t,node_t* x){
while (x!=t->root && x->color==RBTREE_BLACK){
node_t* temp; // 형제노드 temp
if(x==x->parent->left){ // 삭제 노드가 왼쪽 child 일때
temp=x->parent->right; // 형제 노드 설정
if(temp->color==RBTREE_RED){ // case 1: 형제노드가 red
temp->color=RBTREE_BLACK; // 형제노드의 색을 black으로 바꾸고
x->parent->color=RBTREE_RED; // 부모의 색을 red로 변경
Left_Rotate(t,x->parent); // 그후 좌회전
temp=x->parent->right; // 형제노드에 삭제노드의 형제노드 정보를 다시 설정
}
if(temp->left->color==RBTREE_BLACK && temp->right->color==RBTREE_BLACK){ // case 2: 형제노드가 black, 형제 노드의 두 child가 모두 black
temp->color=RBTREE_RED; // 형제 노드 색을 red로 바꾸고
x=x->parent; // 삭제 노드의 parent를 삭제노드로 재설정 (extra black을 해결하기 위해서)
}
else{
if(temp->right->color==RBTREE_BLACK){ // case 3: 형제노드가 black, 형제 노드의 left == red, right == black
temp->left->color=RBTREE_BLACK; // 형제 노드의 왼쪽 자식을 black으로 칠하고
temp->color=RBTREE_RED; // 형제 노드를 red로 칠함
right_Rotate(t,temp); // 오른쪽으로 회전하고
temp=x->parent->right; // 회전을 통해서 temp는 새로운 형제가 되었기 때문에 다시 형제의 정보를 넣어줌
}
temp->color=x->parent->color; // case 4: 형제노드가 black, 형제 노드의 right == red
x->parent->color=RBTREE_BLACK; // 부모 노드의 색을 black으로 바꿈 (extra black이 타고 올라가서 parent를 염색시킴)
temp->right->color=RBTREE_BLACK; // 형제의 오른쪽 child도 black으로 염색됨
Left_Rotate(t,x->parent); // 우회전
x=t->root; // while 문을 탈출하기 위해서 x에 t-> root를 넣어줌
}
}
else{ // 삭제노드가 오른쪽 child 일때 위와 동일한 방법을 반대로 진행
temp=x->parent->left;
if(temp->color==RBTREE_RED){
temp->color=RBTREE_BLACK;
x->parent->color=RBTREE_RED;
right_Rotate(t,x->parent);
temp=x->parent->left;
}
if(temp->right->color==RBTREE_BLACK && temp->left->color==RBTREE_BLACK){
temp->color=RBTREE_RED;
x=x->parent;
}
else{
if(temp->left->color==RBTREE_BLACK){
temp->right->color=RBTREE_BLACK;
temp->color=RBTREE_RED;
Left_Rotate(t,temp);
temp=x->parent->left;
}
temp->color=x->parent->color;
x->parent->color=RBTREE_BLACK;
temp->left->color=RBTREE_BLACK;
right_Rotate(t,x->parent);
x=t->root;
}
}
}
x->color=RBTREE_BLACK;
}transplant
void rb_transplant(rbtree *t, node_t *u, node_t *v){ // erase가 호출하는 서브 루틴
//u는 최소값의 정보가 v에는 최소값의 child 정보가 들어가있음
if(u->parent==t->nil) // u의 parent 가 t->nil이면 root라는 의미
t->root=v; // root에 v를 넣어줌
else if(u==u->parent->left) // u가 parent의 왼쪽 child 이면
u->parent->left=v; // u의 parent의 왼쪽 child에 u의 자식을 넣어줌
else // u가 parent의 right child이면
u->parent->right=v; // right에 넣어줌
v->parent=u->parent; // v의 parent에 u의 parent를 넣어줌
}