[자료구조] 트리(Tree) 시리즈 5: 레드-블랙 트리(RB-Tree)란?

티스토리 뷰

자료구조

[자료구조] 트리(Tree) 시리즈 5: 레드-블랙 트리(RB-Tree)란?

bearn_soo 2024. 8. 4. 21:15

RB-Tree의 정의와 특성

Red-Black Tree(RB-Tree)는 자가 균형 이진 탐색 트리의 한 종류로, 각 노드에 추가적인 비트(색상)를 저장하여 트리의 균형을 유지한다.

주요 특성:

이진 탐색 트리의 모든 특성을 만족한다.
각 노드는 red 또는 black다.
트리의 균형을 유지하여 최악의 경우에도 O(log n)의 시간 복잡도를 보장한다.

RB-Tree의 규칙과 속성

RB-Tree는 다음 규칙을 만족해야 한다:

모든 노드는 red 또는 black이다.
루트 노드는 항상 black이다.
모든 리프 노드(NIL)는 black이다.
red 노드의 자식은 모두 black이어야한다. (red 노드는 연속될 수 없다)
임의의 노드에서 그 노드의 자손인 리프 노드에 이르는 모든 경로에는 동일한 개수의 black 노드가 있어야 한다.

이러한 규칙들로 인해 RB-Tree는 항상 근사적으로 균형을 이루게 된다.

3. RB-Tree의 주요 연산 (삽입, 삭제) 및 재조정 과정

삽입 연산

1. 일반적인 BST 삽입을 수행한다.

2. 삽입된 노드를 red로 칠한다.

node_t *rbtree_insert(rbtree *t, const key_t key) {
  node_t *z = (node_t*)calloc(1, sizeof(node_t));
  z->key = key;
  z->color = RBTREE_RED;  // 새 노드는 항상 빨간색

  node_t *y = t->nil;
  node_t *x = t->root;

  while (x != t->nil) {
    y = x;
    if (z->key < x->key)
      x = x->left;
    else
      x = x->right;
  }

  z->parent = y;
  if (y == t->nil)
    t->root = z;
  else if (z->key < y->key)
    y->left = z;
  else
    y->right = z;

  z->left = t->nil;
  z->right = t->nil;

  rbtree_insert_fixup(t, z);  // 속성 유지를 위한 재조정
  return t->root;
}

3. RB-Tree 속성을 위반한 경우, 다음 과정을 통해 재조정한다:

Case 1: 삼촌 노드가 red인 경우
Case 2: 삼촌 노드가 black이고 새 노드가 내부 노드인 경우
Case 3: 삼촌 노드가 black이고 새 노드가 외부 노드인 경우

void rbtree_insert_fixup(rbtree *t, node_t *z) {
  while (z->parent->color == RBTREE_RED) {
    if (z->parent == z->parent->parent->left) {
      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 {
        if (z == z->parent->right) {
          // Case 2: 삼촌이 검은색, z가 오른쪽 자식
          z = z->parent;
          rbtree_left_rotate(t, z);
        }
        // Case 3: 삼촌이 검은색, z가 왼쪽 자식
        z->parent->color = RBTREE_BLACK;
        z->parent->parent->color = RBTREE_RED;
        rbtree_right_rotate(t, z->parent->parent);
      }
    } else {
      // 대칭적인 경우
      // ...
    }
  }
  t->root->color = RBTREE_BLACK;
}

삭제 연산

1. 일반적인 BST 삭제를 수행한다.

int rbtree_erase(rbtree *t, node_t *z) {
  node_t *y = z;
  node_t *x;
  color_t y_original_color = y->color;

  if (z->left == t->nil) {
    x = z->right;
    rbtree_transplant(t, z, z->right);
  } else if (z->right == t->nil) {
    x = z->left;
    rbtree_transplant(t, z, z->left);
  } else {
    y = tree_minimum(z->right);
    y_original_color = y->color;
    x = y->right;
    if (y->parent == z)
      x->parent = y;
    else {
      rbtree_transplant(t, y, y->right);
      y->right = z->right;
      y->right->parent = y;
    }
    rbtree_transplant(t, z, y);
    y->left = z->left;
    y->left->parent = y;
    y->color = z->color;
  }

  if (y_original_color == RBTREE_BLACK)
    rbtree_delete_fixup(t, x);

  free(z);
  return 0;
}

2. 삭제된 노드나 이동된 노드가 black이었다면, 다음 과정을 통해 재조정한다:

Case 1: 형제 노드가 red인 경우
Case 2: 형제 노드가 black이고 형제의 양쪽 자식이 black인 경우
Case 3: 형제 노드가 black이고 내부 조카가 red, 외부 조카가 black인 경우
Case 4: 형제 노드가 black이고 외부 조카가 red인 경우

void rbtree_delete_fixup(rbtree *t, node_t *x) {
  while (x != t->root && x->color == RBTREE_BLACK) {
    if (x == x->parent->left) {
      node_t *w = x->parent->right;
      if (w->color == RBTREE_RED) {
        // Case 1: x의 형제 w가 빨간색
        w->color = RBTREE_BLACK;
        x->parent->color = RBTREE_RED;
        rbtree_left_rotate(t, x->parent);
        w = x->parent->right;
      }
      if (w->left->color == RBTREE_BLACK && w->right->color == RBTREE_BLACK) {
        // Case 2: x의 형제 w는 검은색, w의 두 자식이 모두 검은색
        w->color = RBTREE_RED;
        x = x->parent;
      } else {
        if (w->right->color == RBTREE_BLACK) {
          // Case 3: x의 형제 w는 검은색, w의 왼쪽 자식은 빨간색, 오른쪽 자식은 검은색
          w->left->color = RBTREE_BLACK;
          w->color = RBTREE_RED;
          rbtree_right_rotate(t, w);
          w = x->parent->right;
        }
        // Case 4: x의 형제 w는 검은색, w의 오른쪽 자식은 빨간색
        w->color = x->parent->color;
        x->parent->color = RBTREE_BLACK;
        w->right->color = RBTREE_BLACK;
        rbtree_left_rotate(t, x->parent);
        x = t->root;
      }
    } else {
      // 대칭적인 경우
      // ...
    }
  }
  x->color = RBTREE_BLACK;
}

RB-Tree 전체 구현

GitHub - hyunS00/rbtree-lab

Contribute to hyunS00/rbtree-lab development by creating an account on GitHub.

github.com

#include "rbtree.h"

#include <stdlib.h>
#include<stdio.h>

rbtree *new_rbtree(void) {
  rbtree *p = (rbtree *)calloc(1, sizeof(rbtree));
  node_t *nil = (node_t *)calloc(1, sizeof(node_t));
  nil->color = RBTREE_BLACK;
  nil->left = nil;
  nil->right = nil;
  nil->parent = nil;

  p->nil = nil;
  p->root = nil;
  return p;
}

void delete_rbtree_node(node_t *nil, node_t *node){
  if (node == nil)
    return;
  
  delete_rbtree_node(nil, node->left);
  delete_rbtree_node(nil, node->right);

  free(node);
}

void delete_rbtree(rbtree *t) {
  if (t == NULL)
    return;

  if (t->root == t->nil){
    free(t->nil);
    t->nil = NULL;
    free(t);
    t = NULL;
    return;
  }
  
  delete_rbtree_node(t->nil, t->root);
  free(t->nil);
  free(t);
}
void rbtree_left_rotate(rbtree *t, node_t *x){
  node_t *y = x->right; // x의 오른쪽 서브트리 y 결국 y를 끌어 올리고 x내려야 함
  x->right = y->left; // y의 왼쪽 서브트리를 x의 오른쪽 서브트리로 옮김

  // 옮겨진 y의 왼쪽서브트리의 루트가 nil이 아니라면 y의 부모를 x로 설정
  if (y->left != t->nil)
    y->left->parent = x;
  y->parent = x->parent; // y의 부모를 x의 부모로 설정

  // x의 부모가 nil이라는 것은 x가 root였던것
  if(x->parent == t->nil){
    t->root = y;
  }
  else if (x == x->parent->left) //x가 부모의 왼쪽 서브트리의 루트였다면
  {
    x->parent->left = y;
  }
  else
  {
    x->parent->right = y; // x가 부모의 오른쪽 서브트리의 루트였다면
  }
  // 서브트리와 부모노드의 관계를 설정후 y의 왼쪽 서브트리에 완전히 x를 옮김
  y->left = x;
  x->parent = y;
}

void rbtree_right_rotate(rbtree *t, node_t *x){
  node_t *y = x->left; // x의 왼쪽 서브트리 y 결국 y를 끌어 올리고 x내려야 함
  x->left = y->right; // y의 오른쪽 서브트리를 x의 왼쪽 서브트리로 옮김

  // 옮겨진 y의 오른쪽서브트리의 루트가 nil이 아니라면 y의 부모를 x로 설정
  if (y->right != t->nil)
    y->right->parent = x;
  y->parent = x->parent; // y의 부모를 x의 부모로 설정

  // x의 부모가 nil이라는 것은 x가 root였던것
  if(x->parent == t->nil){
    t->root = y;
  }
  else if (x == x->parent->right) //x가 부모의 오른쪽 서브트리의 루트였다면
  {
    x->parent->right = y;
  }
  else
  {
    x->parent->left = y; // x가 부모의 왼쪽 서브트리의 루트였다면
  }
  // 서브트리와 부모노드의 관계를 설정후 y의 오른쪽 서브트리에 완전히 x를 옮김
  y->right = x;
  x->parent = y;
}

void rbtree_insert_fixup(rbtree *t, node_t *z){
  // 삽입한 노드z는 red이기 때문에 z의 부모노드는 red가 되면 안됨
  // 부모 노드가 black이 될때 까지 재조정
  while (z->parent->color == RBTREE_RED)
  {
    if (z->parent == z->parent->parent->left) // z의 부모 노드가 조부모노드의 왼쪽인 경우
    {
      node_t *y = z->parent->parent->right; // z의 삼촌 노드
      if (y->color == RBTREE_RED){ // case1: 부모가 red이고 삼촌이 red이면 두 노드와 조부모 노드의 색을 switching
        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) // case2: 부모가 red이고 삼촌이 black일때 z가 오른쪽 자식인 경우 case3으로 만듦
        {
          z = z->parent; // z의 부모를 기준으로 왼쪽으로 회전
          rbtree_left_rotate(t,z);
        }
        // case3: 부모가 red이고 삼촌이 black일때 z가 왼쪽 자식인 경우
        z->parent->color = RBTREE_BLACK;
        z->parent->parent->color = RBTREE_RED;
        rbtree_right_rotate(t,z->parent->parent);
      }
    }
    else // z의 부모 노드가 조부모노드의 오른쪽인 경우
    {
      node_t *y = z->parent->parent->left; // z의 삼촌 노드
      if (y->color == RBTREE_RED){ // case1: 부모가 red이고 삼촌이 red이면 두 노드와 조부모 노드의 색을 switching
        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) // case2: 부모가 red이고 삼촌이 black일때 z가 왼쪽 자식인 경우
        {
          z = z->parent; // z의 부모를 기준으로 오른쪽으로 회전
          rbtree_right_rotate(t,z);
        }

        z->parent->color = RBTREE_BLACK;
        z->parent->parent->color = RBTREE_RED;
        rbtree_left_rotate(t,z->parent->parent);
      }
    }
  }
  // 루트가 빨간색인 경우 블랙으로 칠해줌
  t->root->color = RBTREE_BLACK;
}

node_t *rbtree_insert(rbtree *t, const key_t key) {
  node_t *y = t->nil; // 삽입할 노드의 위치를 탐색하는 노드
  node_t *x = t->root; // 삽입할 노드의 부모 노드

  // 삽입할 노드 z 생성 및 초기화
  node_t *z = (node_t*) calloc(1, sizeof(node_t));
  z->key = key;
 

  // z의 key 값에 따라 알맞은 자리로 이동
  while (x != t->nil)
  {
    y = x;
    // 삽입할 노드의 key값이 x의 key값보다 작다면 x의 왼쪽 자식 탐색
    if (z->key < x->key)
    {
      x = x->left;
    }
    // 삽입할 노드의 key값이 x의 key값보다 작다면 x의 오른쪽 자식 탐색
    else {
      x = x->right;
    }
  }

  // 삽일할 적절한 위치를 탐색후 z의 부모를 y로 설정
  z->parent = y;
  // 처음 삽입되는 노드라면
  if (y == t->nil)
  {
    t->root = z;
  }
  else if (z->key < y->key) // 탐색노드 x가 nil까지 내려가 왼쪽 자식이었는지 오른쪽 자식인지 판단을 못하기 떄문에 y의 어느 자식인지 판단
  {
    y->left = z;
  }
  else{
    y->right = z;
  }
  z->left = t->nil;
  z->right = t->nil;
  z->color = RBTREE_RED;
  // RBtree 규칙 위반여부 판단 후 조정
  rbtree_insert_fixup(t,z);
  return t->root;
}

node_t *rbtree_find(const rbtree *t, const key_t key) {
  node_t *x = t->root; // 위치를 탐색하는 노드

  // key 값에 따라 알맞은 자리로 이동
  while (x != t->nil)
  {
    // key가 있다면 x return
    if (key == x->key){
      return x;
    }
    // key값이 x의 key값보다 작다면 x의 왼쪽 자식 탐색
    if (key < x->key)
    {
      x = x->left;
    }
    // key값이 x의 key값보다 작다면 x의 오른쪽 자식 탐색
    else {
      x = x->right;
    }
  }

  return NULL;
}

void rbtree_trans_plant(rbtree *t, node_t *u, node_t *v){
  if (u->parent == t->nil) // u노드가 루트였다면 v를 루트로 지정
  {
    t->root = v;
  }
  else if (u == u->parent->left) // u노드가 부모의 왼쪽 자식 노드였다면 v를 u의 부모노드의 왼쪽 자식 노드로 지정
  {
    u->parent->left = v;
  }
  else // u노드가 부모의 오른쪽 자식 노드였다면 v를 u의 부모노드의 오른쪽 자식 노드로 지정
  {
    u->parent->right = v;
  }
  // v의 부모노드를 u의 부모노드로 설정
  v->parent = u->parent;
}

void rbtree_delete_fixup(rbtree *t, node_t *x) {
  while (x != t->root && x->color == RBTREE_BLACK) {
    if (x == x->parent->left) {
      node_t *w = x->parent->right;
      if (w->color == RBTREE_RED) {
        w->color = RBTREE_BLACK;
        x->parent->color = RBTREE_RED;
        rbtree_left_rotate(t, x->parent);
        w = x->parent->right;
      }
      if (w->left->color == RBTREE_BLACK && w->right->color == RBTREE_BLACK) {
        w->color = RBTREE_RED;
        x = x->parent;
      } else {
        if (w->right->color == RBTREE_BLACK) {
          w->left->color = RBTREE_BLACK;
          w->color = RBTREE_RED;
          rbtree_right_rotate(t, w);
          w = x->parent->right;
        }
        w->color = x->parent->color;
        x->parent->color = RBTREE_BLACK;
        w->right->color = RBTREE_BLACK;
        rbtree_left_rotate(t, x->parent);
        x = t->root;
      }
    } else {
      node_t *w = x->parent->left;
      if (w->color == RBTREE_RED) {
        w->color = RBTREE_BLACK;
        x->parent->color = RBTREE_RED;
        rbtree_right_rotate(t, x->parent);
        w = x->parent->left;
      }
      if (w->right->color == RBTREE_BLACK && w->left->color == RBTREE_BLACK) {
        w->color = RBTREE_RED;
        x = x->parent;
      } else {
        if (w->left->color == RBTREE_BLACK) {
          w->right->color = RBTREE_BLACK;
          w->color = RBTREE_RED;
          rbtree_left_rotate(t, w);
          w = x->parent->left;
        }
        w->color = x->parent->color;
        x->parent->color = RBTREE_BLACK;
        w->left->color = RBTREE_BLACK;
        rbtree_right_rotate(t, x->parent);
        x = t->root;
      }
    }
  }
  x->color = RBTREE_BLACK;
}

int rbtree_erase(rbtree *t, node_t *p) {
  node_t *y = p; // 삭제할 노드 p를 대체할 노드 y
  node_t *x; // 대체된 노드y의 자리에 대체될 노드 x;
  color_t y_origin_color = y->color; // 대체된 노드의 원래 색깔을 저장

  // 자식 노드가 한개 이하일 때 그냥 교체하면 됨
  if (p->left == t->nil) 
  {
    x = p->right;
    rbtree_trans_plant(t, p, p->right); // p노드의 자리에 p노드의 오른쪽 서브트리를 옮긴다
  }
  else if (p->right == t->nil)
  {
    x = p->left;
    rbtree_trans_plant(t, p, p->left); // p노드의 자리에 p노드의 왼쪽 서브트리를 옮긴다
  }
  // 자식노드가 2개일 때
  else{
    y = rbtree_minimum(t, p->right); // 삭제할 노드 p의 후임자 노드 y
    y_origin_color = y->color; // 후임자 노드 y의 색깔 업데이트
    x = y->right;

    if (y->parent != p) {
      rbtree_trans_plant(t, y, y->right);
      y->right = p->right;
      y->right->parent = y;
    } else {
      x->parent = y; // 대체 노드 x의 부모를 y로 설정
    }

    rbtree_trans_plant(t, p, y);
    y->left = p->left;
    y->left->parent = y;
    y->color = p->color;
  }
  // 사라진 색깔이 black이면 재조정
  if (y_origin_color == RBTREE_BLACK){
    rbtree_delete_fixup(t, x);
  }
  // 삭제할 노드 p 삭제
  free(p);
  p = NULL;
  return 0;
}

RB-Tree vs AVL Tree: 차이점과 선택 기준

차이점:

균형 조건: AVL 트리는 더 엄격한 균형 조건을 가진다.
높이: AVL 트리가 더 완벽한 균형을 이루어 높이가 더 낮을 수 있다.
재조정: RB-Tree는 최대 3번의 회전으로 재조정되지만, AVL 트리는 더 많은 회전이 필요할 수 있다.

선택 기준:

검색이 빈번한 경우: AVL 트리
삽입/삭제가 빈번한 경우: RB-Tree

RB-Tree의 실제 응용 (STL의 set, map 구현)

C++의 STL에서 set과 map은 RB-Tree로 구현되어 있다.

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

[자료구조] Set과 Map 근데 이제 해시와 트리를 곁들인 (0)	2024.10.08
[자료구조] 트리(Tree) 시리즈 4: AVL트리란?(AVL Tree)란? (0)	2024.08.04
[자료구조] 트리(Tree) 시리즈 3: 이진 탐색 트리(Binary Search Tree)란? (0)	2024.08.04
[자료구조] 트리(Tree) 시리즈 2: 이진 트리(Binary Tree)란? (0)	2024.08.04
[자료구조] 트리(Tree) 시리즈 1: 트리(Tree)란? (1)	2024.08.04

공지사항

최근에 올라온 글

최근에 달린 댓글

Total

Today

Yesterday

« 2024/12 »
일	월	화	수	목	금	토
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

글 보관함

초밥구이

티스토리 뷰