[C 언어] RBTree 노드 삭제 구현, 의사 코드 해석

유선·2024년 4월 9일
0

CS

목록 보기
7/25
post-thumbnail

✔️ RBTree 이론 보고 오기 => 클릭

✔️ RBTree 구현 정리 노션 => 클릭

✔️ RBTree 구현 전체 코드 => 클릭

🎄 transplant

⇒ 노드 두개를 매개변수로 넣고, 노드의 부모를 교체한다!

교체되는 노드(부모 없어짐) : u

교체할 노드 (부모 변경): v

  • u 노드의 부모가 nil이라면 (= u 노드가 루트노드라면) v 노드를 루트노드로 바꿔준다.
  • u 노드가 부모의 왼쪽 자식이라면, u 노드의 부모의 왼쪽 자식을 v 노드로 바꿔준다.
  • u 노드가 부모의 오른쪽 자식이라면, u 노드의 부모의 오른쪽 자식을 v 노드로 바꿔준다.
  • v 노드의 부모를 u 노드의 부모로 바꿔준다.
  • tree_transplant 코드
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로 연결한다.
  • zy로 대체한 후, y의 왼쪽 자식을 z의 왼쪽 자식으로 설정하고, y의 색상을 z의 색상으로 설정합니다. 그 후 z를 해제한다.
  • 만약 y의 원래 색상이 검은색이었다면, rbtree_delete_fixup 함수를 호출하여 레드-블랙 트리의 규칙을 복구한다.
  • 슈도 코드 해석
  • rbtree_erase 코드
  // 노드를 삭제하는 함수
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; 

🎄 불균형 조정(fixup)

// 노드 삭제 후 발생한 불균형을 복구하는 함수
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;
}
profile
Sunny Day!

0개의 댓글