[Red-Black 트리]삽입- 구현

📌레드블랙 트리의 다섯가지 속성

1.모든 노드는 red 혹은 black
2.루트 노드는 black
3.모든 nil노드는 black
4.red의 자녀들은 반드시 black == red가 연속적으로 존재할 수 없다.
5.임의의 노드에서 자손 nii 노드들까지 가는 경로들의 black 수는 같다 (자기 자신은 카운트에서 제외)

 

📌삽입

• 레드-블랙 트리에서 새로운 노드를 삽입할때 ,새로운 노드는 항상 red
• 만약 트리가 레드블랙 트리의 특성을 위반한다면, 두가지 방법을 통해 트리의 구조를 조정한다.

1. recolor
2. rotation

 

📌삽입 과정

• 키 값이 20인 노드를 삽입하는 과정을 생각해보자.
• target Node를 20으로 설정하고 시작.

 

• key = 20인 노드가 들어갈 위치 탐색

• key = 20 < 28 이고, 28의 왼쪽 노드가 nil.

• 새로운 노드(20)을 삽입완료.

 

 

📌insert_fixup 과정

👉🏻case.1일때

• 삽입된 red노드(z)의 부모도 red ,삼촌도 red라면
• 부모와 삼촌을 black으로 바꾼뒤 할아버지에서 다시 확인을 하고 red라면 recolor만 해주면 된다.

 

👉🏻case.2일때

• 삽입된 red노드(z)가 부모의 오른쪽 자녀이고, 부모도 red이고 할아버지의 왼쪽 자녀이고, 삼촌은 black일때
• 부모를 기준으로 왼쪽으로 회전한 뒤, 할아버지와 부모의 색을 바꿔준 뒤 오른쪽으로 회전하면 된다.

👉🏻case.3일때

• 삽입된 red 노드가 부모의 왼쪽 자녀이고, 부모도 red이고 할아버지 왼쪽 자녀이고, 삼촌은 black일때
• 할아버지와 부모의 색을 바꾼후 할아버지 기준으로 오른쪽 회전한다.

📌insert , insert_fixup 슈도 코드

 

 

📌C

// 색 변경 함수
void rbtree_insert_fixup(rbtree *t, node_t *z) {
  while (z -> parent -> color == RBTREE_RED) { //z의 부모가 red일때
  // Case # 1 현재 노드의 삼촌, 부모가 red, 할아범이 black : !회전 안 함!
    if (z -> parent == z -> parent -> parent -> left) { //z의 부모가 z의 조상의 왼쪽 자식이면
      node_t *uncle = z -> parent ->parent -> right; //z의 부모의 형제노드 = 삼촌
      if (uncle -> color == RBTREE_RED) { // 삼촌이 red라면
        z -> parent -> color = RBTREE_BLACK; // 부모 red > black
        uncle -> color = RBTREE_BLACK; // 삼촌 red > black
        z -> parent -> parent -> color = RBTREE_RED; // 할아범 black > red
        z = z -> parent -> parent; // 할아버지 가리켜야 다시 while문을 돈다!
      } else { // 삼촌이 black Case 2, 3
        if (z == z -> parent ->right) { //꺾새 모양
          z = z -> parent;
          left_rotation(t, z); // 좌회전
        } // Case 3이 됨 > 색 바꿔주고 우회전하면 끝남
        z -> parent -> color = RBTREE_BLACK;
        z -> parent -> parent -> color = RBTREE_RED;
        right_rotation(t, z -> parent -> parent); // 조상 기준으로 우회전해야함
      }
    } else { //z의 부모가 z의 조상의 오른쪽이면 위의 과정을 반대로 하면 됨
      node_t *uncle = z -> parent -> parent -> left;
      if (uncle -> color == RBTREE_RED) {
        z -> parent -> color = RBTREE_BLACK;
        uncle -> color = RBTREE_BLACK;
        z -> parent -> parent -> color = RBTREE_RED;
        z = z -> parent -> parent;
      } else {
        if (z == z -> parent -> left) {
          z = z -> parent;
          right_rotation(t, z);
        }
        z -> parent -> color = RBTREE_BLACK;
        z -> parent -> parent -> color = RBTREE_RED;
        left_rotation(t, z -> parent ->parent);
      }
    }
  } //While문 끝
  t -> root -> color = RBTREE_BLACK; // 규칙 2를 위해서 root는 항상 black
  return; //void형
}

// 데이터 삽입
node_t *rbtree_insert(rbtree *t, const key_t key) {
  // TODO: implement insert
  node_t *y = t -> nil; // y = 트리의 nil 노드
  node_t *x = t -> root; // x = 트리의 root
  
  while (x != t -> nil) { //x가 nil에 도달할때까지 반복
    y = x;
    if (key < x->key) { //만약 x의 key값보다 삽입할 key의 값이 작으면
      x = x -> left; //x를 x의 왼쪽으로 변경
    } else { //만약 x의 key값보다 삽입할 key값이 크거나 같으면
      x = x -> right;  // x를 x의 오른쪽으로 변경
    }
  }
  //x가 nil을 가리킴 > z를 삽입할 시기
  node_t *z = (node_t *)calloc(1, sizeof(node_t)); // z 노드 생성
  z -> key = key; // z의 key값 넣어줌

  z -> parent = y; // z의 부모는 y
  if (y == t -> nil) { //y가 트리의 nil일때, 비어있던 애(첫 노드)
    t -> root = z; // Case 1 (고려할 필요 없는 경우임 걍 들어감)
  } else if (z -> key < y -> key) { // y의 key값이 삽입할 key값보다 작을 때
    y -> left = z; // y의 왼쪽 자식으로 감
  } else {
    y -> right = z;
  }
  
  z -> left = t -> nil; // z 왼쪽 자식 nil
  z -> right = t -> nil; // z 오른쪽 자식 nil
  z -> color = RBTREE_RED; // 삽입은 늘 red
  // left_rotation(t,z);
  // if (z->parent->parent != NULL) {
  //   right_rotation(t,z);
  // }
  
  rbtree_insert_fixup(t, z);

  return t->root;
}