[자료구조] Red-Black Tree (with C)

레드-블랙 트리(Red-Black Tree)를 공부하기 전에 트리(Tree), 이진 트리(Binary Tree), 이진 탐색 트리(Binary Searach Tree)에 대한 선행 학습이 필요함.

우선 왜 레드-블랙 트리(Red-Black Tree)라는 자료구조가 필요해졌는지 알기 위해 균형 이진 탐색 트리(Balanced Binary Search Tree)에 대해 알고 넘어가야 한다.

균형 이진 탐색 트리(Balanced Binary Search Tree)

이진 탐색 트리(Binary Search Tree)의 연산에서 최악의 경우 시간복잡도는 O(N)이 되는데 이 때 트리는 다음과 같이 구성된다.

이처럼 노드들이 한 쪽으로 쏠려버린 트리를 편향 트리(Degenerated Tree)라고 부른다.

편향 트리와 같이 밸런스가 맞지 않는 이진 탐색 트리를 불균형 이진 탐색 트리(Unbalanced Binary Search Tree)라고 부르고 반대로 완전 이진 탐색 트리와 같이 균형이 잡힌 트리를 균형 이진 탐색 트리(Balanced Binary Search Tree)라고 한다.

위처럼 편향 트리와 같은 경우를 방지하기 위해 즉, 추가되는 노드로 인해 높이가 점점 커지는 것을 막기 위해서 균형 이진 탐색 트리가 고안되었다.

균형 이진 탐색 트리는 노드의 삽입과 삭제가 일어나는 경우에 자동으로 그 높이를 작게 유지하도록 설계되었기 때문에 성능상 매우 유리하다.

이런 균형 이진 탐색 트리의 종류에는 여러가지가 있다. 그리고 그 중 레드-블랙 트리에 대해서 알아보고자 한다.

레드-블랙 트리(Red-Black Tree)

레드-블랙 트리는 다음과 같은 조건들을 무조건적으로 만족한다.

1. 모든 노드는 빨간색 또는 검정색이다.
2. 루트 노드는 항상 검정색이다.
3. 모든 말단 노드들은 검정색이다. (레드 블랙 트리에서의 말단 노드는 무조건 NIL node이다.)

NIL node? 자식 노드가 존재하지 않을 경우 NIL node라는 특수한 노드가 자식 노드로써 존재한다고 가정한다. 따라서 모든 말단 노드는 NIL node가 된다. 이는 레드-블랙 트리에 한정한 가정이다.

4. 빨간색 노드의 두 자식 노드는 검정색이다 (즉, 빨간색 노드가 연속해서 나올 수 없으며, 검정색 노드만이 빨간색 노드의 부모 노드가 될 수 있다.)
5. 임의의 노드에서 말단 노드로 가는 경로에서 만나는 검정색 노드의 수는 같다. (이 때, 현재 노드가 검정색이라면 세지 않는다.)

위 조건들을 항상 만족하는 레드-블랙 트리 연산의 시간복잡도는 다음과 같다.

연산	평균적인 시간복잡도	최악의 경우 시간복잡도
검색	O(log n)	O(log n)
삽입	O(log n)	O(log n)
삭제	O(log n)	O(log n)

6가지 조건들을 지켜가며 균형을 유지했을 때 최악의 경우에도 O(log n)의 실행 시간을 보장해주는 것을 알 수 있다.

이러한 레드-블랙 트리는 실시간 처리와 같은 실행시간이 중요한 경우와 일정한 실행 시간을 보장하는 또 다른 자료구조를 만드는데 이용될 수 있다.

특히 함수형 프로그래밍에서의 연관 배열이나 집합(Set)등을 레드-블랙 트리로 구현해 놓은 경우가 많다.

이제 연산에 대해 알아보자. (연산은 본인이 C언어를 이용해서 구현하는 과정에서 겪었던 우여곡절을 바탕으로 설명한다.)

검색 연산

레드-블랙 트리에서의 검색 연산은 이진 탐색 트리에서의 검색 연산과 같다. 즉, 찾고자 하는 Key 값을 가지고 루트 노드부터 시작해서 말단 노드까지 Key를 비교하는 연산을 반복적으로 수행해나간다.

/**
 * RB tree에서 노드를 찾음
 * @param t 탐색할 트리의 주소값
 * @param key 찾을 노드의 키값
*/
node_t *rbtree_find(const rbtree *t, const key_t key) {
  node_t *n = t -> root;

  // key를 가지고 반복적으로 노드를 탐색해나감.
  while (n != t -> nil) {
    if(n->key < key) {
      n = n-> right;
    }else if(n -> key > key) {
      n = n -> left;
    }else {
      return n;
    }
  }

  return NULL;
}

이 때 역시 Key 값을 기준으로 오른쪽 서브트리로 이동할지 또는 왼쪽 서브트리로 이동할지 결정되므로 O(log n)의 수행 시간이 소요된다.

검색 연산을 수행하다가 자식 노드가 NIL node인 노드를 만난다면 찾고자 하는 Key값을 가진 노드가 없다는 것이므로 NULL을 반환하면서 검색을 종료한다.

삽입 연산

레드-블랙 트리에서의 삽입 연산 또한 이진 탐색 트리에서의 삽입 연산과 동일하다. 그러나 레드-블랙 트리의 조건을 만족하기 위해서 후처리 과정이 필요하다. 이 때 후처리 과정에서 사용되는 트리 회전(tree rotation)에 대해 숙지해야 한다.

트리 회전

불균형한 트리를 이진트리로 만들기 위해서 노드의 위치를 바꾸는 과정을 회전이라고 표현하며 레드-블랙 트리에서의 회전은 왼쪽 회전, 오른쪽 회전으로 나뉜다. (트리의 회전 또한 다양한 형태가 있었지만 레드 블랙 트리에서의 회전을 바탕으로 학습했다.)

오른쪽 회전(right rotation)
왼쪽 회전(left rotation)

회전 연산의 의사 코드는 다음과 같다.

그리고 의사코드를 참고하여 구현한 회전 함수는 아래와 같다.

/**
 * x를 기준으로 left rotation을 수행한다.
 * @param tree 트리
 * @param x 기준 노드
*/
void left_rotation(rbtree *tree, node_t *x) {
  node_t *y;

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

  y -> left = x;
  x -> parent = y;
}

/**
 * x를 기준으로 right rotation을 수행한다.
 * @param tree 트리
 * @param x 기준 노드
 * 
*/
void right_rotation(rbtree *tree, node_t *x) {
  node_t *y;

  y = x -> left;
  x -> left = y -> right;

  if(y -> right != tree -> nil) {
    y -> right -> parent = x;
  }

  y -> parent = x -> parent;

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

  y -> right = x;
  x -> parent = y;
}

삽입 연산 과정에서 레드-블랙 트리의 조건이 위배되었을 때 위와 같은 회전 연산을 통해서 다시 균형을 유지할 수 있게 된다. 이제 삽입 연산 과정에서 레드-블랙 트리의 조건이 위배되는 상황에 대해 알아보도록 하자.

위에서 설명한 것과 같이 레드-블랙 트리에서의 삽입 연산은 이진 탐색 트리에서의 삽입 연산과 동일한 과정을 우선적으로 수행하게 된다. 그 후 새로 삽입된 노드를 빨간색 노드로 설정한다. 그리고 주변 노드들의 색에 따라 경우를 나누어 추가적인 연산을 수행해준다.

CASE 1. 새로 삽입되는 노드가 루트 노드에 위치할 때

새로 삽입되는 노드는 무조건 빨간색으로 설정된다. 하지만 새로 삽입되는 노드가 루트 노드에 위치하게 된다면 2번 조건(루트 노드는 항상 검정색이다.)을 위배하게 된다. 이 경우 루트 노드를 다시 검정색으로 칠해줌으로써 조건을 만족시킬 수 있다. 코드 상에서는 아래와 같이 Fixup 함수 내의 가장 마지막 줄에 위치한다.

  // 루트는 항상 검은색.
  t -> root -> color = RBTREE_BLACK;

CASE 2. 새로 삽입되는 노드의 부모 노드가 빨간색 & 삼촌 노드가 빨간색

나는 case 2를 수정하는 과정? 방법?을 Recoloring이라는 용어로 학습하였다. 즉 새로 삽입하려는 노드의 부모가 빨간색일 경우 4번 조건(빨간색 노드는 연속으로 나올 수 없다.)을 위반하게 되고 이 때 삼촌 노드를 기준으로 2가지 경우로 나눠서 Fixup을 진행한다. 삼촌 노드 또한 빨간색일 경우에 Recoloring을 진행함으로써 별다른 회전 연산 없이 조건을 다시 만족시킬 수 있다.

이 때 삽입된 노드의 부모 노드와 삼촌 노드를 검정색으로 다시 칠하고, 조부모 노드를 빨간색으로 다시 칠한다. 이러한 Recoloring을 통해 4번 조건을 다시 만족시키고 5번 조건 또한 위반되지 않는다. 하지만 여기서 주의해야할 점이 있다. Recoloring을 진행했을 때 할아버지 노드가 4번 조건을 또 다시 위반할 수 있으므로 Recoloring을 루트 노드까지 반복적으로 수행해주어야 한다. 나는 처음에 이 점을 생각하지 못하고 구현했다 그리고 3시간을 헤맸다. 결국 의사 코드를 바탕으로 다시 작성 했고 그렇게 완성된 코드는 아래와 같다. (Fixup 함수 내에서 조건문을 통해 수행해주고 있다.)

// 해당 조건문은 반복문 안에서 돌고 있음. -> 루트 노드까지 거슬러 올라가며 조건을 위반하는지 판단함.
if (y -> color == RBTREE_RED) {
        // z의 삼촌 y가 RED
        z -> parent -> color = RBTREE_BLACK;
        y -> color = RBTREE_BLACK;
        z -> parent -> parent -> color = RBTREE_RED;
        z = z -> parent -> parent;
      }

처음에 구현했던 코드를 공개하자면..

if(uncle) {
    // 삼촌이 레드일 경우 - Recoloring
    // 삽입된 노드의 부모와 삼촌 노드를 검은색으로, 부모의 부모 노드를 빨간색으로.
    my_parent -> color = RBTREE_BLACK;
    my_uncle -> color = RBTREE_BLACK;
    my_grand_parent -> color = RBTREE_RED;

    if (t -> root -> color == 0) {
      t -> root -> color = RBTREE_BLACK;
    }
}

단순하게 조건을 따라서 명시적으로 구현하고자 했기 때문에 해당 케이스를 반복적으로 체크해줘야 한다는 생각을 하지 못했다.

CASE 3. 새로 삽입되는 노드의 부모 노드가 빨간색 & 삼촌 노드가 검은색 또는 NIL node

case 3은 새로 삽입되는 노드의 부모 노드가 빨간색이고 삼촌 노드가 검정색인 경우이며, case 3 안에서 또 다른 케이스로 나뉜다.

새로 삽입되는 노드가 부모의 오른쪽 자식 노드: 부모를 기준으로 left_rotation(t, n -> parent)를 수행해준다. 그리고 부모였던 노드를 새로 삽인되는 노드로 생각하고 아래 2번 케이스의 과정을 진행해준다.
새로 삽입되는 노드가 부모의 왼쪽 자식 노드: 부모 노드를 검정색으로 칠하고 할아버지 노드를 빨간색으로 칠한 후에 할아버지 노드를 기준으로 right_rotation(t, p -> parent)를 수행해준다.

위의 경우에 따른 연산을 수행해준 뒤에 한번 더 생각해야 할 점은 새로 삽입되는 노드의 부모 노드의 위치이다. 부모 노드가 할아버지의 왼쪽 자식 노드일 경우와 오른쪽 자식 노드일 경우로 나누어서 정확히 반대의 경우로 나누어 코드를 짜야한다.

또한 case 3의 경우에도 회전 연산을 마쳤을 때 다시 조건을 위배하는 상황이 있을 수 있으므로 루트 노드까지 거슬러 올라가면서 조건을 체크해주는 것 또한 기억해야한다.

삽입 연산 시의 fixup 함수는 아래와 같다. (의사 코드를 바탕으로 작성했다.)

/**
 * 삽입 연산 과정 중 RBtree의 속성을 위배했을 경우 fix 수행
 * @param t 트리
 * @param z 새로 삽입 할 노드
*/
void rbtree_insert_fixup(rbtree *t, node_t *z) {
  node_t *y;
  
  while (z -> parent -> color == RBTREE_RED) {
    if (z -> parent == z -> parent -> parent -> left) {
      // z의 부모노드가 할아버지 노드의 왼쪽 노드일 경우
      y = z -> parent -> parent -> right;

      if (y -> color == RBTREE_RED) {
        // z의 삼촌 y가 RED
        z -> parent -> color = RBTREE_BLACK;
        y -> color = RBTREE_BLACK;
        z -> parent -> parent -> color = RBTREE_RED;
        z = z -> parent -> parent;
      }else {
        // z의 삼촌 y가 BLACK 
        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 {
      // z의 부모노드가 할아버지 노드의 오른쪽 노드일 경우
      y = z -> parent -> parent -> left;

      if (y -> color == RBTREE_RED) {
        // z의 삼촌 y가 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;
}

삽입 함수의 코드는 다음과 같다.

/**
 * RB tree에 노드를 추가한다.
 * @param t 
 * @param key
 * @return
 *  
*/
node_t *rbtree_insert(rbtree *t, const key_t key) {
  // TODO: implement insert
  node_t *y = t -> nil;
  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;
    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;
  z -> color = RBTREE_RED;

  rbtree_insert_fixup(t, z);

  return z;
}

삭제 연산

포스팅 예정..

출처 : 위키피디아 - 레드 블랙 트리(Red-Black Tree)

'Development > 자료구조 & 알고리즘' 카테고리의 다른 글

[알고리즘] 백준 12785 - 토쟁이의 등굣길 (0)	2023.05.13
[알고리즘] 백준 2225 - 합분해 (1)	2023.05.12
[알고리즘] 백준 14888 - 연산자 끼워넣기 (파이썬) (0)	2023.04.26
[알고리즘] 백준 21606 - 아침산책 (파이썬) (0)	2023.04.25
[알고리즘] 백준 10971 - 외판원 순회2 (파이썬) (0)	2023.04.12

write off

[자료구조] Red-Black Tree (with C)

균형 이진 탐색 트리(Balanced Binary Search Tree)

레드-블랙 트리(Red-Black Tree)

검색 연산

삽입 연산

트리 회전

CASE 1. 새로 삽입되는 노드가 루트 노드에 위치할 때

CASE 2. 새로 삽입되는 노드의 부모 노드가 빨간색 & 삼촌 노드가 빨간색

CASE 3. 새로 삽입되는 노드의 부모 노드가 빨간색 & 삼촌 노드가 검은색 또는 NIL node

삭제 연산

'Development > 자료구조 & 알고리즘' 카테고리의 다른 글

댓글

티스토리툴바

[자료구조] Red-Black Tree (with C)

균형 이진 탐색 트리(Balanced Binary Search Tree)

레드-블랙 트리(Red-Black Tree)

검색 연산

삽입 연산

트리 회전

CASE 1. 새로 삽입되는 노드가 루트 노드에 위치할 때

CASE 2. 새로 삽입되는 노드의 부모 노드가 빨간색 & 삼촌 노드가 빨간색

CASE 3. 새로 삽입되는 노드의 부모 노드가 빨간색 & 삼촌 노드가 검은색 또는 NIL node

삭제 연산

'Development > 자료구조 & 알고리즘' 카테고리의 다른 글

관련글

댓글

티스토리툴바

검색 연산

삽입 연산