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

정의

레드-블랙 트리 (Red-Black Tree) 는 각 노드에 색 (빨강/검정) 을 부여하고 5 가지 규약을 지켜 높이 O(log N) 을 보장하는 자가 균형 이진 탐색 트리. 삽입/삭제/탐색 모두 O(log N) 최악 시간에 처리.

1978년 Leonidas J. Guibas 와 Robert Sedgewick 이 2-3-4 트리의 이진 표현으로 고안. C++ STL std::map, Java TreeMap, Linux kernel CFS 스케줄러 등 산업계 표준 자료구조.

문제 상황과 동기

일반 이진 탐색 트리 (BST) 는 최악 O(N) 로 퇴화 (오름차순 삽입 시 사슬 트리). AVL Tree 는 엄격한 균형 (좌우 높이 차 ≤ 1) 으로 O(log N) 을 보장하지만 회전 빈도가 높다.

Red-Black Tree 는 느슨한 균형 (longest path ≤ 2 × shortest path) 으로 갱신 시 최대 3 회 회전 으로 복원 가능. 실무에서 평균 성능이 AVL 보다 좋아 널리 채택.

핵심 통찰: 2-3-4 트리를 이진 트리로 인코딩 하면 각 4-node 를 빨강 노드 2개로 쪼개고, 검정 노드만 세면 perfect balance. 빨강 노드는 “같은 레벨” 표시.

시각화

5 가지 규약

1. 모든 노드는 빨강 또는 검정.
2. 루트는 검정.
3. 모든 리프 (NIL) 는 검정.
4. 빨강 노드의 자식은 모두 검정 (빨강-빨강 연속 금지).
5. 모든 경로는 같은 수의 검정 노드 (black-height).

이 규약들이 보장하는 바: 가장 긴 경로 (빨강-검정 교대) ≤ 2 × 가장 짧은 경로 (모두 검정) → 높이 ≤ 2 log(N+1).

핵심 아이디어

Invariant

Black-height bh(x) = x 에서 리프까지의 검정 노드 개수 (x 자신 제외). 규약 5 에 의해 모든 경로의 bh 가 같다.

N 개 노드 트리의 black-height 를 h_b 라 하면:

N ≥ 2^{h_b} - 1   (완전 검정 트리 하한)
h_total ≤ 2 h_b   (규약 4, 빨강 연속 불가)
∴ h_total ≤ 2 log(N + 1)

회전

삽입/삭제 시 빨강-빨강 충돌이나 black-height 불균형을 색 재조정 + 회전 으로 복원:

좌회전 (Left Rotate):
    x              y
   / \            / \
  α   y    =>    x   γ
     / \        / \
    β   γ      α   β

회전은 O(1) 에 서브트리 모양만 바꾸고 inorder 순서는 불변.

알고리즘

삽입

insert(T, z):
    1. z 를 일반 BST 삽입 (z.color = RED)
    2. fix_insert(T, z)       # 규약 복원

fix_insert(T, z):
    while z.p.color == RED:   # 규약 4 위반
        if z.p == z.p.p.left:
            y = z.p.p.right   # uncle
            case 1: y.color == RED
                -> z.p, y 를 검정, z.p.p 를 빨강, z = z.p.p
            case 2: z == z.p.right
                -> 좌회전(z.p), z = z.p (case 3 으로)
            case 3: z == z.p.left
                -> 우회전(z.p.p), 색 바꿈, 종료
        else: (symmetric)
    T.root.color = BLACK

case 1: recolor (상향 전파). case 2,3: 최대 2 회전 + 종료.

삭제

delete(T, z):
    1. z 를 일반 BST 삭제, 실제 삭제된 노드 y 와 y 의 자식 x 파악
    2. if y.color == BLACK:
           fix_delete(T, x)

fix_delete(T, x):
    while x != T.root and x.color == BLACK:
        if x == x.p.left:
            w = x.p.right   # sibling
            case 1: w.color == RED
                -> w 를 검정, x.p 를 빨강, 좌회전(x.p)
            case 2: w 의 자식 모두 검정
                -> w 를 빨강, x = x.p (상향)
            case 3: w.right.color == BLACK
                -> w.left 를 검정, w 를 빨강, 우회전(w)
            case 4: w.right.color == RED
                -> w.right 를 검정, 좌회전(x.p), 종료
        else: (symmetric)
    x.color = BLACK

case 1~3 은 변환. case 4 가 최종 회전 + 종료. 최대 3 회전.

구현

// 간략 RB-Tree: 삽입만 (삭제는 코드 3배 길이)
#include <iostream>
using namespace std;
enum Color { RED, BLACK };
struct Node {
  int key; Color color; Node *p, *left, *right;
  Node(int k): key(k), color(RED), p(nullptr), left(nullptr), right(nullptr) {}
};
struct RBTree {
  Node* root;
  RBTree(): root(nullptr) {}
  void leftRotate(Node* x) {
      Node* y = x->right; x->right = y->left;
      if (y->left) y->left->p = x;
      y->p = x->p;
      if (!x->p) root = y;
      else if (x == x->p->left) x->p->left = y; else x->p->right = y;
      y->left = x; x->p = y;
  }
  void rightRotate(Node* x) {
      Node* y = x->left; x->left = y->right;
      if (y->right) y->right->p = x;
      y->p = x->p;
      if (!x->p) root = y;
      else if (x == x->p->right) x->p->right = y; else x->p->left = y;
      y->right = x; x->p = y;
  }
  void fixInsert(Node* z) {
      while (z->p && z->p->color == RED) {
          if (z->p == z->p->p->left) {
              Node* y = z->p->p->right;
              if (y && y->color == RED) { // case 1
                  z->p->color = BLACK; y->color = BLACK;
                  z->p->p->color = RED; z = z->p->p;
              } else {
                  if (z == z->p->right) { leftRotate(z->p); z = z->p; } // case 2
                  z->p->color = BLACK; z->p->p->color = RED; rightRotate(z->p->p); // case 3
              }
          } else { // symmetric
              Node* y = z->p->p->left;
              if (y && y->color == RED) {
                  z->p->color = BLACK; y->color = BLACK;
                  z->p->p->color = RED; z = z->p->p;
              } else {
                  if (z == z->p->left) { rightRotate(z->p); z = z->p; }
                  z->p->color = BLACK; z->p->p->color = RED; leftRotate(z->p->p);
              }
          }
      }
      root->color = BLACK;
  }
  void insert(int key) {
      Node* z = new Node(key), *y = nullptr, *x = root;
      while (x) { y = x; x = (key < x->key) ? x->left : x->right; }
      z->p = y;
      if (!y) root = z;
      else if (key < y->key) y->left = z; else y->right = z;
      fixInsert(z);
  }
  void inorder(Node* n) {
      if (n) { inorder(n->left); cout << n->key << (n->color == RED ? "R " : "B ");
               inorder(n->right); }
  }
};
int main() {
  RBTree t;
  int n; cin >> n;
  for (int i = 0, x; i < n; i++) { cin >> x; t.insert(x); }
  t.inorder(t.root); cout << "\n";
}

# 간략 RB-Tree (삽입만)
class Node:
  def __init__(self, key, color='R', p=None, left=None, right=None):
      self.key, self.color, self.p, self.left, self.right = key, color, p, left, right
​
class RBTree:
  def __init__(self):
      self.root = None
  def leftRotate(self, x):
      y = x.right; x.right = y.left
      if y.left: y.left.p = x
      y.p = x.p
      if not x.p: self.root = y
      elif x == x.p.left: x.p.left = y
      else: x.p.right = y
      y.left = x; x.p = y
  def rightRotate(self, x):
      y = x.left; x.left = y.right
      if y.right: y.right.p = x
      y.p = x.p
      if not x.p: self.root = y
      elif x == x.p.right: x.p.right = y
      else: x.p.left = y
      y.right = x; x.p = y
  def fixInsert(self, z):
      while z.p and z.p.color == 'R':
          if z.p == z.p.p.left:
              y = z.p.p.right
              if y and y.color == 'R':  # case 1
                  z.p.color = y.color = 'B'; z.p.p.color = 'R'; z = z.p.p
              else:
                  if z == z.p.right: self.leftRotate(z.p); z = z.p  # case 2
                  z.p.color = 'B'; z.p.p.color = 'R'; self.rightRotate(z.p.p)  # case 3
          else:  # symmetric
              y = z.p.p.left
              if y and y.color == 'R':
                  z.p.color = y.color = 'B'; z.p.p.color = 'R'; z = z.p.p
              else:
                  if z == z.p.left: self.rightRotate(z.p); z = z.p
                  z.p.color = 'B'; z.p.p.color = 'R'; self.leftRotate(z.p.p)
      self.root.color = 'B'
  def insert(self, key):
      z, y, x = Node(key), None, self.root
      while x:
          y = x; x = x.left if key < x.key else x.right
      z.p = y
      if not y: self.root = z
      elif key < y.key: y.left = z
      else: y.right = z
      self.fixInsert(z)
  def inorder(self, n):
      if n:
          self.inorder(n.left)
          print(f"{n.key}{n.color}", end=" ")
          self.inorder(n.right)
​
n = int(input())
arr = list(map(int, input().split()))
t = RBTree()
for x in arr: t.insert(x)
t.inorder(t.root); print()

7
7 3 18 10 22 8 11

3R 7B 8R 10B 11R 18B 22R

복잡도

AVL 보다 회전 횟수가 적어 평균 갱신 성능이 우수. 탐색은 AVL 이 근소하게 빠름 (더 낮은 높이).

변형 / 활용

함정

1. NIL 노드 처리

많은 교과서 구현은 sentinel NIL 노드를 두어 리프를 모두 NIL 로 통일. 실무에서는 nullptr 체크로 처리하는 게 메모리 효율적이지만 case 분기가 복잡.

2. 색 재조정 case 순서

uncle 색 체크 (case 1) 를 먼저 해야 case 2,3 로 넘어감. 순서 틀리면 무한 루프.

3. 삭제 복잡도

삽입은 case 3개, 삭제는 case 8개 (좌우 대칭 포함). 삭제 구현이 삽입보다 3배 길고 실수하기 쉬움. 산업 코드는 테스트 케이스 수백 개로 검증.

4. 회전 방향 혼동

leftRotate 는 오른쪽 자식을 위로 올림 (시계 반대). rightRotate 는 왼쪽 자식을 위로 (시계). 이름과 방향이 직관의 반대라 헷갈림.

BOJ 연습 문제

참고

• AVL 트리
• 이진 탐색 트리
• B-Tree
• Order Statistics Tree (augmented RB-Tree)