[TIL] - 2023.05-10

📌 - RB트리 삭제

int rbtree_erase(rbtree *t, node_t *z) {
 
  node_t *y = z; // 삭제하려는 노드 z를 우선 y에 저장. 
  node_t *x;
  color_t y_original_color = y->color; // y의 컬러를 저장

 
  
  if (z->left == t->nil){//유효한 값을 가진 자식이 오른쪽에만 하나 있는 경우
    x = z->right; //오른쪽 자식을 x에 담아두고
    transplant(t, z, z->right); //z의 오른쪽 자식을 z에 위치에 이식(transplant)하면서 z는 제거
    
    
  }else if(z->right == t->nil){//유효한 값을 가진 자식이 왼쪽에만 하나 있는 경우
    x = z->left;
   
    transplant(t, z, z->left);  // z의 왼쪽 자식을 z에 위치에 이식하면서 z는 제거됨
  }else{// 유효한 자식이 둘인 경우
    y = tree_minimum(t,z->right);   // y = z의 오른쪽 서브트리의 최소값 ( z의 successor)
    y_original_color = y->color; // 삭제 되는 컬러 저장
    x = y->right; // x는 y의 오른쪽 서브트리
    if (y->parent == z){ // y의 부모가 z일때
      x->parent = y; // x의 부모는 y  -> z가 삭제 되면서 y가 어차피 parent의 위치로 가기 때문
    }else{ 
      transplant(t, y, y->right); // y를 삭제하면서 y의 오른쪽을 y로 변경
      y->right = z->right; // y의 오른 자식 = z의 오른 자식
      y->right->parent = y; // y의 오른쪽 자식의 부모 = y
    }
    transplant(t, z, y);//z를 삭제하면서 y를 z의 위치로 변경
    y->left = z->left; // z의 왼쪽 서브트리를 y의 왼쪽으로 이식
    y->left->parent = y;
    y->color = z->color;
  }
  
  // fix up
  if (y_original_color == RBTREE_BLACK){ //지워지는 색이 검정일 경우
    node_t *brother;
    while (x!=t->root && x->color == RBTREE_BLACK){// x가 루트가 아니고, x의 컬러가 블랙일때
      if(x == x->parent->left){ // x가 왼쪽 자식일 때
        brother = x->parent->right; // x의 형제
        // x 의 형제가 RED 인 경우
        if(brother->color == RBTREE_RED){ // 형제의 컬러가 레드일때 case # 1
          brother->color = RBTREE_BLACK; // 형제의 컬러 = 검정
          x->parent->color = RBTREE_RED; // x의 부모의 컬러 = 빨강
          left_rotate(t, x->parent); // 부모 기준으로 왼쪽 회전
          brother = x->parent->right; // 형재는 x부모의 오른쪽
        }
        // X의 형제는 BLACK이고 형제의 두 자식이 모두 BLACK인 경우
        if(brother->left->color == RBTREE_BLACK && brother->right->color==RBTREE_BLACK){ // 형제의 왼쪽 색이 검정이고 형제의 오른쪽 컬러가 검정일때 case # 2
          brother->color = RBTREE_RED; // 형제의 컬러 = 빨강
          x = x->parent; // x는 x의 부모
        // X의 형제는 BLACK, 형제의 왼쪽 자식은 RED, 형제의 오른쪽 자식은 BLACK인 경우
        }else{ 
          if(brother->right->color == RBTREE_BLACK){ //형제의 오른쪽 색 = 검정 case # 3
            brother->left->color = RBTREE_BLACK; // 형제의 왼쪽 색 = 검정
            brother->color = RBTREE_RED; // 형제의 컬러 = 빨강
            right_rotate(t, brother); // 오른쪽 회전
            brother = x->parent->right; // 형제 = x의 부모의 오른쪽자식
          }
          // X의 형제는 BLACK이고 형제의 오른쪽 자식은 RED인 경우
          brother->color = x->parent->color; // 형제의 색 = x의 부모의 색 case # 4
          x->parent->color = RBTREE_BLACK;  
          brother->right->color = RBTREE_BLACK;
          left_rotate(t, x->parent);
          x = t->root;
        }
      }else{
        //오른쪽 케이스 ( 왼쪽, 오른쪽만 반대고 동일함)
        brother = x->parent->left;
        if(brother->color == RBTREE_RED){
          brother->color = RBTREE_BLACK;
          x->parent->color = RBTREE_RED;
          right_rotate(t, x->parent);
          brother = x->parent->left;
        }
        if(brother->right->color == RBTREE_BLACK && brother->left->color==RBTREE_BLACK){
          brother->color = RBTREE_RED;
          x = x->parent;
        }else{
          if(brother->left->color == RBTREE_BLACK){
            brother->right->color = RBTREE_BLACK;
            brother->color = RBTREE_RED;
            left_rotate(t, brother);
            brother = x->parent->left;
          }
          brother->color = x->parent->color;
          x->parent->color = RBTREE_BLACK;
          brother->left->color = RBTREE_BLACK;
          right_rotate(t, x->parent);
          x = t->root;
        }
      }
    }
    x->color = RBTREE_BLACK;
  }
  free(z);
  return 0;
  // erase 끝
}

 

📌 - RB트리 교체

// 이식하는 함수
// 서브 트리 이동을 위해 노드가 u가 루트인 서브트리를 노드 v가 루트인 서브트리로 교체
void transplant(rbtree *t, node_t *u, node_t *v){
  if (u->parent == t->nil){ // u의 부모가 nil 즉, u가 루트노드라면
    t->root = v; //v를  트리의 루트노드로 삼는다.
  }else if(u == u->parent->left){ //u가 부모의 왼쪽 자식일 경우
    u->parent->left = v; //v를 왼쪽 자식으로 이식 (u를 대체)
  }else{ //오른쪽 자식일 경우
    u->parent->right = v; //v를 오른쪽 자식으로 이식
  }
  v->parent = u->parent;
}

 

 

📌 - RB트리 최소, 최대, 서브루트의 최소값

node_t *rbtree_min(const rbtree *t) {  // 최소값 반환
  // TODO: implement find
  node_t *min_node = t->root; // t->root부터 시작
  while (min_node->left != t->nil){ // 왼쪽노드가 nil일때까지
     min_node = min_node->left;
  }
  return min_node;
}

node_t *rbtree_max(const rbtree *t) { // 최대값 반환
  // TODO: implement find
   node_t *max_node = t->root; // t->root부터 시작
  while (max_node->right != t->nil){ // 오른쪽 노드가 nil일때까지
     max_node = max_node->right;
  }
  return max_node;
}

node_t *tree_minimum(const rbtree *t, node_t *sub_root){
    // TODO: implement find
    node_t *r = sub_root;
    if (r == t -> nil)
        return r;
    while (r -> left != t -> nil)
    {
        r = r -> left;
    }
    return r;
}

 

 

---

 

「 불운이란 무엇일까? 생각이라네. 갈등, 논쟁, 책망, 비난 불손, 경망스러움 등은 무엇을 말하는 걸까? 이것들 또한 생각이라네. ㅡ리고 이 사실보다 중요한 것은 이런 생각들이 우리의 합리적 선택 바깥에 놓여 있을 때지. 그때 그것들은 선 아니면 악의 모습으로 나타난다네. 자신의 선택 영역 안에 속하게 할 때만 이 생각들을 바꿀 수가 있다네. 그러면 무슨 일이 일어나든 사람들은 평화로움을 유지할 수 있다네. 」

-에픽테토스, 대화록, 3.3.18b-19

 

우리는 쉼 없이 생각을 한다. 오늘 하루 당신은 이런저런 생각을 했을 것이다.생각하다가 자주 분노에 사로잡히는 것은 놀랍지 않은 일이다. 

하지만 생각을 놓아버린다면 어떻게 될까? 잡초를 제거하는 것처럼 생각을 자르고 솎아내자. 좋거나 나쁘다는 느낌에 사로잡히지 않으면서 생각이나 판단에 물들지 않는 것이다. 단지 그것뿐이다.

「 에픽테토스가 이렇게 말했다. "우리는 동의하는 기술을 다시 배워야 한다. 그리고 욕망에 대해서도 특별한 주의를 기울여야 한다. 욕망은 적당히 제한 받아야 하며, 공익을 증진할 수 있도록 해야 하며, 실제 가치에 부합할 수 있도록 유의해야 한다.  」

-마르쿠스 아우렐리우스, 명상록, 11.37

 

중요한 것은 경청하고 배우려는 자세다. 우리는 사회적 지위와 상관없이 다른 누군가로부터 기꺼이 배울 수 있어야한다.

 

 

---