레드블랙 트리 - delete 편

레드블랙 트리 - delete편

delete 시 문제점(불균형)

• 제거된 노드가 root노드이거나 BLACK이 제거되었을 경우

5번째 조건 임의의 노드에서 자손 nil 노드들까지 가는 경로들의 black 수는 같다.

delete 문제점 해결법(불균형 복구)

RB-DELETE-Fixup을 구현한다.
불균형 CASE 1~5
CASE 1. remove가 루트인 경우
CASE 2. x의 형제노드가 RED 인경우
CASE 3. x의 형제노드가 BLACK이고 형제노드의 두 자식 모두 BLACK인 경우
CASE 4. x의 형제노드는 BLACK이고, 형제노드의 오른쪽 자식은 RED인 경우
CASE 5. x의 형제 노드는 BLACK이고, 형제 노드의 왼쪽 자식 RED, 노드의 오른쪽 자식은 BLACK인 경우

DELETE 코드

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

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;
    rb_transplant(t,p,p->right);
  }
  else if(p->right == t->nil){
    x=p->left;
    rb_transplant(t,p,p->left);
  }
  else{
    y=p->right;
    while(y->left!=t->nil){
      y=y->left;
    }
    y_original_color = y->color;
    x=y->right;
    if(y->parent==p){
      x->parent=y;
    }
    else{
      rb_transplant(t,y,y->right);
      y->right = p->right;
      y->right->parent =y;
    }
    rb_transplant(t,p,y);
    y->left = p->left;
    y->left->parent =y;
    y->color = p->color;
  }
  if(y_original_color==RBTREE_BLACK){
    rbtree_delete_fixup(t,x);
  }

  free(p);
  return 0;
}

void rbtree_delete_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 : x의 형제 w가 적색인 경우
      if(w->color == RBTREE_RED){
        w->color =RBTREE_BLACK;
        x->parent->color = RBTREE_RED;
        left_rotate(t,x->parent);
        w=x->parent->right;
      }

      //case 2 : x의 형제 w는 흑색이고 w의 두 자식이 모두 흑색인 경우
      if (w->left->color==RBTREE_BLACK && w->right->color ==RBTREE_BLACK)
      {
        w->color = RBTREE_RED;
        x=x->parent;
      }
      //case 3 : x의 형제 w는 흑색, w의 왼쪽 자식은 적색, w의 오른쪽 자신은 흑색인 경우
      else{
        if(w->right->color == RBTREE_BLACK){
          w->left->color = RBTREE_BLACK;
          w->color = RBTREE_RED;
          right_rotate(t,w);
          w=x->parent->right;
        }
        //case 4 : x의 형제 w는 흑색이고 w의 오른쪽 자식은 적색인 경우
        w->color = x->parent->color;
        x->parent->color = RBTREE_BLACK;
        w->right->color = RBTREE_BLACK;
        left_rotate(t,x->parent);
        x=t->root;
      }
      
    }

    //case 5~8
    else{
      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->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;
          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;
}