1. 삽입 함수 구현

레드블랙트리의 삽입 알고리즘을 구현해보면 다음과 같다.
아래의 코드에서 BLACK은 1, RED는 0으로 정의되었다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

// 레드블랙트리에 z 노드를 삽입하는 함수
void RBT_insert(RBTree *T, TreeNode * z)
{
  TreeNode * y = T->nil; // y 노드를 선언하여 nil을 할당한다.
  TreeNode * x = T->root; // x 노드를 선언하여 루트를 할당한다.

  while (x != T->nil) { // x가 nil이 아니면 반복문을 수행한다.
    y = x;              // y에 x를 할당한다. (y는 x를 한 레벨 차이로 쫓아내려온다)
    if (z->key < x->key) // z의 key가 x의 key보다 작으면
      x = x->left; // x에 x의 왼쪽 자식을 할당한다.
    else x = x->right; //z의 key가 x의 key보다 크면, x에 x의 오른쪽 자식을 할당한다.
  }

  z->parent = y; // z의 부모를 y로 변경한다.
  if (y == T->nil) // y가 nil이라면
    T->root = z; // z는 트리의 루트다.
  else if (z->key < y->key) // z의 key가 y의 key보다 작으면
    y->left = z; // y의 왼쪽 자식으로 z를 할당한다.
  else y->right = z; // z의 key가 y의 key보다 크면, y의 오른쪽 자식으로 z를 할당한다.

  z->left = T->nil; // z의 왼쪽 자식에 nil을 할당한다.
  z->right = T->nil; // z의 오른쪽 자식에 nil을 할당한다. 
  z->color = RED; // z의 색깔을 RED로 할당한다.

  RBT_insert_fixup(T, z); // RBT_insert_fixup 함수를 호출한다.
}

// 삽입 후 레드블랙트리의 규칙에 맞게 조정하는 함수
void RBT_insert_fixup(RBTree * T, TreeNode * z)
{
  while(z != T->root && z->parent->color == RED ){ // z의 부모 노드가 RED 색깔인 경우 반복문을 수행한다.
    if (z->parent == z->parent->parent->left) { // z의 부모가 왼쪽 자식 노드인 경우
      TreeNode * y = z->parent->parent->right; // z의 조부모의 오른쪽 자식 노드 y를 선언한다.
      if (y->color == RED) { // case 1: 삼촌 노드 y의 색깔이 RED인 경우
        z->parent->color = BLACK; // z의 부모 색깔을 BLACK으로 변경
        y->color = BLACK; // y의 색깔을 BLACK으로 변경
        z->parent->parent->color = RED; // z의 조부모의 색깔을 RED로 변경
        z = z->parent->parent; // z를 z의 조부모로 변경한다 (z의 조부모에서 같은 문제가 발생할 수 있으므로)
      } 
      else { // 삼촌 노드 y의 색깔이 BLACK인 경우 (nil 노드 포함)
        if (z == z->parent->right) { // case 2: z가 부모의 오른쪽 자식 노드인 경우
          z = z->parent; // z를 z의 부모로 변경한다.
          left_rotate(T, z); // left_rotate 함수를 호출
        } // case 3: z가 부모의 왼쪽 자식 노드인 경우
        z->parent->color = BLACK; // z의 부모의 색깔을 BLACK으로 변경
        z->parent->parent->color = RED; // z의 조부모의 색깔을 RED로 변경
        right_rotate(T, z->parent->parent); // z의 조부모를 기준으로 right_rotate 함수를 호출
      }
    } 
    else { // z의 부모가 오른쪽 자식 노드인 경우 (위 경우와 left-right가 대칭된다)
      TreeNode * y = z->parent->parent->left; // z의 조부모의 왼쪽 자식 노드 y를 선언한다.
      if (y->color == RED) { // case 4: 삼촌 노드 y의 색깔이 RED인 경우
        z->parent->color = BLACK; // z의 부모 색깔을 BLACK으로 변경
        y->color = BLACK; // y의 색깔을 BLACK으로 변경
        z->parent->parent->color = RED; // z의 조부모의 색깔을 RED로 변경
        z = z->parent->parent; // z를 z의 조부모로 변경한다 (z의 조부모에서 같은 문제가 발생할 수 있으므로)
      }
      else { // 삼촌 노드 y의 색깔이 BLACK인 경우 (nil 노드 포함)
        if (z == z->parent->left) { // case 5: z가 부모의 왼쪽 자식 노드인 경우
          z = z->parent; // z를 z의 부모로 변경한다.
          right_rotate(T, z); // right_rotate 함수 호출
        } // case 6: z가 부모의 오른쪽 자식 노드인 경우
        z->parent->color = BLACK; // z의 부모의 색깔을 BLACK으로 변경
        z->parent->parent->color = RED; // z의 조부모의 색깔을 RED로 변경
        left_rotate(T, z->parent->parent); // z의 조부모를 기준으로 left_rotate 함수 호출
      }
    }
  }
  T->root->color = BLACK;
}

2. 레드블랙트리의 블랙높이

레드블랙트리에는 ‘블랙높이’라는 것이 존재한다.
이는 특정한 노드로부터 리프노드까지의 경로상에 있는
블랙 노드의 개수를 의미한다.

레드블랙트리

시작 노드는 색깔이 블랙이더라도 포함되지 않음에 유의하자.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

// x 노드의 블랙높이를 계산하는 함수
int get_black_height(RBTree* T, TreeNode* x) {
  int black_node_count = 0;

  /* 레드블랙트리의 특성 4에 의하여, 
  x에서 어떤 경로로 내려가든 블랙높이는 동일하다. */
  while (x != T->nil) { // x가 nil 노드가 아니면 반복문을 수행한다.
    if (x->left != T->nil) // x의 왼쪽 자식이 존재한다면
      x = x->left; // x를 x의 왼쪽 자식으로 변경한다.
    else // 그렇지 않다면 (x가 단말 노드이거나 오른쪽 자식만 존재하는 경우)
      x= x->right; // x를 x의 오른쪽 자식으로 변경한다.

    // 노드의 색깔이 블랙이면 개수를 1 증가시킨다. (nil 노드 포함)
    if (x->color == BLACK)
      black_node_count++;
  }
  return black_node_count; // 블랙 노드의 개수를 반환한다.
}

3. 결과 출력

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

int main(void)
{
  RBTree* T = create_RBTree(); // 레드블랙트리 생성 및 초기화

  // 노드 생성
  TreeNode* node_30 = new_node(30); 
  TreeNode* node_20 = new_node(20); 
  TreeNode* node_10 = new_node(10); 
  TreeNode* node_40 = new_node(40); 
  TreeNode* node_50 = new_node(50); 
  TreeNode* node_60 = new_node(60); 

  // 레드블랙트리에 삽입
  RBT_insert(T, node_30);
  RBT_insert(T, node_20);
  RBT_insert(T, node_10);
  RBT_insert(T, node_40);
  RBT_insert(T, node_50);
  RBT_insert(T, node_60);

  // 결과 출력
  printf("삽입 결과\n");
  printf("=================================================\n");
  printf("node_20의 블랙높이: %d, 컬러: %d \n", 
  get_black_height(T, node_20), node_20->color);
  printf("node_10의 블랙높이: %d, 컬러: %d \n", 
  get_black_height(T, node_10), node_10->color);
  printf("node_40의 블랙높이: %d, 컬러: %d \n", 
  get_black_height(T, node_40), node_40->color);
  printf("node_30의 블랙높이: %d, 컬러: %d \n", 
  get_black_height(T, node_30), node_30->color);
  printf("node_50의 블랙높이: %d, 컬러: %d \n", 
  get_black_height(T, node_50), node_50->color);
  printf("node_60의 블랙높이: %d, 컬러: %d \n", 
  get_black_height(T, node_60), node_60->color);
  printf("     (컬러 1은 BLACK, 0은 RED) \n");
  printf("\n\n");

  return 0;
}

결과 이미지