rb-Tree

6 분 소요

RB-Tree(Red-Black Tree)

각 노드가 레드 혹은 블랙 인
이진 탐색 트리
(단순한 추가정보)

스스로 균형을 잡는 트리
(self-balancing tree)

트리 높이를 최소로 보장한다
삽입, 삭제 시 균형을 잡아준다

RB-Tree의 특성(properties)

모든 노드는 적색 혹은 흑색
루트 노드는 흑색이다
모든 리프 노드(NIL)는 흑색이다
적색 노드의 자식은 언제나 흑색이다
어떤 노드와 리프 노드 사이에 있는
흑색 노드 수는 동일하다

이러한 특성을 통해
적색 와 흑색 노드 수의 균형을 맞추고
삽입 삭제 시, 트리를 재배치하기도 함

리프 노드는 데이터를 담지 않음

black depth : 루트와 어떤 노드 사이에 있는 흑색 노드의 수
black height : 어떤 노드와 리프 사이에 있는 흑색 노드의 수

이러한 특성으로
RB-Tree는 가장 큰 리프의 길이가
작은 것의 2배를 넘지 않는것을 보장한다
=> BST의 ‘최악’의 경우를 방지하여 O(log N)을 보장

RB-Tree의 연산
탐색 : BST 와 동일 (단, O(log n)이 보장)
삽입 : O(log n) 보장
삭제 : O(log n) 보장
다만, 삽입과 삭제의 경우
특성이 망가질 수 있기에
이러한 특성을 고치려 트리 구조를 재배치(회전)하거나
노드의 색을 바꾼다
배우는 이유?
특정한 데이터를 보고
RB-Tree를 적용할 수 있을지를 판단할 수는 있어야 하므로

RB-Tree의 삽입(Insert)

BST와 같은 방식으로 삽입
추가하는 노드는 언제나 적색을 가진다
(언제나 리프에 추가)

이후, 조건을 만족할 때까지 트리를 고친다

삽입의 각종 상황(Case)

조건 : 검사 노드의 부모가 적색 노드(초기 검사 노드는 삽입된 노드의 왼쪽 자식)
삽입 노드의 삼촌 노드가 ‘적색’인 경우,
조부모의 색을 색과 부모, 삼촌의 색을 교환하기
이후 조부모를 검사 노드로 설정
삼촌 노드가 ‘흑색’이며, 검사 노드가 ‘오른쪽 자식’인 경우
좌회전 이후 4번 조건으로 넘어간다
삼촌 노드가 ‘흑색’이며, 검사 노드가 ‘왼쪽 자식’인 경우
조부모와 부모의 색을 바꾼 후, 우회전 해준다
검사 노드가 ‘오른쪽 자식’인 경우는 2,3,4 의 좌/우를 반대로 적용하여 해결한다

삽입 예시 코드 (C)

node_t *rbtree_insert(rbtree *t, const key_t key)
{
  if(t == NULL){
    printf("rbtree_insert in NULL point");
    return NULL;
  }

  node_t *newNode = (node_t *)calloc(1, sizeof(node_t));
  newNode->key = key;

  node_t *targetNode = t->root;
  node_t *prevNode = t->nil;

  // 노드 삽입 위치 찾기
  while (targetNode != t->nil)
  {
    prevNode = targetNode;
    // bst 규칙으로
    // 작은 값이라면 왼쪽으로 아니라면 오른쪽으로
    if (key < targetNode->key)
    {
      targetNode = targetNode->left;
    }
    else
    {
      targetNode = targetNode->right;
    }
  }

  // 트리가 비어있었음
  if (prevNode == t->nil)
  {
    t->root = newNode;
  }
  else if (newNode->key < prevNode->key)
  { // 키 값이 부모 노드보다 작음
    prevNode->left = newNode;
  }
  else
  {
    prevNode->right = newNode;
  }

  newNode->left = t->nil;
  newNode->right = t->nil;
  newNode->parent = prevNode;
  newNode->color = RBTREE_RED;

  rb_insert_fixup(t, newNode);

  return t->root;
}

삽입 후 트리 수정 예시 코드 (C)

void rb_insert_fixup(rbtree *t, node_t *z)
{
  // 속성 2,4 를 위반할 수 있으니 확인한다
  // 해당 내용은 모두 '부모가 red' 일 때 발생이 가능하다
  while (z->parent->color == RBTREE_RED)
  {
    if (z->parent == z->parent->parent->left)
    {                                               // 부모가 조부모의 왼쪽 자식
      node_t *uncleNode = z->parent->parent->right; // 삼촌 노드(조부모의 오른쪽 자식)
      if (uncleNode->color == RBTREE_RED)
      { // 삼촌 노드가 붉은 색
        // case 1 (부모와 삼촌 모두 red)
        z->parent->color = RBTREE_BLACK;
        uncleNode->color = RBTREE_BLACK;
        z->parent->parent->color = RBTREE_RED; // 조부모의 색을 red로 바꿔준다
        z = z->parent->parent;          // 조부모 입장에서 다시 체크해야 하기에 z를 바꿔준다
      }
      else
      {
        if (z == z->parent->right)
        { // 현재 노드가 부모의 오른쪽 자식
          // case 2
          // 부모를 기준으로 왼쪽 회전 후 case 3를 적용
          z = z->parent;
          rb_left_rotate(t,z);
        }
        // case 3
        z->parent->color = RBTREE_BLACK; // 부모색을 검게 (부모와 조부모 색 교환)
        z->parent->parent->color = RBTREE_RED;  // 조부모 색을 붉게(부모가 붉다는 가정이며, 또한 4번 규칙)
        rb_right_rotate(t,z->parent->parent);
      }
    }
    else // 부모가 조부모의 오른쪽 자식이므로 위의 코드의 좌우를 변경해준다
    {
      node_t *uncleNode = z->parent->parent->left; // 삼촌 노드(조부모의 왼쪽 자식)
      if (uncleNode->color == RBTREE_RED)
      { // 삼촌 노드가 붉은 색
        // case 1 (부모와 삼촌 모두 red)
        z->parent->color = RBTREE_BLACK;
        uncleNode->color = RBTREE_BLACK;
        z->parent->parent->color = RBTREE_RED; // 조부모의 색을 red로 바꿔준다
        z = z->parent->parent;          // 조부모 입장에서 다시 체크해야 하기에 z를 바꿔준다
      }
      else
      {
        if (z == z->parent->left)
        { // 현재 노드가 부모의 왼쪽 자식
          // case 2
          // 부모를 기준으로 오른쪽 회전 후 case 3를 적용
          z = z->parent;
          rb_right_rotate(t,z);
        }
        // case 3
        z->parent->color = RBTREE_BLACK; // 부모색을 검게 (부모와 조부모 색 교환)
        z->parent->parent->color = RBTREE_RED;  // 조부모 색을 붉게(부모가 붉다는 가정이며, 또한 4번 규칙)
        rb_left_rotate(t,z->parent->parent);
      }
    }
  }

  // root 의 색은 black 이여야 한다 (2번 규칙)
  t->root->color = RBTREE_BLACK;
}

RB-Tree의 삭제(Delete)

BST와 같은 방식으로 삭제한다
(리프 노드를 삭제
부모 노드 삭제 시,
Successor을 찾아 교환)

이 때, 색을 변경할 수 있으므로
‘지운 색’을 기억해야 한다

지운 노드가 검은 노드라면 트리를 고친다
(2,4,5 번 특성에 위배될 수 있기에)

삭제의 각종 상황(Case)

조건 : 검사 노드는 루트가 아니며
검은색이다 (초기 검사 노드는 노드 삭제 후, 대체될 노드)
(루트 노드의 경우는 마지막에 black을 대입해줌으로서 2번 특성을 지킬 수 있음)
1.1 검사노드는 부모의 왼쪽 자식임
검사노드의 형제가 적색인 경우,
형제를 흑색으로, 부모를 적색으로 바꾼 뒤
부모를 기준으로 좌회전 한다
이후 형제 노드를 재설정 한 뒤
3,4,5 번의 case를 검사한다
형제가 흑색이며, 형제의 두 자식이 흑색인 경우,
형제를 적색으로 만든 후, 검사 노드를 부모 노드로 바꿔준다
형제가 흑색이며, 형제의 왼쪽 자식만 적색인 경우,
형제의 왼쪽 자식을 흑색으로 만든 후,
형제를 적색으로 만든다
이후 형제를 기준으로 우회전 한 후
형제를 재설정하고 5번 case로 넘어간다
형제가 흑색이며, 형제의 오른쪽 자식만 적색인 경우,
형제의 색과 부모의 색을 바꾸고
형제의 우측 자식의 색을 흑색으로 바꾼다
이후 좌회전을 한 후
검사 노드를 루트 노드로 만든다
(루프 종료)
검사 노드가 부모의 오른쪽 자식인 경우,
2~5의 좌/우 를 뒤집어서 시행한다

삭제 예시 코드 (C)

int rbtree_erase(rbtree *t, node_t *z)
{
  if(t == NULL || z == NULL){
    printf("rbtree_erase in NULL point");
    return -1;
  }

  node_t* target = z; // 삭제할 노드
  color_t targetOriginColor = target->color;
  node_t* v = t->nil; // 대체할 노드

  if(z->left == t->nil)
  {
    v = z->right;
    rbtree_transplant(t,z,v);
  }
  else if(z->right == t->nil)
  {
    v = z->left;
    rbtree_transplant(t,z,v);
  }
  else // 삭제 노드의 자식이 2개 있는 상황
  {
    // 삭제 노드 기준의 succesor 값을 찾는다
    target = rbtree_find_succesor(t,z);
    if (target == NULL){
      printf("rbtree_erase cant find succesor!");
      return -1;
    }

    // 삭제 노드가 아니라 succesor의 색
    targetOriginColor = target->color;
    v = target->right;
    if (target->parent == z){ // succesor의 부모가 삭제 노드라면
      v->parent = target; // v는 원래 삭제될 위치로 이동될 것이기에 부모 재설정
    }
    else{
      rbtree_transplant(t,target,v);
      target->right = z->right;
      target->right->parent = target;
    }
    rbtree_transplant(t,z,target);
    target->left = z->left;
    target->left->parent = target;
    target->color = z->color;
  }

  if (targetOriginColor == RBTREE_BLACK)
  {
    rb_erase_fixup(t,v);
  }

  // 노드 삭제되었으므로 해제
  free(z);
  z = NULL;

  return 0;
}

삭제 후 트리 수정 예시 코드 (C)

void rb_erase_fixup(rbtree *t, node_t *z)
{
  if(t == NULL || z == NULL){
    printf("rb_erase_fixup in NULL point!");
    return;
  }

  node_t* temp = t->nil;

  while (z != t->root && z->color == RBTREE_BLACK)
  {
    if (z == z->parent->left)
    {
      temp = z->parent->right;
      if(temp->color == RBTREE_RED)
      {
        temp->color = RBTREE_BLACK;
        z->parent->color = RBTREE_RED;
        rb_left_rotate(t,z->parent);
        temp = z->parent->right;
      }

      if(temp->left->color == RBTREE_BLACK &&
      temp->right->color == RBTREE_BLACK)
      {
          temp->color = RBTREE_RED;
          z = z->parent;
      }
      else
      {
        if(temp->right->color == RBTREE_BLACK)
        {
          temp->left->color = RBTREE_BLACK;
          temp->color = RBTREE_RED;
          rb_right_rotate(t,temp);
          temp = z->parent->right;
        }

        temp->color = z->parent->color;
        z->parent->color = RBTREE_BLACK;
        temp->right->color = RBTREE_BLACK;
        rb_left_rotate(t,z->parent);
        z = t->root;
      }
    }
    else
    {
      temp = z->parent->left;
      if(temp->color == RBTREE_RED)
      {
        temp->color = RBTREE_BLACK;
        z->parent->color = RBTREE_RED;
        rb_right_rotate(t,z->parent);
        temp = z->parent->left;
      }

      if(temp->right->color == RBTREE_BLACK &&
      temp->left->color == RBTREE_BLACK)
      {
          temp->color = RBTREE_RED;
          z = z->parent;
      }
      else
      {
        if(temp->left->color == RBTREE_BLACK)
        {
          temp->right->color = RBTREE_BLACK;
          temp->color = RBTREE_RED;
          rb_left_rotate(t,temp);
          temp = z->parent->left;
        }

        temp->color = z->parent->color;
        z->parent->color = RBTREE_BLACK;
        temp->left->color = RBTREE_BLACK;
        rb_right_rotate(t,z->parent);
        z = t->root;
      }
    }
  }
  
  z->color = RBTREE_BLACK;
}

참고 자료

Introduction To Algorithms : 13_ RB Tree

Twitter Facebook LinkedIn

Hyun JaeHoon

rb-Tree

RB-Tree(Red-Black Tree)

RB-Tree의 특성(properties)

RB-Tree의 삽입(Insert)

RB-Tree의 삭제(Delete)

참고 자료

공유하기

댓글남기기

참고

Direct X InitDirect3D

Direct X Init 1

백준 Gold 5 A와 B

백준 Gold 4 동전 1