[C 언어] RBTree key 추가

유선·2024년 4월 9일

C 언어 RB-Tree 정글 4주차

CS

목록 보기

5/25

✔️ RBTree 이론 보고 오기 => 클릭

✔️ RBTree 구현 정리 노션 => 클릭

✔️ RBTree 구현 전체 코드 => 클릭

🎄 key 추가

tree_insert(tree, key): key 추가
=> 구현하는 ADT가 multiset이므로 이미 같은 key의 값이 존재해도 하나 더 추가 합니다.

새 노드 생성

새 노드를 동적으로 생성한다.
노드의 key를 입력받고, color를 RED로, 자식 노드들은 nil 노드로 설정한다.
이미 같은 key의 값이 존재해도 하나 더 추가 한다. (multiset)

새 노드를 삽입할 위치 탐색

루트 노드부터 탐색을 시작하여 탐색 중인 노드보다 key값이 작은 경우 왼쪽 자식으로, 큰 경우 오른쪽 자식으로 이동한다.
탐색 중인 노드의 자식 노드가 nil 노드인 경우, 새 노드를 해당 자식 노드로 추가하고, 반복문을 종료한다.
반복문 종료 후 새 노드의 부모를 지정한다.

불균형 조정

노드 삽입 후, 불균형을 해결해야한다.
새로 삽입된 노드는 항상 RED 색상으로 삽입되는데, 새로 삽입된 노드의 부모 노드가 RED인 경우, RB tree의 규칙을 위반하게 되어 불균형이 발생한다.
이 불균형을 해결하기 위해 총 3가지 케이스로 나누어 처리한다.

회전

구조를 바꾸면서도 이진탐색트리의 특징을 유지시키는 방법은 회전이다.

code

새로운 키 추가 코드

// 새로운 키를 RB 트리에 추가하는 함수
node_t *rbtree_insert(rbtree *t, const key_t key) {
  // 새로운 노드를 동적으로 할당, 초기화
  node_t *addnode = (node_t *)malloc(sizeof(node_t));
  addnode->key = key;
  addnode->left = t->nil;
  addnode->right = t->nil;
  addnode->color = RBTREE_RED;

  node_t *cur = t->root; // 현재 노드를 루트로 초기화
  node_t *parent = t->nil; // 부모 노드를 nil로 초기화

  // 새로운 노드를 삽입할 위치를 찾기
  while (cur != t->nil) {
    parent = cur;
    if (cur->key > key) {
      cur = cur->left;
    } else {
      cur = cur->right;
    }
  }

  addnode->parent = parent; // 추가된 노드의 부모를 설정

  if (parent == t->nil) {
    // 트리가 비어있는 경우 새로운 노드를 루트로 설정
    t->root = addnode;
  } else if (key < parent->key) {
    parent->left = addnode;
  } else {
    parent->right = addnode;
  }

  // 삽입된 노드에 대해 불균형 복구
  rbtree_insert_fixup(t,addnode);
  return addnode;
}

불균형 조정 코드

// 새로운 노드 삽입 후 발생한 불균형을 복구하는 함수
void rbtree_insert_fixup(rbtree *t,node_t *z) {
  while(z != t->root && z->parent->color == RBTREE_RED) {
    if(z->parent->parent->left == z->parent) {
      node_t *y = z->parent->parent->right;
      if(y->color == RBTREE_RED) {
        // Case 1: 부모와 삼촌이 모두 빨간색인 경우
        z->parent->color = RBTREE_BLACK;
        y->color = RBTREE_BLACK;
        z->parent->parent->color = RBTREE_RED;
        z = z->parent->parent;
      } else {
        // Case 2, 3: 부모는 빨간색이지만 삼촌은 검은색인 경우
        if(z == z->parent->right) {
          // Case 2: z가 부모의 오른쪽 자식인 경우
          z = z->parent;
          left_rotate(t,z);
        }
        // Case 3: z가 부모의 왼쪽 자식인 경우
        z->parent->color = RBTREE_BLACK;
        z->parent->parent->color = RBTREE_RED;
        right_rotate(t,z->parent->parent);
      }
    } else {
      // 대칭
      node_t *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 *x) {
  node_t *y = x->right; // y는 x의 오른쪽 자식 노드로 설정
  x->right = y->left; // x의 오른쪽 자식을 y의 왼쪽 자식으로 설정

  // 만약 y의 왼쪽 자식이 nil이 아니라면, 그 노드의 부모를 x로 설정
  if (y->left != t->nil) {
    y->left->parent = x;
  }

  // y의 부모를 x의 부모로 설정
  y->parent = x->parent;

  // 만약 x의 부모가 nil이라면, y를 새로운 루트로 설정
  if(x->parent == t->nil)
    t->root = y;

  // x가 x의 부모의 왼쪽 자식이라면, y를 x의 부모의 왼쪽 자식으로 설정
  else if (x == x->parent->left)
    x->parent->left = y;
  
  // y를 x의 부모의 오른쪽 자식으로 설정
  else 
    x->parent->right = y;

  // x를 y의 왼쪽 자식으로 설정
  y->left = x;

  // y를 x의 부모로 설정
  x->parent = y;
}

// 오른쪽으로 회전하는 함수 (left_rotate와 대칭)
void right_rotate(rbtree *t, node_t *x) {
  node_t *y = x->left;
  x->left = y->right;
  if (y->right != t->nil) {
    y->right->parent = x;
  }
  y->parent = x->parent;
  if(x->parent == t->nil)
    t->root = y;
  else if (x == x->parent->right)
    x->parent->right = y;
  else x->parent->left = y;
  y->right = x;
  x->parent = y;
}