자료구조, rbtree insert

자료구조, rbtree insert

---

📌 RB-Insert

 
삽입노드는 항상 RED
왜? 삽입 후 모든 경로에 Black Height 영향을 주지 않기 때문.

rb-insert, 출처 : CLRS book

rbtree insert 이해

root부터 시작해 트리를 순회하면서 z노드(삽입노드)의 부모 위치를 찾아줍니다.
부모 위치(y)를 찾은 뒤 z노드의 부모를 y노드를 가리키도록 포인터로 설정해주고
z노드의 자식들은 모두 nil노드로, 컬러는 빨간색으로 설정해줍니다.
그런 다음, RB트리의 균형을 맞춰주는 함수로 이동!
 

📄 rbtree.c

node_t *rbtree_insert(rbtree *t, const key_t key) {
  // TODO: implement insert 
  node_t *y = t->nil; // y will be parent of z
  node_t *x = t->root;
  // 노드 크기 만큼의 동적 메모리 할당
  node_t *z = (node_t *)calloc(1, sizeof(node_t));
  // 입력받은 key 값 할당
  z->key= key;
  
  while (x != t->nil) {
      y = x; // root부터 시작해 z의 부모 노드가 될 노드 찾음
      if (z->key < x->key) {
          x = x->left;
      }
      // 작으면 오른쪽으로 한칸 내려감
      else {
          x = x->right;
      }
  };
  // nil까지 내려가서 z의 부모값으로 y 할당
  z->parent = y;

  if (y == t->nil){  // x가 값이 없어서 while문 패스시 , 
    t->root = z;  // root 주소에 할당
  }  
  else if (z->key < y->key){   //입력값 z가 부모값 y보다 크면
    y->left = z;   // 왼쪽 
  }
  else {
    y->right = z;  //오른쪽
  };

  // 삽입된 z  child nil , color red 
  z->left = t->nil;
  z->right = t->nil;
  z->color = RBTREE_RED;
  
  // rbtree 특성 위반 체크 
  rbtree_insert_fixup(t, z);

  return t->root;
}

 

---

📌 RB-Insert-Fixup

 
삽입노드가 Red인데, 삽입노드의 부모 노드도 Red이면 double Red가 되므로 RBtree의 균형이 깨진다.
그러므로 조정해준뒤, z노드의 할아버지노드(z.p.p)로 타고타고 올라가
double Red가 없어질 때까지 fix-up 작업을 진행해 준다.

RB-Insert-Fixup, 출처 : CLRS book

현재 추가한 노드를 가리키는 z, 이 z노드의 삼촌(u)의 컬러가 중요하다.
(Case1) u노드가 빨간색이면 recoloring 작업만 진행하고 z의 할아버지노드로 탐색 위치를 조정해준다.
 
u노드가 검정색일 경우, 두 가지로 나뉜다.
(Case2) z가 z부모의 왼쪽 자식일 때는 left-rotate 후, z의 할아버지 노드로 탐색 위치를 조정해준다.
(Case3) z가 z부모의 오른쪽 자식일 때는 recoloring & right-rotate 후, z의 할아버지 노드로 탐색 위치를 조정해준다.
 

📄 rbtree.c

void rbtree_insert_fixup(rbtree *t, node_t *z) {
  node_t *y;
  
  while (z->parent->color == RBTREE_RED) {
    // z의 부모가 조부모의 왼쪽 서브 트리일 경우
    if (z->parent == z->parent->parent->left) {
      y = z->parent->parent->right;
      
      // CASE 1 : 노드 z의 삼촌 y가 적색인 경우
      if (y->color == RBTREE_RED) {
        z->parent->color = RBTREE_BLACK;
        y->color = RBTREE_BLACK;
        z->parent->parent->color = RBTREE_RED;
        z = z->parent->parent;
      }
      // CASE 2 : z의 삼촌 y가 흑색이며의 z가 오른쪽 자식인 경우
      else {
        if (z == z->parent->right) {
          z = z->parent;
          rotate_left(t, z);
        }
        // CASE 3 : z의 삼촌 y가 흑색이며의 z가 오른쪽 자식인 경우
        z->parent->color = RBTREE_BLACK;
        z->parent->parent->color = RBTREE_RED;
        rotate_right(t, z->parent->parent);
      }
    }
    // z의 부모가 조부모의 왼쪽 서브 트리일 경우
    else {
      y = z->parent->parent->left;

      // CASE 4 : 노드 z의 삼촌 y가 적색인 경우
      if (y->color == RBTREE_RED) {
        z->parent->color = RBTREE_BLACK;
        y->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;
          rotate_right(t, z);
        }
        // CASE 6 : z의 삼촌 y가 흑색이며의 z가 오른쪽 자식인 경우
        z->parent->color = RBTREE_BLACK;
        z->parent->parent->color = RBTREE_RED;
        rotate_left(t, z->parent->parent);
      }
    }
  }
  t->root->color = RBTREE_BLACK;
}

---

전반적인 insert과정은 다음 그림과 같다.

rb insert 과정 이해

---

공부자료 1 : CLRS book (Introduction to Algorithms) 13장 레드 블랙 트리
공부자료 2 : 자료구조 레드-블랙 트리 쉽게 이해하기  https://code-lab1.tistory.com/62