크래프톤 정글

RB-Tree 구현하기 (C언어) - Part.6 삭제 구현

고웅 2025. 4. 22. 11:21

지난 시간에 간단하게 RB-Tree에서의 삭제를 이론적으로 살펴봤다. 이제 실제 구현을 통해 삭제에 대한 것을 설명하겠다.

1. 구현 목표

우리는 삭제 기능을 구현하기에 앞서 다음과 같은 기능들을 구현해야 한다.

  1. 노드 삭제
  2. 노드 삭제 시 노드 연결
  3. 삭제 시 fixup 함수
  4. 노드 기준 최소 값 찾기 (successor 탐색)

2. 기능 구현

🔨 노드 삭제

int rbtree_erase(rbtree *t, node_t *p) {
    // TODO: implement to_erase
}

먼저 노드 삭제의 진입 함수인 erase 함수를 구현할 것이다. 이 함수는 BST의 삭제 방법에 따라 노드를 삭제하는 역할을 한다.

구현 아이디어:

  1. successor, replacement 라는 노드를 가리킬 포인터 변수 생성
  2. 삭제되는 노드의 색상을 담을 변수 생성(우리는 열거형-enum으로 색상을 관리한다)
  3. 조건문 if (삭제하는 노드의 왼쪽 자식이 nil일때)
    1. p노드가 삭제되고 대체될 변수는 p의 오른쪽 자식이 될 것이다.
    2. transplant() 함수를 사용한다. -> 이 함수는 추 후 구현하겠다.
  4. 조건문 else if (삭제하는 노드의 오른쪽 자식이 nil일 때)
    1. p노드가 삭제되고 대체될 변수는 p의 왼쪽 자식이 될 것이다.
    2. transplant() 함수를 사용한다. -> 이 함수는 추 후 구현한다.
  5. 조건문 else (삭제하려는 노드의 자식이 둘일 경우)
    1. 삭제하려는 노드의 후임자를 찾아야 한다. -> 이 함수도 추후 구현한다.
    2. 삭제되는 노드의 후임자 색을 저장한다.
    3. replacement는 실제로 successor 자리에 올라올 노드이다.
      우리가 삭제를 한다는 것은 리프 노드에서 일어난다. 즉 트리 중간의 값을 삭제하는 경우 해당 노드가 삭제되는 것이 아니라 그중 후임자가 삭제되는 것이다.
    4. 조건문 if (후임자의 부모가 p인 경우)
      1. replacement의 부모는 successor가 맞기 때문에 그대로 둔다.
    5. 조건문 else (후임자의 부모가 p가 아닌 경우) 
      1. 먼저 successor가 p의 오른쪽 서브트리로 치환해서 트리에서 successor를 제거한다.
      2. 그다음 successor에 p의 오른쪽 자식을 붙인다.
      3. successor를 successor의 오른쪽 자식의 부모로 설정한다.
    6. 삭제 대상 p를 successor로 교체한다. 즉 p 자리에 successor가 올라온다.
    7. p의 왼쪽 자식을 successor의 왼쪽으로 붙인다.
    8. 이제 successor는 p의 왼쪽, 오른쪽 자식을 모두 가지게 된다.
    9. successor는 원래 RED일 수도 있는데, p의 색을 그대로 승계시켜야 한다.
  6. 삭제되는 노드의 색이 검은색이면 속성 위반이 발생하니 fixup 함수를 호출한다.
  7. 삭제하고자 하는 노드 p의 메모리를 해제한다.

굉장히 복잡하다. 위 설명만을 보고 이해하기 어려울 수 있으니 필요하다면 확인할 수 있게 완성 코드를 첨부한다.

더보기 
int rbtree_erase(rbtree *t, node_t *p) {
    // TODO: implement to_erase
    node_t *successor = p;
    node_t *replacement;
    color_t original_color = p->color;

    if (p->left == t->nil) {
        replacement = p->right;
        rb_transplant(t, p, replacement);
    } else if (p->right == t->nil) {
        replacement = p->left;
        rb_transplant(t, p, replacement);
    } else { // 삭제하려는 노드의 자녀가 둘인 경우
        // 삭제하려는 노드 기준 successor 즉 후임자를 찾는 과정
        successor = rb_tree_min_subtree(t, p->right);
        // 삭제되는 노드의 successor의 색을 저장
        original_color = successor->color;
        replacement = successor->right;
        // successor 노드를 기존 노드에서 분리하기 위한 작업
        if (successor->parent == p) {
            replacement->parent = successor;
        }
        else {
            rb_transplant(t, successor, replacement);
            successor->right = p->right;
            successor->right->parent = successor;
        }
        // 분리된 successor 노드를 삭제하려는 노드에 대체하는 작업
        rb_transplant(t, p, successor);
        successor->left = p->left;
        successor->left->parent = successor;
        successor->color = p->color;
    }

    if (original_color == RBTREE_BLACK) {
        rb_delete_fixup(t, replacement);
    }
    free(p);
    return 0;
}

🔨  노드 바꾸기

이제 위 코드에서 누락했던 함수 기능을 하나씩 구현해 보자. 먼저 노드를 바꾸는 함수다.

void rb_transplant(rbtree *t, node_t *p, node_t *replacement) {
}

이 함수의 목적은 트리 내에서 어떤 노드 p를 다른 노드 replacement로 바꾸는 함수다.

  • p 노드 자리에 replacement 노드를 올리는 작업
  • 부모 포인터만 바꿔주는 함수
  • 실제로 자식 연결이나 노드 데이터 교체는 하지 않음

구현 아이디어:

  1. 삭제 대상 p 가 루트 노드일 경우 - 트리의 루트를 replacement로 교체
  2. p가 부모의 왼쪽 자식일 경우 - 부모의 왼쪽 포인터를 replacement 로 변경
  3. p가 부모의 오른쪽 자식일 경우 - 부모의 오른쪽 포인터를 replacement 로 변경
  4. replacement의 부모 포인터도 p의 부모로 바꾼다.
더보기 
void rb_transplant(rbtree *t, node_t *p, node_t *replacement) {
    if (p->parent == t->nil) {
        t->root = replacement;
    } else if (p == p->parent->left) {
        p->parent->left = replacement;
    } else {
        p->parent->right = replacement;
    }
    replacement->parent = p->parent;
}

🔨  후임자 찾기 Successor

node_t *rb_tree_min_subtree(rbtree *t, node_t *start) {
}

이 함수는 삭제 대상 노드의 후임자를 찾는 함수이다.

구현 아이디어:

  1. 현재 노드를 지정할 cur 선언
  2. 반복문을 진행한다. - 현재 노드의 왼쪽 자식이 nil일 때까지
  3. 현재 노드를 현재 노드의 왼쪽 자식으로 선택한다.
  4. 선택된 노드를 반환한다.
더보기 
node_t *rb_tree_min_subtree(rbtree *t, node_t *start) {
    node_t *cur = start;
    while (cur->left != t->nil) {
        cur = cur->left;
    }
    return cur;
}

🔨  fixup 함수 (가장 중요)

이제 삭제 기능에서 가장 중요한 속성 위반을 고쳐줄 함수를 구현한다.

void rb_delete_fixup(rbtree *t, node_t *target) {
}

삭제를 진행할 때 double black 인 경우가 발생하는데 이를 해결해야 한다.

구현 아이디어 :

  1. while을 사용하여 현재 노드가 루트가 아니면 서 삭제할 노드의 색상이 Black 일 때만 반복한다.
  2. node_parent, sibling 이란 노드 포인터 변수를 선언한다.
  3. 조건문 if (삭제된 노드가 부모의 왼쪽 자식인 경우)
    1. 형재 노드를 부모의 오른쪽 노드로 선택한다.
    2. 조건문 if (형제의 색깔이 RED 인경우) -> case 1
      1. 형재의 색을 Black으로 바꾼다.
      2. 타깃의 부모의 색을 RED로 바꾼다.
      3. 부모를 기준으로 왼쪽으로 회전시킨다.
    3. 조건문 else (형제의 색깔이 Black인 경우)
      1. 조건문 if (형제의 왼쪽 자식의 색이 Black이면서 형제의 오른쪽 자식의 색이 Black인 경우) -> case 2
        1. 형제의 색을 RED로 설정
        2. 타깃을 타깃의 부모로 변경
      2. 조건문 else (형제의 왼쪽 자식 중 RED인 자식이 있는 경우)
        1. 조건문 if (형제의 오른쪽 자식이 Black일 경우) -> case 3
          1. 형제가 Black이고, 왼쪽 자식만 Red면 → 오른쪽 Red로 만드는 구조로 바꾸기 위해 sibling을 회전한다.
          2. 이 회전은 Case 4로 진입하기 위한 전처리다
        2. 형제의 오른쪽 자식이 Red이면 최종적으로 균형을 복구할 수 있다.
        3. 색을 재조정하고, 부모를 중심으로 회전하여 Double Black 상태를 완전히 제거
        4. target = t->root;로 설정하여 루프 종료 시킨다 (루트에 도달한 것으로 처리)
  4. 조건문 else(삭제된 노드가 부모의 오른쪽 자식인 경우)
    1. 위의 과정을 반대로 진행한다.
  5. 타깃의 색상을 Black으로 만들어주면서 끝이 난다.
더보기 
void rb_delete_fixup(rbtree *t, node_t *target) {
    while (target != t->root && target->color != RBTREE_RED) {
        node_t *node_parent = target->parent;
        node_t *sibling;
        if (target == node_parent->left) {
            // target이 부모의 왼쪽 자식인 경우
            sibling = node_parent->right;
            if (sibling->color == RBTREE_RED) { // case 1
                sibling->color = RBTREE_BLACK;
                target->parent->color = RBTREE_RED;
                rb_left_rotation(t, target->parent);
                sibling = target->parent->right;
            }else {
                // 형제의 색이 검정색일 때 조건문 진입
                // case 2
                if (sibling->left->color == RBTREE_BLACK && sibling->right->color == RBTREE_BLACK) {
                    sibling->color = RBTREE_RED;
                    target = target->parent;
                } else {
                    // case 3 처리
                    if (sibling->right->color == RBTREE_BLACK) {
                        sibling->left->color = RBTREE_BLACK;
                        sibling->color = RBTREE_RED;
                        rb_right_rotation(t,sibling);
                        sibling = node_parent->right;
                    }
                    // case 4 처리
                    sibling->color = node_parent->color;
                    node_parent->color = RBTREE_BLACK;
                    sibling->right->color = RBTREE_BLACK;
                    rb_left_rotation(t, node_parent);
                    target = t->root;

                }
            }

        }
        else {
            // target이 부모의 오른쪽 자식인 경우
            sibling = node_parent->left;
            if (sibling->color == RBTREE_RED) { // case 1
                sibling->color = RBTREE_BLACK;
                target->parent->color = RBTREE_RED;
                rb_right_rotation(t, target->parent);
                sibling = target->parent->left;
            }else {
                // 형제의 색이 검정색일 때 조건문 진입
                // case 2
                if (sibling->left->color == RBTREE_BLACK && sibling->right->color == RBTREE_BLACK) {
                    sibling->color = RBTREE_RED;
                    target = target->parent;
                } else {
                    // case 3 처리
                    if (sibling->left->color == RBTREE_BLACK) {
                        sibling->right->color = RBTREE_BLACK;
                        sibling->color = RBTREE_RED;
                        rb_left_rotation(t,sibling);
                        sibling = node_parent->left;
                    }
                    // case 4 처리
                    sibling->color = node_parent->color;
                    node_parent->color = RBTREE_BLACK;
                    sibling->left->color = RBTREE_BLACK;
                    rb_right_rotation(t, node_parent);
                    target = t->root;
                }
            }
        }
    }
    target->color = RBTREE_BLACK;

}

기능 구현이 종료되었다. 만약 설명을 봐도 이해가 안 된다면 정상이다. 쉽게 이해할 수 없을 정도로 보기만 하면 매우 어렵게 느껴졌다. 위 코드를 작성한 본인도 설명하라고 하면 버벅거리거나 막히는 부분이 많을 것이다. 그럴 때는 아래 출처 혹은 참조에 있는 자료를 반복해서 보다 보면 이해가 될 것 같다.

출처

https://youtu.be/6drLl777k-E?si=zPEX5ev8GapzBIE2

 

저작자표시 동일조건