[C언어] RB 트리 구현(2) - 삭제, 탐색
RB 트리는 삭제가 좀 더 복잡한데요...아무튼 보시죠
레드 블랙 트리 삭제
삭제의 경우의 수는 3가지입니다~ 코드와 함께 확인해보겠습니다.
int rbtree_erase(rbtree *t, node_t *p)
{
node_t *y = p;
node_t *x = NULL;
color_t y_ori_color = y->color;
if (p->left == t->nil)
{
x = p->right;
rbtree_transplant(t, p, p->right);
}
else if (p->right == t->nil)
{
x = p->left;
rbtree_transplant(t, p, p->left);
}
else // 자식이 2명인 경우
{
y = subtree_min(t, p->right);
y_ori_color = y->color;
x = y->right;
if (y->parent == p)
x->parent = y;
else
{
rbtree_transplant(t, y, y->right);
y->right = p->right;
y->right->parent = y;
}
rbtree_transplant(t, p, y);
y->left = p->left;
y->left->parent = y;
y->color = p->color;
}
if (y_ori_color == RBTREE_BLACK){
rbtree_erase_fixup(t, x);
}
free(p);
return 0;
}
if (p->left == t->nil)
왼쪽 자식이 없는 경우입니다. 또한 자식이 둘 다 없는 경우도 체크됩니다.
오른쪽 자식이 없는 경우인데, 위 조건문을 통과했으니 자식이 하나 있는 경우입니다.
그 다음은 자식이 둘 다 존재하는 경우입니다.
이 함수는 삭제할 노드의 successor를 찾는 함수입니다. successor는 삭제할 노드와 자리를 바꿀 leaf 노드입니다. 트리에서 노드를 삭제할 때는 조건에 맞는 leaf 노드와 삭제할 노드의 값을 바꿔 leaf 노드를 삭제하는 방법을 사용하는데요. 그를 위한 함수입니다. 저는 삭제할 노드의 오른쪽 서브트리에서 가장 작은 값을 선택했습니다. 반대로 왼쪽 서브트리에서 가장 큰 값을 선택하는 것도 가능합니다.
이 함수는 p노드와 y노드의 부모를 바꾸는 함수입니다. 삭제할 노드와 successor의 자리를 바꾸는 과정을 이행합니다. (정확히는 p의 부모를 y에게 넘겨주는 것 같네요...)
node_t *rbtree_transplant(rbtree *t, node_t *u, node_t *v) // u와 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 t->root;
}
이후로 부모와 서브트리를 서로 옮겨준 후,
successor는 삭제할 노드의 색을 물려받습니다.
삭제하는 노드는 p노드지만, 삭제되는 색은 위치를 대신한 leaf 노드 successor의 색입니다. 삭제되는 색이 BLACK일 경우 속성이 위반되었는지 확인해야합니다.
삭제 시 속성 위반 확인
void rbtree_erase_fixup(rbtree *t, node_t *x)
{
node_t *s = NULL; // x의 형제 노드
while (x != t->root && x->color == RBTREE_BLACK)
{
if (x == x->parent->left) // x가 부모의 왼쪽 자식일 때
{
s = x->parent->right;
if (s->color == RBTREE_RED) // 경우 1
{
s->color = RBTREE_BLACK;
x->parent->color = RBTREE_RED;
rotate(t, x->parent, LEFT);
s = x->parent->right;
}
// 경우 2
else if (s->left->color == RBTREE_BLACK && s->right->color == RBTREE_BLACK)
{
s->color = RBTREE_RED;
x = x->parent;
}
else {
if (s->right->color == RBTREE_BLACK) // 경우 3
{
s->left->color = RBTREE_BLACK;
s->color = RBTREE_RED;
rotate(t, s, RIGHT);
s = x->parent->right;
}
// 경우 4
s->color = x->parent->color;
x->parent->color = RBTREE_BLACK;
s->right->color = RBTREE_BLACK;
rotate(t, x->parent, LEFT);
x = t->root;
}
}
else // x가 부모의 오른쪽 자식일 때
{
s = x->parent->left;
if (s->color == RBTREE_RED)
{
s->color = RBTREE_BLACK;
x->parent->color = RBTREE_RED;
rotate(t, x->parent, RIGHT);
s = x->parent->right;
}
else if (s->right->color == RBTREE_BLACK && s->left->color == RBTREE_BLACK)
{
s->color = RBTREE_RED;
x = x->parent;
}
else {
if (s->left->color == RBTREE_BLACK)
{
s->right->color = RBTREE_BLACK;
s->color = RBTREE_RED;
rotate(t, s, LEFT);
s = x->parent->left;
}
s->color = x->parent->color;
x->parent->color = RBTREE_BLACK;
s->left->color = RBTREE_BLACK;
rotate(t, x->parent, RIGHT);
x = t->root;
}
}
}
x->color = RBTREE_BLACK;
}
인자로 받아오는 x는 삭제할 노드의 자식 중 하나가 되며, s노드는 x의 형제 노드입니다.
경우 1) 형제 노드가 RED
형제 노드를 BLACK으로
부모 노드를 RED로 바꿔줍니다. 그리고 rotate
rotate는 x의 부모를 기준으로 x노드가 아래로 가도록 돌려줍니다. 그림에서는 왼쪽으로 rotate 해야합니다. 최종적으로 다음과 같은 모습이 됩니다.
경우 2) 형제 노드 BLACK & 형제 노드의 자식이 둘 다 BLACK
간단합니다~ 형제 노드의 색을 RED로 변경해주고, x의 부모를 x로 삼아 다시 while문을 진행합니다.
경우 3) 형제 노드 BLACK & 형제 노드의 자식 중 꺾인 노드가 RED
case 3는 단계적으로 진행됩니다.
1) 꺾인 노드를 BLACK으로 변경, 형제 노드를 RED로 변경
2) 형제 노드를 기준으로 ROTATE
3) 변경된 형제 노드를 재설정하고 case 4 시작
이 과정은 아래 그림과 같습니다.
형제 노드를 기준으로 rotate하는 이유는 꺾인 노드를 펴주기 위함입니다. 2번까지 진행된 노드의 모습은 경우 4와 같은 형태이기 때문에 경우 3은 경우 4로 이어집니다.
경우 4) 형제 노드 BLACK & 형제 노드의 자식 중 꺾이지 않은 노드가 RED
하늘색 세모는 형태 상관없는 자식서브트리입니다...ㅎㅎ rotate할 때 서브트리의 움직임을 표현하기 위해 넣었어요.
case 4도 단계적으로 설명하자면
1) 형제 노드의 색을 부모의 색으로 바꿔줍니다. 아래 그림은 둘 다 BLACK이라 변경사항이 없지만
만약 parent가 red였다면 형제 노드를 red로 바꿔주어야 합니다.
2) 부모의 색을 BLACK으로 바꾸고, 형제 노드의 오른쪽 자식을 BLACK으로 변경합니다.
3) 부모 노드를 기준으로 ROTATE
세 단계를 거치고 나면 위 그림 같은 과정이 됩니다.
이렇게 case 1,2,3,4를 살펴보며 삭제 과정이 끝났습니다~
레드 블랙 트리 탐색
탐색은 간단합니다. 레드블랙트리도 기본적으로 이진트리이기 때문에 이진트리를 탐색하는 방법과 다르지 않습니다.
node_t *find(const rbtree* t, const key_t key){
node_t *x = t->root;
while (x != t->nil){
if (x->key > key){
x = x->left;
}
else if(x->key < key){
x = x->right;
}
else{
return x;
}
}
return NULL;
}
레드 블랙 트리 순회
추가로 중위순회를 이용해 정렬된 순서로 탐색하는 코드입니다. 재귀를 이용했습니다.
void test_inorder(const rbtree *t, node_t *x, key_t *res, const int n, int *index){
if (x == t->nil)
return;
test_inorder(t, x->left, res, n, index);
if (*index < n)
res[(*index)++] = x->key;
else
return;
test_inorder(t, x->right, res, n, index);
}
저번 게시글에도 적었지만 삭제와 관련된 코드 및 case는 [Introduction to Algorithms]이라는 책을 참고했습니다!