⇒ 노드 두개를 매개변수로 넣고, 노드의 부모를 교체한다!
교체되는 노드(부모 없어짐) : u
교체할 노드 (부모 변경): v
u
노드의 부모가 nil이라면 (= u
노드가 루트노드라면) v
노드를 루트노드로 바꿔준다.u
노드가 부모의 왼쪽 자식이라면, u
노드의 부모의 왼쪽 자식을 v
노드로 바꿔준다.u
노드가 부모의 오른쪽 자식이라면, u
노드의 부모의 오른쪽 자식을 v
노드로 바꿔준다.v
노드의 부모를 u
노드의 부모로 바꿔준다.void rbtree_transplant(rbtree *t, node_t *u, node_t *v) {
// u의 부모가 nil인 경우, v를 트리의 새로운 루트로 설정
if (u->parent == t->nil) {
t->root = v;
}
// u가 부모의 왼쪽 자식인 경우, v를 부모의 새로운 왼쪽 자식으로 설정
else if (u == u->parent->left) {
u->parent->left = v;
}
// u가 부모의 오른쪽 자식인 경우, v를 부모의 새로운 오른쪽 자식으로 설정
else u->parent->right = v;
v->parent = u->parent; // v의 부모를 u의 부모로 설정(양방향 연결)
}
z
와 그 자리에 올릴 후계자 노드 y
를 설정합니다. 또한 y
의 원래 색상을 y_original_color
에 저장한다.z
의 왼쪽 자식이 t->nil
인 경우, 즉 왼쪽 자식이 없는 경우, z
를 그 오른쪽 자식으로 대체한다.z
의 오른쪽 자식이 t->nil
인 경우, 즉 오른쪽 자식이 없는 경우, z
를 그 왼쪽 자식으로 대체한다.z
가 양쪽 자식을 모두 가진 경우, z
의 오른쪽 서브트리에서 최소값을 가진 노드를 찾아 y
에 할당합니다. 이후 y
의 원래 색상을 y_original_color
에 저장하고, y
의 오른쪽 자식을 x
로 설정한다.y
의 부모가 z
인 경우, x
의 부모를 y
로 설정한다. 그렇지 않은 경우, y
를 그 자리에 대체한 후 y
의 오른쪽 자식을 y
로 연결한다.z
를 y
로 대체한 후, y
의 왼쪽 자식을 z
의 왼쪽 자식으로 설정하고, y
의 색상을 z
의 색상으로 설정합니다. 그 후 z
를 해제한다.y
의 원래 색상이 검은색이었다면, rbtree_delete_fixup
함수를 호출하여 레드-블랙 트리의 규칙을 복구한다. // 노드를 삭제하는 함수
int rbtree_erase(rbtree *t, node_t *z) {
node_t* y = z; // 삭제할 노드를 가리키는 포인터 y를 z로 초기화
color_t y_original_color = y->color; // 삭제할 노드의 색상을 저장
node_t *x; // 삭제된 노드의 자식 노드를 가리킬 포인터 x를 선언
// 삭제할 노드의 왼쪽 자식이 nil인 경우
if (z->left == t->nil) {
x = z->right; // 삭제할 노드의 오른쪽 자식을 x로 지정
rbtree_transplant(t, z, z->right); // 삭제할 노드를 오른쪽 자식으로 교체
// 삭제할 노드의 오른쪽 자식이 nil인 경우
} else if (z->right == t->nil) {
x = z->left; // 삭제할 노드의 왼쪽 자식을 x로 지정
rbtree_transplant(t, z, z->left); // 삭제할 노드를 왼쪽 자식으로 교체
// 삭제할 노드의 양쪽 자식이 모두 존재하는 경우
} else {
y = rbtree_successor(t, z->right); // 오른쪽 서브트리에서 후계자 노드 찾기
y_original_color = y->color; // 후계자 노드의 색상을 저장
x = y->right; // 후계자 노드의 오른쪽 자식을 x로 지정
// 후계자 노드가 삭제할 노드의 바로 다음 노드인 경우
if (y->parent == z)
x->parent = y;
else {
rbtree_transplant(t, y, y->right); // 후계자 노드를 오른쪽 자식으로 교체
y->right = z->right; // 삭제할 노드의 오른쪽 서브트리를 후계자 노드의 오른쪽 서브트리로 설정
y->right->parent = y; // 후계자 노드의 오른쪽 서브트리의 부모를 후계자 노드로 설정
}
rbtree_transplant(t, z, y); // 삭제할 노드를 후계자 노드로 교체
y->left = z->left; // 삭제할 노드의 왼쪽 서브트리를 후계자 노드의 왼쪽 서브트리로 설정
y->left->parent = y; // 후계자 노드의 왼쪽 서브트리의 부모를 후계자 노드로 설정
y->color = z->color; // 후계자 노드의 색상을 삭제할 노드의 색상으로 설정
}
free(z); // 삭제할 노드의 메모리를 해제
// 삭제된 노드의 색상이 검정일 경우, 불균형을 복구
if (y_original_color == RBTREE_BLACK){
rbtree_erase_fixup(t, x);
}
return 0;
// 노드 삭제 후 발생한 불균형을 복구하는 함수
void rbtree_erase_fixup(rbtree *t, node_t *x){
// x가 루트가 아니고, x의 색상이 검정인 동안 반복합니다.
while (x != t->root && x->color==RBTREE_BLACK)
{
// x가 부모의 왼쪽 자식인 경우
if(x == x->parent->left){
node_t *w = x->parent->right; // w는 삼촌
// Case 1: w의 색상이 빨강인 경우
if(w->color == RBTREE_RED){
w->color = RBTREE_BLACK; // w의 색상을 검정으로 변경
x->parent->color = RBTREE_RED; // x의 부모의 색상을 빨강으로 변경
left_rotate(t, x->parent); // x의 부모를 기준으로 왼쪽 회전
w = x->parent->right; // w를 x의 부모의 새로운 오른쪽 자식으로 설정
}
// Case 2: 삼촌 w의 왼쪽 자식과 오른쪽 자식이 모두 검정인 경우
if(w->left->color == RBTREE_BLACK && w->right->color == RBTREE_BLACK){
w->color = RBTREE_RED; // w의 색상을 빨강으로 변경
x = x->parent; // x를 x의 부모로 이동
}else{
// Case 3: 삼촌 w의 오른쪽 자식의 색상이 검정
if (w->right->color == RBTREE_BLACK){
w->left->color = RBTREE_BLACK; // w의 왼쪽 자식의 색상을 검정으로 변경
w->color = RBTREE_RED; // w의 색상을 빨강으로 변경
right_rotate(t, w); // w를 기준으로 오른쪽 회전
w = x->parent->right; // w를 x의 부모의 새로운 오른쪽 자식으로 설정
}
// Case 4: 삼촌 w가 검정, w의 오른쪽 자식의 색상이 빨강
w->color = x->parent->color; // w의 색상을 x의 부모의 색상으로 변경
x->parent->color = RBTREE_BLACK; // x의 부모의 색상을 검정으로 변경
w->right->color = RBTREE_BLACK; // w의 오른쪽 자식의 색상을 검정으로 변경
left_rotate(t, x->parent); // x의 부모를 기준으로 오른쪽 회전
x = t->root; // x를 트리의 루트로 설정(종료)
}
}else{ // 대칭
node_t *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->left->color == RBTREE_BLACK && w->right->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;
}