1. 배경

이진탐색트리는 최악의 경우,
즉 트리의 균형이 한쪽으로 치우칠 경우
O(n)의 시간복잡도를 갖는다.

이러한 단점을 보완하기 위해 제안된
자가균형(self-balancing) 트리 디자인으로
레드블랙트리, AVL 트리가 있다.

이번 글에서는 레드블랙트리 알고리즘에 대해 정리해본다.

2. 기본 원리

레드블랙트리는 이진탐색트리의 모든 노드에
블랙 또는 레드의 색을 칠하되
다음의 법칙을 만족해야 한다.

  1. 루트는 블랙이다.
  2. 모든 리프는 블랙이다.
  3. 레드 노드의 자식은 반드시 블랙이다. (블랙 노드의 자식은 어떤 색이든 상관없다)
  4. 루트에서 임의의 리프 노드에 이르는 경로에서 만나는 블랙 노드의 수는 동일하다. 중요

레드블랙트리

레드블랙트리에서의 리프는 일반적인 리프 노드와 다르다.
모든 NIL 포인터가 NIL라는 리프 노드를 가리킨다고 가정한다.

*NIL 포인터: 아무것도 가리키지 않는 빈(empty) 포인터

3. 레드블랙트리에서의 삽입

기본적으로 이진탐색트리에서의 삽입과 같다.
다만, 삽입된 노드(x)를 레드로 칠한다.

이때 만일 x의 부모 노드 p의 색깔이

  1. 블랙이라면 아무 문제가 없다.
  2. 레드라면 기본 원리 3에 위배된다.

그러므로 부모 노드인 p가 레드인 경우만 고려하면 된다.

레드블랙트리

이때 p2와 x의 형제 노드는 반드시 블랙임을 알 수 있다.
그리고 s의 색깔에 따라 두 경우로 나뉜다.

1) s가 레드인 경우

이 경우에는 p2는 레드로, p와 s는 블랙으로 바꾼다.

레드블랙트리

기본 원리 4를 충족시킨다는 것에 주목하자.
즉, 리프 노드에 이르는 경로에서
만나는 블랙 노드의 수가 전과 동일하다.

한편, p2의 부모 노드도 레드일 수 있다.
이는 재귀적으로 문제를 해결해야 한다.

2-1) s가 블랙이고, x가 오른쪽 자식인 경우

레드블랙트리

p의 서브트리를 Left-rotation 시킨다.
(rotation 대해서는 후술하겠다)
그리고 2-2로 이동한다.

2-2) s가 블랙이고, x가 왼쪽 자식인 경우

레드블랙트리

p2와 p의 색상을 바꾼다.
그리고 p2의 서브트리를 Right-rotation 시킨다.

기본 원리 4를 충족시킨다는 것에 주목하자.
즉, 리프 노드에 이르는 경로에서
만나는 블랙 노드의 수가 전과 동일하다.

4. Left/Right rotation

레드블랙트리에는 Left/Right rotation 함수가 필요하다.
이는 다음과 같다.

레드블랙트리

c언어를 기반으로 작성한 코드는 다음과 같다.

// x 노드를 중심으로 왼쪽으로 회전하는 함수
void left_rotate(RBTree *T, TreeNode * x) {
  TreeNode * y = x->right; // x의 오른쪽 노드를 y로 선언한다.

  x->right = y->left; // x의 오른쪽 노드에 y의 왼쪽 자식을 할당한다.

  if (y->left != T->nil) // y의 왼쪽 자식이 nil 노드가 아니라면
    y->left->parent = x; // y의 왼쪽 자식의 부모를 x로 할당한다.

  y->parent = x->parent; // y의 부모에 x의 부모를 할당한다. 
  if (x->parent == T->nil) // x가 트리의 루트 노드였다면
    T->root = y; // y가 새로운 루트다.
  else if (x == x->parent->left) // x가 부모의 왼쪽 자식 노드였다면
    x->parent->left = y;
  else // x가 부모의 오른쪽 자식 노드였다면
    x->parent->right = y;

  y->left = x; // y의 왼쪽 자식으로 x를 할당한다.
  x->parent = y; // x의 부모로 y를 할당한다.
}

// x 노드를 중심으로 오른쪽으로 회전하는 함수
void right_rotate(RBTree *T, TreeNode * x) {
  TreeNode * y = x->left; // x의 왼쪽 노드를 y로 선언한다.

  x->left = y->right; // x의 왼쪽 노드에 y의 오른쪽 자식을 할당한다.

  if (y->right != T->nil) // y의 오른쪽 자식이 nil 노드가 아니라면
    y->right->parent = x; // y의 오른쪽 자식의 부모를 x로 할당한다.

  y->parent = x->parent; // y의 부모에 x의 부모를 할당한다. 
  if (x->parent == T->nil) // x가 트리의 루트 노드였다면
    T->root = y; // y가 새로운 루트다.
  else if (x == x->parent->left) // x가 부모의 왼쪽 자식 노드였다면
    x->parent->left = y;
  else // x가 부모의 오른쪽 자식 노드였다면
    x->parent->right = y;

  y->right = x; // y의 오른쪽 자식으로 x를 할당한다.
  x->parent = y; // x의 부모로 y를 할당한다.
}

레드블랙트리 알고리즘은 시간복잡도가 O(1)로, 상수의 시간이 걸린다.
즉, 오버헤드가 그리 크지 않다.

레드블랙트리 알고리즘을 활용해
트리의 균형을 유지하는 것은 이득이 된다.

참고문헌

그 외 알아둘 것들

  • 레드블랙트리보다 AVL 트리가 균형을 더 잘 잡는 편이다.