레드 블랙 트리 - insert

레드 블랙 트리-insert 편

새로 삽입할 노드 z를 red로 칠해준다.
이때 z가 red로 칠 할 경우 래드 블랙 특성 중 하나가 위반될 수 있으므로 rb-insert-fixup 함수를 사용한다.

새 노드 생성 및 삽입할 위치 탐색

• 새로운 노드를 동적으로 생성한다.
• 노드의 key를 입력받고, color는 RED로, 자식노드들은 nil 노드로 설정한다.
• 반복문을 통해 루트 노드부터 탐색을 시작해서 가르키고 있는 노드보다 key 값이 더 작은 경우 왼쪽 자식으로, 큰 경우에는 오른쪽 자식으로 이동한다.
• 반복문 종료 후 새 노드의 부모를 지정한다.

<이때 key란 노드의 원소를 뜻한다.>

insert 코드

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는 루트노드
  node_t *z =(node_t *)calloc(1,sizeof(node_t)); //새 노드 생성
  z -> key = key; //

  while(x != t->nil){ //루트노드가 nil이 아닐때 
    y=x; // y
    if (z->key < x->key){ //
      x=x->left;
    }
    else{
      x=x->right;
      }
    }
  z->parent =y;
  if (y==t->nil){
    t->root = z;
  }
  else if(z->key < y->key){
    y->left = z;
  }
  else{
    y->right =z;
  }
  z->left = t->nil; //새로 삽입한 노드의 왼쪽이랑 오른쪽은 nil로 설정
  z->right = t->nil;
  z ->color = RBTREE_RED; // z노드의 색을 레드로 설정
  rb_insert_fixup(t, z); //불균형 복구
  
  return z;
}

insert 시 문제점

삽입 후에는 tree가 rbtree 5가지 조건을 만족해야 한다.
삽입 했을 때 만족하지 못하는 조건은 2가지가 있다.

2번째 조건 root 노드는 black이다.
-> z가 root 노드라면 2번째 조건을 만족하지 못한다. 그 외에는 만족

4번째 조건 red 노드의 자식노드들은 전부 black이다. 즉 red-red 연속 노드는 없다.)
-> 새로 삽입한 z의 부모 노드가 red일때 조건을 만족하지 못한다.

insert 문제점 해결법

RB-insert-Fixup를 구현한다.
조건 2를 위반 했을 시 : z가 root면서 red인 경우

z를 black으로 변경해주면 된다.

조건 4를 위반 했을 시 : z노드의 부모 노드가 red인 경우

z의 부모노드왕 형제 노드를 black으로 바꾸고 할아버지 노드를 red로 바꾼다.

• insert(10)의 경우

이때 3가지 경우가 존재하게 된다.

CASE 1. z의 삼촌 y가 적색인 경우

• 1. z의 부모 노드와 z의 삼촌 노드가 모두 black으로 칠해주고 z의 할아버지 노드를 적색으로 칠해 준다.

다만 이렇게 색을 변경해주면, 할아버지 노드 위로 red-red 충돌 문제가 발생할 수 있다. 이 경우에는 root 노드 까지 가서 root노드만 black으로 바꾸어주면 된다.

CASE 2. z의 삼촌 y가 흑색이며 z가 오른쪽 자식인 경우

• z의 부모노드를 기준으로 left-rotation을 하고, z의 부모노드를 z로 변경한다. 이후 case 3을 실행한다.

CASE 3. z의 삼촌 y가 흑색이며 z가 왼쪽 자식인 경우

• z의 부모노드와 할아버지 노드의 색깔을 바꾸고 right-rotation 해준다.

insert 구현하기

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는 루트노드
  node_t *z =(node_t *)calloc(1,sizeof(node_t)); //새 노드 생성
  z -> key = key; //

  while(x != t->nil){ //루트노드가 nil이 아닐때 
    y=x; // y
    if (z->key < x->key){ //
      x=x->left;
    }
    else{
      x=x->right;
      }
    }
  z->parent =y;
  if (y==t->nil){
    t->root = z;
  }
  else if(z->key < y->key){
    y->left = z;
  }
  else{
    y->right =z;
  }
  z->left = t->nil; //새로 삽입한 노드의 왼쪽이랑 오른쪽은 nil로 설정
  z->right = t->nil;
  z ->color = RBTREE_RED; // z노드의 색을 레드로 설정
  rb_insert_fixup(t, z); //불균형 복구
  
  return z;
}


//새로 삽입된 노드는 항상 RED 색상으로 삽입 되는데, 새로 삽입된 노드의 부모 노드가 RED인경우, 규칙위반이므로 불균형
//따라서 3가지로 나눠서 CASE 해결
void rb_insert_fixup(rbtree *t,node_t *z){
  node_t *uncle; //삼촌 노드 설정
  while(z->parent->color == RBTREE_RED) {
    //z의 부모가 조부모의 왼쪽 서브트리일 경우
    if(z->parent == z->parent->parent->left){
      uncle=z->parent->parent->right;
      //CASE 1: 노드 z의 삼촌 y가 적색인 경우
      if(uncle->color ==RBTREE_RED){
        z->parent->color =RBTREE_BLACK; 
        uncle->color = RBTREE_BLACK;
        z -> parent -> parent ->color =RBTREE_RED;
        z = z ->parent->parent;
      }
      // case 2 : z의 삼촌 uncle이 흑색이며 z가 오른쪽 자식 인 경우
      else{
        if(z == z->parent->right){
            z = z->parent;
            left_rotate(t,z);
        }
        //case 3 : z이 삼촌 y가 흑색이며 z의 왼쪽 자식 인 경우
        z->parent->color = RBTREE_BLACK;
        z->parent->parent->color = RBTREE_RED;
        right_rotate(t,z->parent->parent);
      }
    }
    //z의 부모가 조부모의 왼쪽 서브 트리 일 경우
    else{
      uncle=z->parent->parent->left;
      //case 4 : 노드 z의 삼촌 y가 적색인 경우
      if(uncle->color == RBTREE_RED){
        z->parent->color =RBTREE_BLACK;
        uncle->color = RBTREE_BLACK;
        z -> parent -> parent ->color =RBTREE_RED;
        z = z ->parent->parent;
      }
      //case 5 : z의 삼촌 y가 흑생이며 z가 오른쪽 자식인 경우
      else{
        if(z == z->parent->left){
            z = z->parent;
            right_rotate(t,z);
        }
        //case 6 : z의 삼촌 y가 흑색이며 z가 왼쪽 자식일 경우
        z->parent->color = RBTREE_BLACK;
        z->parent->parent->color = RBTREE_RED;
        left_rotate(t,z->parent->parent);
      }

    }
  }
  t->root->color = RBTREE_BLACK;
}