RB 트리가 뭐야? RB트리 삽입까지 알아보자

RB트리의 개념 

 

RB트리 (Red-Black Tree) 는 자가 균형 이진 탐색 트리의 한 종류로 데이터를 효율적으로 저장하고 검새그 삽입, 삭제 연산을 수행하기 위해 사용된다. 

 

 

RB 트리의 특성

1. 노드 색깔 : 각 노드는 Red Color  또는 Black Color

2. 루트 노드 : 루트 노드는 항상 Black Color

3. 리프 노드 : 모든 리프 노드(NIL)는 Black Color

4. Red 노드의 자식 : Red 노드의 자식은 항상 Black Color . 하지만 Black 노드는 연속될 수 있다.  즉, Red 노드 - Red 노드는 불가능하고, Red - Black 이나 Black - Black은 가능하다.

5. Black node의 수 : 임의의 노드로부터 리프 노드에 도달하는 모든 경로에서 Black 노드의 수는 일정하다.

 

간단한 RB 트리에서 5번 특성을 확인해보자.

 

15 노드를 루트 노드로 RB트리가 구성되어 있다.

5번 특성을 확인할 때, 경로의 Black 노드의 수에서 루트 노드는 포함시키지 않고, 리프노드인 nil 노드는 포함시켜 Black 노드의 개수를 정한다. 사진의 트리를 보면 각 리프까지의 경로의 Black 노드의 수가 2로 일정한 것을 볼 수 있으며, 이는 RB트리의 특성을 만족한다고 할 수 있다.

 

 

---

RB 트리 문제를 다루기 앞서 용어 정의를 그림과 같이 하겠다.

현재 노드는 8번 노드로 current node이며, 10번은 parent node, 11번은 sibling node이다.

 

 

RB 트리 - 삽입

 

삽입하려는 노드는 항상 Red Color 이다. 삽입하려는 노드의 parent node가 Black Color이면 RB트리 특성을 만족하지만, Red Color일 때 RB트리 4번 특성인 연속 Red 노드 (Red - Red) 문제가 발생한다. 따라서 이를 해결해주기 위한 case들이 존재한다.

 

 

Case 1.  parent 와 uncle이 모두 Red 일 때

 

parent 와 uncle의 red 색을 부모의 black 과 교환한다. 이는 RB트리 5번 특성인 black 노드의 수도 만족하며 4번 특성도 만족하게 된다.

 

 

Case 2.  parent 가 Red , uncle 이 Black 이고, 꺾여있을 때

 

 

parent를 왼쪽 회전하여 다음 그림과 같이 만든다. 이렇게 한 후 Case 3을 진행한다.

 

 

Case 3.  parent 가 Red , uncle 이 Black 이고, 선형일 때

 

parent 와 grand parent의 색을 변경하고, grand parent 기준으로 오른쪽 회전을 한다.

 

 

삽입을 했을 때, 최종적으로 루트 노드가 Black 인지 확인하고, 아니라면 Black으로 변경해준다.(RB트리 2번 특성)

 

// 노드 삽입 : t 라는 rbtree에 key 값을받아 노드를 생성하여 rbtree를 구성하기 
node_t *rbtree_insert(rbtree *t, const key_t key)
{ // 2

  node_t *y = t->nil;  // y : 부모
  node_t *x = t->root; // x : 현재 노드

  // 새 메모리 할당하여 삽입할 노드를 만들어줌 & 초기화
  node_t *z = (node_t *)calloc(1, sizeof(node_t));

  if (z == NULL){ // 메모리 할당 실패
    return NULL;
  }
  z->color = RBTREE_RED;
  z->left = t->nil;
  z->right = t->nil;
  z->parent = NULL;
  z->key = key;

  /*
  y 에 현재 x의 값을 넣어주고 x를 left or right로
  보냄으로써 y는 x의 부모가 됨을 알 수 있음.
  */
  while (x != t->nil)
  {
    y = x;
    if (key < x->key)
    {
      x = x->left;
    }
    else
    {
      x = x->right;
    }
  }

  /*
  삽일할 노드 z의 부모를 y로 설정하고
  y의 상태에 따라 혹인 y의 값에 따라  z의 자리를 결정함.
  이는 아까 설정한 x와 z가 같다라는 것을 알 수 있음
  */
  z->parent = y;
  if (y == t->nil)
  {
    t->root = z;
  }
  else if (key < y->key)
  {
    y->left = z;
  }
  else
  {
    y->right = z;
  }

  // z를 마지막노드로 하는 설정 nil노드 추가해주기
  z->left = t->nil;
  z->right = t->nil;
  z->color = RBTREE_RED;

  insert_fixup(t, z);

  return z;
}

// 삽입을 했을 때, 노드의 색상과 RBtree의 특성을 만족하도록 변경
void insert_fixup(rbtree *t, node_t *z)
{
  // z : cur node
  node_t * y;
  while( z->parent -> color == RBTREE_RED){
    if (z->parent == z->parent->parent->left){
      y = z->parent->parent->right;
      if (y->color == RBTREE_RED){
        z->parent->color = RBTREE_BLACK;
        y->color = RBTREE_BLACK;
        z->parent->parent->color = RBTREE_RED;
        z = z->parent->parent;
      }else{
        if (z== z->parent->right){
          z = z->parent;
          left_rotate(t,z);
        }
        z->parent->color = RBTREE_BLACK;
        z->parent->parent->color = RBTREE_RED;
        right_rotate(t,(z->parent->parent));
      }
    }else{
      y = z->parent->parent->left;
      if (y->color == RBTREE_RED){
        z->parent->color = RBTREE_BLACK;
        y->color = RBTREE_BLACK;
        z->parent->parent->color = RBTREE_RED;
        z = z->parent->parent;
      }else{
        if (z== z->parent->left){
          z = z->parent;
          right_rotate(t,z);
        }
        z->parent->color = RBTREE_BLACK;
        z->parent->parent->color = RBTREE_RED;
        left_rotate(t,(z->parent->parent));
      }
    }
  }
  t->root->color = RBTREE_BLACK;
}

// 왼쪽 회전
void left_rotate(rbtree *t, node_t *z)
{
  node_t *y = z->right;
  z->right = y->left; // y의 왼쪽 서브트리를 z의 
  if(y->left != t->nil){
    y->left->parent = z;
  }
  y->parent = z->parent;
  if(z->parent == t->nil){ // z가 루트였다면 y가 트리루트
    t->root = y;
  }else if(z == z->parent->left){
    z->parent->left = y;
  }else{
    z->parent->right = y;
  }
  y->left = z;
  z->parent = y;
}
// 오른쪽 회전
void right_rotate(rbtree *t, node_t *z)
{
  node_t *y = z->left;
  z->left = y->right;
  if(y->right != t->nil){
    y->right->parent = z;
  }
  y->parent = z->parent;
  if(z->parent == t->nil){
    t->root = y;
  }else if(z == z->parent->right){
    z->parent->right = y;
  }else{
    z->parent->left = y;
  }
  y->right = z;
  z->parent = y;
}