정글사관학교 36일차 TIL: Red-Black Tree(RB트리) 삽입 구현

요 며칠간 끊임없이 고통을 안겨줬던 레드블랙 트리(이하 RB트리)..그래도 계속 보다 보니까 얼추 감이 잡히기 시작한다. 아직 가장 큰 관문인 삭제가 남아있지만 그래도 삽입 구현 완료! RB트리 개념부터 시작해서 삽입까지 빠르게 정리하고 마무리할 예정. 오늘 풀었던 알고리즘 문제는 따로 포스팅해야겠다.

 

Red-Black Tree(레드블랙 트리)

1. RB트리 정의

 rb트리는 균형 이진 탐색 트리의 여러 버전 중 하나이다. 균형 이진 탐색 트리란, 이진 탐색 트리에 노드를 삽입/삭제하는 과정에서 어느 한 쪽으로 노드가 쏠리는 것을 방지하기 위해 규칙을 추가한 심화 버전 이진 탐색 트리라고 보면 되겠다. 왜 이런 짓을 하냐? 이진 탐색 트리를 만드는 이유는 특정 노드를 검색하는데 드는 시간 복잡도가 O(log N)으로 매우 효율적이기 때문인데, 만약 이진 탐색 트리가 한쪽으로 쭈루루룩 쏠렸다면? 아래 이미지와 같은 최악의 경우 시간 복잡도는 O(N)으로, 이진 탐색 트리를 만드는 이유가 없어진다.

 

 

위와 같은 상황을 방지하기 위한 방법 중 하나로 고안된 것이 RB트리이다. 생김새는 아래와 같다. 좀 그지같이 생긴 면이 없잖아 있다. 대체 무슨 규칙이 추가된 건지 살펴보자. RB트리는 노드의 색이 2가지 -Black과 Red로 이뤄져 있다.

 

가장 끝에 있는 leaf 노드를 보면 NIL이라고 적힌 특이한 형상을 띄고 있는데, 이는 NULL에 해당하는 노드이다. RB트리에서는 이런 NIL 노드를 하나의 독립된 노드로 취급한다. 그래서 leaf 노드는 가장 끝에 있는 동그란 노드가 아니라 그 노드에 달린 NIL에 해당한다. 따라서 무조건 NIL이 leaf 노드에 해당한다. 이는 rb트리의 주요한 특징 중 하나이다. NIL을 제외한 모든 동그라미 노드를 내부 노드라고 한다.

 

 

RB트리는 총 5개의 조건을 만족해야 비로소 RB트리라고 말할 수 있게 된다. 여기서 전제는 RB트리가 이진탐색트리의 구조를 따른다는 것.(= 왼쪽 자식 노드 값 < 자기 자신 값 < 오른쪽 자식 노드 값)

 

1. 모든 노드는 Red/Black 둘 중 한 가지 색을 갖는다. (NIL 포함)
2. Root 노드 색은 반드시 Black이다.
3. Leaf(NIL) 노드는 반드시 Black이다.
4. Red node는 2개의 자식 노드를 가지며 자식 노드의 색상은 반드시 black이다. (NIL 노드도 자식 노드에 해당!)
5. 어떤 한 노드에서 leaf 노드로 가는 모든 경로에 대해 각 경로마다 있는 블랙 노드의 수는 항상 같다.

5번만 부가설명을 하면, 어떤 한 노드를 정했을 때, 그 노드에서 leaf 노드까지 가는 경로의 수는 여러 가지다. 예를 들어 위 이미지에서 8번 노드를 골라보자. 8번 노드에서 NIL까지 가는 경로의 수는 (8-1-N), (8-1-6-N), (8-11-N) 총 세 가지이다. 이때, 출발하는 자기 자신(=8번 노드)를 제외하고 길에 놓여있는 검은색 노드의 수는 2로, 모든 경로에 대해 같은 개수를 지닌다.

 

이를 식으로 나타내보자.

 

h(v) = v의 높이(height = leaf와 v 사이에 부모-자식으로 연결된 노드 개수)

bh(v) = v에서 leaf 노드로 갈 때, v (자기자신)을 제외하고 만나는 black 노드의 개수 (모두 동일하다 했으니 v만 정해지면 값은 하나로 정해진다.)

 

이때, [v의 sub-tree의 내부 노드 개수 >= 2**(bh(v))-1]과 같다. 증명은 패스.

 

2. 레드블랙트리 회전

레드블랙 트리는 위의 5가지 조건을 항상 만족하기 위해, 새로운 노드를 삽입하거나 삭제할 때 상황에 따라 기존 노드의 색을 수정하고 위치를 변경하는 작업을 거쳐야 한다. 따라서 기존 노드를 회전하는 작업을 수행한다. 아래 이미지를 보자. 새로운 노드를 삽입하는 과정에서 기존 노드를 회전해 10의 자식 노드였던 20이 루트 노드로 바뀌게 된다. 색깔 역시 바뀐다. 따라서 이를 위해 가장 먼저 노드를 회전하는 함수부터 짜보도록 하자. 아래 pseudocode를 따라가면 쉽게 구현이 가능하다.(여기서 뭔가 턱턱 막히는 느낌이 들면 이진 탐색 트리와 연결 리스트부터 공부하는 걸 추천!)

 

 

void left_rotation(rbtree *t, node_t *x) {
    node_t *y = x->right;
    x->right = y->left; // x 오른쪽 자식에 y->left 달아
    if (y->left != t->nil){
      y->left->parent = x;
    }
    y->parent = x->parent;
    if (x->parent ==t->nil) {// x가 루트 노드이면 (루트 노드의 부모는 t->nil)
      t->root = y; // 이제 y가 루트 노드가 되어야 함
    }
    else if (x == x->parent->left){ // x가 왼쪽 자식 노드이면
      x->parent->left = y;
    }
    else {
      x->parent->right = y; // x가 오른쪽 자식 노드
    }
    y->left = x;
    x->parent = y;
}

//right_rotation은 위에서 left를 right으로 바꾸기만 하면 끝

 

3. 레드블랙트리 삽입

삽입이 조금 까다롭다 생각할 수 있는데, 이 영상만큼 삽입을 쉽게 설명하는 자료가 없는듯. 정말 좋아서 이 영상은 아래에 영상을 삽입해둔다. 꼭 봤으면!

 

 

RB트리에서 삽입 연산을 실행할 때 고려해야 하는 경우의 수는 3가지이다. 사실 5가지인데, 앞의 2가지는 기본적인 조건이라 그냥 스무스하게 넘어갈 수 있다. 삽입하려는 새로운 노드를 z라고 하겠다.

 

먼저, 삽입 시에 한 가지 규칙이 있다. 삽입하는 노드의 색은 반드시 red에서 출발한다. 따라서 새로운 노드의 자식 노드는 반드시 black이어야 한다.(규칙 4)

 

한 가지 더. RB트리는 이진탐색트리의 심화 버전이라고 했다. 삽입/삭제가 달라지지만 기본적으로 탐색 알고리즘은 동일하기 때문에 여기서는 설명하지 않는다.(이진탐색트리에서 탐색 알고리즘이 궁금하면 여기로!) 

 

케이스를 나눠서 살펴보자.

 

1. z = t->root인 경우 (==트리에 아무 노드도 없어서 루트 노드에 삽입하는 경우)

 

트리가 비어있으니 트리의 root에 z를 삽입한다. root의 색상은 반드시 검은색이어야 하니(규칙 2), z->color = black으로 색상을 바꾼다. 그리고 삽입하면 끝.

 

2. z ->parent->color == black인 경우 (새로 삽입하는 위치에서 부모 노드의 색이 검은색인 경우)

 

black 색상 노드 밑에는 black이든 red든 어떤 노드가 와도 상관이 없다. 이때, 탐색 과정에서 while문을 돌려 z가 위치할 수 있는 맨 끝단까지 반드시 갈 수밖에 없으니 새로운 노드 z 밑에는 NIL 말고 다른 동그라미 노드가 달릴 수 없다는 점을 유념하자. 따라서 이 경우에는 아무 것도 고려할 필요가 없다. 그냥 삽입을 진행하면 끝.

 

3. z->parent->color == RED인 경우

 

여기서부터 총 3가지로 나눠서 생각한다. 이때부터 부모-자식 외에도 할아버지/삼촌이 나오는데(대가족 총출동..) 너무 어렵게 생각할 것 없다. 할아버지는 부모 노드의 부모 노드이고 삼촌 노드는 부모 노드와 같은 레벨에 있는 형제 노드이다. 이제부터 삼촌 노드를 uncle, 할아버지 노드를 gp(=grandparent)라고 하자.

 

3-1) z->uncle->color == RED인 경우 (삼촌 노드의 색이 빨간색인 경우)

 

부모의 색과 삼촌 노드의 색 둘 다 빨간색이려면 gp의 색이 반드시 검은색이어야 한다. 빨간색 노드의 부모로는 빨간색이 올 수 없기 때문(규칙 4).

 

이런 상황에서, gp와 (부모&삼촌) 노드 색을 서로 바꾼다. 즉, gp가 red, parent와 uncle이 검은색이 되게 바꾼다. 그러고 나면 모든 규칙을 만족하므로 삽입 과정 종료.

 

3-2) z->uncle->color == BLACK인 경우 (삼촌 노드의 색이 검은색인 경우)

 

이 경우는 조금 더 복잡해지는데, 별 거 없다. 여기서 두 가지 상황을 나눠서 생각한다.

 

3-2-a)x, parent, gp가 linear하게 연결된 경우 (== 위에 올린 이미지와 같이 z-parent-gp가 꺾이지 않고 직선으로 연결된 상황)

 

이때, parent와 gp를 연결하는 링크를 중심으로 우회전한다. 우회전 알고리즘은 위에 구현해뒀으니 그대로 갖다 쓴다.

 

3-2-b) x,parent, gp가 triangle로 연결된 경우(==위의 그림에서 sibling 자리에 z가 오면 z-parent-gp 연결 모양새가 ^ <- 이렇게 꺾인선 모양이 되는 상황)

 

이때는 두 번 회전하게 되는데, 먼저 z와 parent를 연결한 선을 중심으로 좌회전을 해서 z가 parent의 부모 노드가 되게끔 한다. 그러면 z가 gp의 자식 노드가 되는데, z-gp 사이 링크를 중심으로 우회전시켜 z가 gp 자리에 오게 한다. 마지막으로 z와 gp 색을 바꿔 z가 black, gp가 red가 되게끔 하면 끝!

 

모든 로직이 1) 회전(n회) -> 2) 색 재배치 로 진행되는 것을 볼 수 있다. 코드는 아래 적어뒀다. 이 역시 수도코드를 따라 치면 쉽게 구현 가능!

 

 

node_t *rbtree_insert(rbtree *t, const key_t key) {
  // TODO: implement insert
  node_t *y = t->nil;
  node_t *x = t->root;

  while (x != t->nil){
    y = x;
    if (x->key == key) {
      printf("같은 키가 있습니다.\n");
      return x;
    }
    else if (key < x->key){
      x = x->left;
    } 
    else {
      x = x->right;
    }
  }
  //x가 null을 가리키면 그때가 z를 삽입할 때!

  node_t *z = (node_t *)calloc(1, sizeof(node_t));
  z->key = key;
  z->parent = y; //x가 NIL을 가리키고 y는 그 위 노드 가리킴 
  if (y == t->nil) //애초에 트리가 비어있다면 y는 t->nil 그대로
    t->root = z; // Case 1 (Case 2는 고려할 필요 X => 알아서 pass)
  else if (z->key < y->key) // y 왼쪽 자식으로 와야지.
    y->left = z;
  else
    y->right = z;
  
  z->left = t->nil; 
  z->right = t->nil;
  z->color = RBTREE_RED;
  rb_insert_fixup(t, z);
  return t->root;
}

void rb_insert_fixup(rbtree* t, node_t *z){
  while (z->parent->color ==RBTREE_RED) {
    if (z->parent == z->parent->parent->left){ //z의 parent가 왼쪽 자식 노드이면
      node_t *uncle = z->parent->parent->right;
      if (uncle->color == RBTREE_RED) { // 경우 1: z->uncle의 색이 red
        z->parent->color = RBTREE_BLACK; // 색 바꿔주고
        uncle->color = RBTREE_BLACK; // 색 바꿔주고
        z->parent->parent->color = RBTREE_RED; // 여기도 색 바꿔주고 & 여기서는 회전 없음.
        z= z->parent->parent; // ??? 왜 할부지 가리킴? => 할부지 밑으로 업뎃 끝났으니 그 위에서 다시 while문 돌아야 하니!
      }
      else {// uncle color가 블랙
        if (z == z->parent->right) { // 경우 2, 3: uncle color가 black일 때
          z = z->parent;
          left_rotation(t, z);
        }
        z->parent->color = RBTREE_BLACK;
        z->parent->parent->color = RBTREE_RED;
        right_rotation(t, z->parent->parent);
      }
    }
    // left => right로 방향 바꿈
    else {
      node_t *uncle = z->parent->parent->left;
      if (uncle->color == RBTREE_RED) { // 경우 1: z->uncle의 색이 red
        z->parent->color = RBTREE_BLACK; // 색 바꿔주고
        uncle->color = RBTREE_BLACK; // 색 바꿔주고
        z->parent->parent->color = RBTREE_RED; // 여기도 색 바꿔주고 & 여기서는 회전 없음.
        z= z->parent->parent; // ??? 왜 할부지 가리킴? => 할부지 밑으로 업뎃 끝났으니 그 위에서 다시 while문 돌아야 하니!
      }
      else {
        if (z == z->parent->left) { // 경우 2, 3: uncle color가 black일 때
          z = z->parent;
          right_rotation(t, z);
        }
        z->parent->color = RBTREE_BLACK;
        z->parent->parent->color = RBTREE_RED;
        left_rotation(t, z->parent->parent);
      }
    }
      
  }
  t->root->color = RBTREE_BLACK;

}