자료구조, rbtree delete

자료구조, rbtree delete

 

삭제 역시, 해당 노드를 삭제했을 때, 트리의 균형이 깨지는지 여부가 중요하다.

rbtree 삭제 케이스

 

트리 균형에 위반되지 않는 조건

1. 삭제 노드의 컬러가 Red인 경우

2. 삭제 노드의 컬러가 Black이고 자식이 1개일 경우(유일한 자식)

 

이 외의 케이스는 모두 트리 균형이 깨질 수 있다.

---

📌 RB-Transplant

RB-Transplant, 출처 : CLRS book

RB- Transplant 이해

기존 노드의 부모 노드(u.p)를 새로운 노드의 부모(v.p)로 설정해주므로써 노드를 교체하는 함수이다.

 

📄 rbtree.c

void rbtree_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;
}

---

📌 Tree-Minimum

BST에서와 마찬가지로, 왼쪽 노드가 nil일때까지 추적해 오른쪽 부트리의 가장 작은 노드을 return하도록 해주는 함수이다.

 

📄 rbtree.c

node_t *tree_minimum(rbtree *t, node_t *x) {
  while (x->left != t->nil)
  {
    x = x->left;
  }

  return x;
}

---

 

📌 RB-Delete

rb-delete, 출처 : CLRS book

rbtree delete 이해

속성에 영향을 주지 않을 경우

단순하게 유일한 자식과 삭제할 노드의 위치를 변경해준다.

그후, 삭제하려는 노드의 컬러(가 black이었다면, 균형을 맞춰주기 위해 fixup 과정을 진행하면 된다.

 

속성에 영향을 주는 경우

BST와 동일하게 z노드의 부트에 가장 작은 값을 찾아 y가 그 노드를 가리키도록 하고

y노드의 색이 없어지게 되는 것이므로 이때, y노드의 컬러를 저장해준다.

y의 자식노드를 x가 가리키도록해 삭제후, y,z 교체후, y와 연결해준다.

만약, 교체 후 트리에서 사라지게 되는 색이 블랙이면 x노드를 기준으로 fix-up 과정을 진행한다.

 

📄 rbtree.c

int rbtree_erase(rbtree *t, node_t *p) {
  // TODO: implement erase
  node_t *y;
  node_t *x;
  color_t y_original_color;

  y = p;
  y_original_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{
    // p 노드 자식 2개이상
    y = tree_minimum(t, p->right); // 오른쪽 서브트리에 가장 작은값과 교체
    y_original_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_original_color == RBTREE_BLACK){
    rbtree_erase_fixup(t, x);
  }

  free(p); // 동적할당 해제
  return 0;
}

처음 노드를 할당할때, calloc으로 heap 메모리 영역에 동적 할당 시켜줬으므로 이를 해제해줘야 한다.

그렇지 않으면 메모리 누수가 발생할 수 있다.

---

📌 RB-Delete-Fixup

rb-delete-fixup, 출처 : CLRS book

RB-delete-fixup이해

insert의 경우, 삼촌의 색이 중요했다면

delete의 경우, 형제의 색과 형제 자식의 색이 중요하다.

 

left rotate할때는 x의 부모를 기준으로 restructing해야 하고

right rotate할때는 x의 형제(w)를 기준으로 restructing 해야 한다.

 

📄 rbtree.c

// 삭제시 규칙 위반 하는 경우
// case 1: x의 형제 w가 적색
// case 2: x의 형제 w는 흑색이고 w의 두 자식이 모두 흑색
// case 3: x의 형제 w는 흑색, w의 왼쪽 자식은 적색, w의 오른쪽 자식은 흑색
// case 4: x의 형제 w는 흑색이고 w의 오른쪽 자식은 적색

void rbtree_erase_fixup(rbtree *t, node_t *x){
  node_t *w;
  while (x!= t->root && x->color == RBTREE_BLACK){
    // case 1-4
    if (x == x->parent->left){
      w = x->parent->right;
      // case 1
      if (w->color == RBTREE_RED){
        w->color = RBTREE_BLACK;                    // case 1
        x->parent->color = RBTREE_RED;              // case 1
        rotate_left(t,x->parent);                   // case 1
        w = x->parent->right;                       // case 1
      }

      if (w->left->color == RBTREE_BLACK && w->right->color == RBTREE_BLACK) {
        w->color = RBTREE_RED;                      // case 2
        x = x->parent;                              // case 2
      }

      else {
        if (w->right->color == RBTREE_BLACK){
          w->left->color = RBTREE_BLACK;            // case 3
          w->color = RBTREE_RED;                    // case 3
          rotate_right(t,w);                        // case 3
          w = x->parent->right;                     // case 3
        }
        w->color = x->parent->color;                // case 4              
        x->parent->color = RBTREE_BLACK;            // case 4   
        w->right->color = RBTREE_BLACK;             // case 4   
        rotate_left(t,x->parent);                   // case 4   
        x = t->root;                                // case 4    
      }
    }
    else{
      w = x->parent->left;

      if (w->color == RBTREE_RED){
        w->color = RBTREE_BLACK;
        x->parent->color = RBTREE_RED;
        rotate_right(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;
          rotate_left(t,w);
          w = x->parent->left;
        }
        w->color = x->parent->color;
        x->parent->color = RBTREE_BLACK;
        w->left->color = RBTREE_BLACK;
        rotate_right(t,x->parent);
        x = t->root;
      }
    }
  }
  x->color = RBTREE_BLACK;
}

else 이후로는 left<->right 형태이다.