[TIL] - 2023.05.09

📌 - RB트리 Insert

 

🚀 - 트리 생성

 

rbtree *new_rbtree(void) {
  rbtree *p = (rbtree *)calloc(1, sizeof(rbtree));
  // TODO: initialize struct if needed
  node_t *nil = (node_t*)calloc(1,sizeof(node_t));
  nil -> color = RBTREE_BLACK;
  p->nil = p-> root = nil;
  return p;
}

 

 

🚀 - 노드 삽입

 

node_t *rbtree_insert(rbtree *t, const key_t key) {
  // TODO: implement insert
  node_t *new_node = (node_t*)calloc(1,sizeof(node_t)); // 동적 할당으로 새 노드 생성
  new_node -> key= key; // 받아온 키로 노드 키 지정
  new_node ->color= RBTREE_RED; // 빨간색으로 초기화
  new_node ->left = new_node->right = t->nil; // 왼쪽, 오른쪽 전부 nil로 초기화

  node_t *current = t-> root; //현재 노드 -> rb트리의 루트노드
  while(current != t->nil){ // 현재 노드가 nil노드가 아닐때까지
    if(key<current->key){ // 입력 받은 키가 현재 노드의 키 값보다 작을 경우
      if(current -> left == t -> nil){ // 현재노드의 왼쪽 노드가 nil일 경우
        current-> left= new_node; // 현재 노드의 왼쪽노드에 new_node 넣기
        break; //멈춰
      } 
      current = current -> left; // 현재 노드 = 왼쪽노드
    }
    else{ // 키가 현재노드의 키보다 크거나 같을 경우
      if(current -> right == t->nil){ //현재노드의 오른쪽이 nil노드일 경우
        current -> right = new_node;  // 현재노드의 오른쪽에 new_node넣기
        break;
      }
      current = current->right; //현재 노드 = 오른쪽 노드
    }
   
  
  }
  new_node -> parent = current; // new node의 부모 = 현재노드

  if(current == t->nil){ // 현재노드가 nil노드 일때
    t-> root = new_node; // 루트에 new_node 삽입
  }


  
  rb_insert_fix(t,new_node); //불규칙 판단

  return new_node;
}

 

 

🚀 - 불규칙 판단

void rb_insert_fix(rbtree *t , node_t *node){
  node_t *uncle;
  while(node->parent->color == RBTREE_RED){
    if (node->parent == node->parent->parent->left){
      uncle= node->parent->parent->right;
      if (uncle->color == RBTREE_RED){
        node->parent->color = RBTREE_BLACK;
        uncle->color = RBTREE_BLACK;
        node->parent->parent->color = RBTREE_RED;
        node = node->parent->parent;
        rb_insert_fix(t,node);
        return;
      }
      else {
      if( node == node->parent->right){
        node = node->parent;
        left_rotate(t,node);

        }
        node->parent->color = RBTREE_BLACK;
        node->parent->parent->color = RBTREE_RED;
        right_rotate(t,node->parent->parent);
      }
    }else{
       uncle= node->parent->parent->left;
      if (uncle->color == RBTREE_RED){
        node->parent->color = RBTREE_BLACK;
        uncle->color = RBTREE_BLACK;
        node->parent->parent->color = RBTREE_RED;
        node = node->parent->parent;
        rb_insert_fix(t,node);
        return;
      }else {
      if( node == node->parent->left){
        node = node->parent;
        right_rotate(t,node);

      }
      node->parent->color = RBTREE_BLACK;
      node->parent->parent->color = RBTREE_RED;
      left_rotate(t,node->parent->parent);
      }
    }
  }
  t->root->color =RBTREE_BLACK;
}

 

 

🚀 - 트리 회전

void right_rotate(rbtree *t, node_t *node){
   node_t* y = node->left;
  node->left = y->right;

  if ( y->right != t->nil){
    y->right->parent = node;
  }

  y->parent = node->parent;

  if( node->parent == t->nil){
    t->root = y;
  }
  else if(node==node->parent->right){
    node->parent->right =y;
  }else{
    node->parent->left = y;
  }
  y->right = node;
  node->parent = y;

}

void left_rotate(rbtree *t, node_t *node){
   node_t* y = node->right;
  node->right = y->left;

  if ( y->left != t->nil){
    y->left->parent =node;
  }

  y->parent = node->parent;



  if( node->parent == t->nil){
    t->root = y;
  }
  else if(node==node->parent->left){
    node->parent->left =y;
  }else{
    node->parent->right = y;
  }
  y->left = node;
  node->parent = y;

}

 

❗️ - 처음엔 가독성을 높이기 위해 아래의 형식으로 했었는데 노드를 변경해주면서 계속 주속 바뀌어서 값이 제대로 출력이 되지 않았음

 node_t *parent = node->parent;
  node_t *grandParent = parent->parent;
  node_t *uncle;

결국 하나하나 타이핑을 해서 해결했다.

 

 

 

---

 

「 우울함과 사나운 감정으로는 어떤 것도 받아들이지 못할 것이네. 나는 기꺼이 내 몫의 세금을 낼 것이야. 불평이나 두려움을 불러오는 모든 것들은 살면서 지불해야 하는 세금과 같은 것이지. 친애하는 루실리우스여! 자네 또한 이것들로부터 예의를 희망해서는 안된다네. 」

-세네카. 도덕에 관한 서한. 96.2

 

인생에는 여려가지 형태의 세금이 따른다. 불만을 품고 세금을 회피하고자 애를 쓸 수 있지만 궁극적으로는 모두 헛된 일이다. 지불해야 할 것은 지불하고 지켜야할 것은 지켜야 한다.

「 대화에서 상대방이 무엇을 말하는지 주의를 기울여라. 그 다음 행동으로부터 무엇이 따라 나오는지 살펴라. 행동을 살피는 것은 그 목표가 무엇인지 찾기 위함이고 말에 주의를 기울이는 것은 의미하는 바를 찾기 위함이다.  」

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

 

아우렐리우스는 우리에게 자신의 사고와 행동을 관찰하라고 요구했다. 패턴을 찾아야 원인이 어떤 결과와 만나는지 알 수 있고 부정적인 행동 패턴을 막을 수 있다. 이를 통해 우리는 궁극적으로 삶을 개선할 수 있다.

「 상처받았다는 생각을 버려라. 그러면 상처도 없어진다. 피해의식을 버려라. 그러면 피해도 사라진다. 」

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

 

화가 나 있거나 상처받은 상태에 있을수록 판단은 자제하는 것이 좋다. 감정이 판단을 흐리게 하기 때문이다.

타인의 행동과 외부 사건을 정확하게 추론할 수 잇어야 적절하게 반응할 수 있다.

 

---