RB_Tree(레드블랙트리)

이진트리의 경우 계속하여 큰값이나 작은값이 들어올 경우 노드가 한쪽으로 치우칠 수 가 있다.

이경우 특정 key값을 탐색하는데 시간이 늘어나는 단점이 있으며

이를 보완한 것이 자가균형이진탐색트리 Red-Black Tree이다.

RBtree의 특성

모든 노드의 색은 빨간색 혹은 검은색이다.
루트 노드는 검은색 이어야 한다.
모든 리프노드는 루트노드와 같은 검은색이다.
빨간색 노드의 자식은 모두 검은색이다.
루트노드에서 리프노드까지 가는 경로상 만나는 검은색 노드의 수는 모두 동일하다

RBtree 시간 복잡도 O(logn):

RBtree 삽입

기본적 삽입은 이진트리의 삽입과 같다 그러나 삽입과정에서 루트 노드는 검은색이어야 하며 빨간색 노드의 자식은 검은색이어야 한다는등 조건이 있어 RB트리의 특성을 만족하여 특정 key값의 삽입 혹은 삭제시 균형잡힌 트리를 회복하기 위해 아래와 같이 회전이 발생한다.

RB트리의 삽입 left회전&amp;amp;amp;amp;amp;amp;nbsp;

삽입과정에서 삽입되는 노드의 색들은 빨간색이며 만약 이것이 루트노드라면 검은색으로 바꾸어 주는 과정을 거친다.

따라서 맨처음 들어온 10은 빨간색 이었다 그다음 20은 10보다 크므로 10의 right노드로 들어온다.

그다음 들어올 30도 빨간색을 가지고 들어오며 10보다 크므로 riight 20보다 크므로 right 노드에 위치한다.

이때 20의 부모노드인30도 빨간색이라 <빨간색 노드의 자식은 모두 검은색> 이라는 조건을 어겼기 때문에 회복과정이 필요하다.

단순하게 30의 색을 검은색으로 바꾸면되지 않을까? 하지만 이렇게 되면

<루트노드에서 리프노드까지 가는 경로상 만나는 검은색 노드의 수는 모두 동일하다.>

위 규칙이 안맞게 된다.

위의경우에서는 LEFT 회전으로 RB트리의 조건을 만족시켜 주었다.

삽입과정의 문제 해결

위와같은 삽입 과정의 문제는 모두 새로 삽입되는 노드의 부모노드가 적색인 경우 발생하며

이를 해결하기 위한 경우는 크게 아래 3가지 경우로 나뉜다.

1. 삼촌노드가 red인경우

2. 삼촌은 검은색이며 새로 삽입한 노드가 부모노드의 오른쪽 자식인경우

3. 삼촌은 검은색이며 새로 삽입한 노드가 부모노드의 왼쪽 자식인경우

이다.

1. 삼촌 노드가 red인경우

부모노드 -&amp;amp;amp;amp;amp;amp;gt;검은색 조상노드-&amp;amp;amp;amp;amp;amp;gt;빨간색

삽입하는 노드를 z라고 할때 z의 부모와 삼촌(y) 모두 빨간색인 경우이다. z.p.p(z의 증부모)는 무조건 검은색이므로

z.p(z의 부모) 와 y를 검은색으로 칠하여 z와 z.p의 색이 모두 빨간색 이라는 문제가 해결 가능하다.

여기서 원래 빨간색이었던 z.p와 삼촌(y)를 검은색으로 칠해주었기 때문에 z.p.p를 빨간색으로 칠해 rb트리의 특성 5번째(루트노드에서 리프노드까지 가는 경로상 만나는 검은색 노드의 수는 모두 동일하다) 를 만족시킨다.

이렇게만 끝나면 좋지만 우리는 z.p.p를 빨간색으로 바꾸면서 이와 인접한 노드에서 또 문제가 발생할 수 있다. 그러므로 이제 z를 z.p.p로 바꿔주어 특성을 위반하는사항이 없는지 다시 검사하여야 한다.

(z를 z.p.p로 바꾸어 준다는 부분이 헷갈릴 수 있는데 z는 단순하게 검사를 하기위한 곳을 가리키는 포인터라고 생각하자.)

2. 삼촌은 검은색이며 새로 삽입한 노드가 부모노드의 오른쪽 자식인경우

경우 2와 3은 삼촌이 검은색며 삽입되는 노드(z) 가 왼쪽이나 오른쪽이냐로 나뉜다.

2번경우는 삼촌이 검은색이면서 z가 오른쪽 자식인 경우이다.

이 경우는 z를 LEFT 회전을 통해 왼쪽 자식으로 바꾼다 만약 이경우 z이 삼촌이 검은색이라면 경우 3으로 넘어가고 그렇지 않고 z.p가 적색인경우 경우 1로 넘어가나 위의 경우

z.p가 루트이므로 left회전으로 끝났다 :)

3. 삼촌은 검은색이며 새로 삽입한 노드가 부모노드의 왼쪽 자식인경우

2번과 반대로 RIGHT 회전을 해주면 해결된다.

// 타입 생성
typedef struct node_t {
  color_t color;
  key_t key;
  struct node_t *parent, *left, *right;
} node_t;

typedef struct {
  node_t *root;
  node_t *nil;  // for sentinel
} rbtree;

//left 로테이트
void left_rotate(rbtree *t, node_t *x)
{
  node_t *y = x->right;
  //x를 left 로테이션 하는 것이므로 x의 right 자리에 있는 노드가 현 x자리로 올것이다.
  x->right = y->left;

  if (y->left != t->nil)
  {
    y->left->parent = x;
  }
  y->parent = x->parent;
  if (x->parent == t->nil)
    t->root = y;
  else if (x == x->parent->left)
    x->parent->left = y;
  else
    x->parent->right = y;
  y->left = x;
  x->parent = y;
}

//right 로테이트
void right_rotate(rbtree *t, node_t *x)
{
  node_t *y = x->left;
  //x를 left 로테이션 하는 것이므로 x의 right 자리에 있는 노드가 현 x자리로 올것이다.
  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;
}

//삽입이후 특성을 확인해줄 fixup
node_t *rb_insert_fixup(rbtree *t, node_t *z)
{
  node_t *y;
  // node_t *g = grandparent(t, z);
 
    while (z->parent->color == RBTREE_RED)
    {
      if (z->parent == z->parent->parent->left)
      {
        y = z->parent->parent->right;
        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->right)
          {
            z = z->parent;
            left_rotate(t, z);
          }
          z->parent->color = RBTREE_BLACK;
          z->parent->parent->color = RBTREE_RED;
          right_rotate(t, z->parent->parent);
        }
      }
      else
      {
        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;
  return t->root;
}


node_t *rbtree_insert(rbtree *t, const key_t key)
{

  // TODO: implement insert
  node_t *x = t->root;
  node_t *y = t->nil;
  node_t *z = (node_t *)calloc(1, sizeof(node_t));
  z->key = key;
  //1. 현재 RBtree의 Root 값이 존재 하지 않는다면?삽입값이 root가 된다

  while (x != t->nil)
  {
    y = x;
    if (z->key < x->key)
      x = x->left;
    else
      x = x->right;
  }
  //이곳을 빠져나왔다는 것은 마지막 노드의 주소를 y에게 넘기고 왔다는뜻
  z->parent = y;
  //새로 들어가는 노드인 z는 맨 마지막노드의 자식일테니 y를 부모로
  if (y == t->nil)
  {
    t->root = z;
  }
  //y가 비었다면?RB트리의 root 값은 새로 들어온 z가 된다.
  else if (z->key < y->key)
  {
    y->left = z;
  }
  else
    y->right = z;

  z->left = t->nil;
  z->right = t->nil;
  z->color = RBTREE_RED;
  //새로 삽입되는 노드의 칼라는 초기 RED다 .

  //삽입이후 부모의 색상 비교
  rb_insert_fixup(t, z);

  return t->root;
}

코드가 길지만 천천히 보면 이해가 간다 :)

다음엔 삽입을 정리해 보겠다 :)

저작자표시 (새창열림)

'Algorithms과 자료구조' 카테고리의 다른 글

파이썬 알고리즘(소수찾기 에라토스 테네스 체) (0)	2022.02.06
해시테이블 (0)	2022.01.16
RB_TREE(삭제) (0)	2021.12.08

윤SW

RB_Tree(레드블랙트리)_삽입

RBtree의 특성

RBtree 시간 복잡도 O(logn):