42경산 & 알고리즘/자료구조 & 코테

[자료구조/C언어] 레드-블랙 트리(Red-Black Tree) 규칙·회전·삽입·삭제 정리

kugorang 2024. 2. 18. 23:57
728x90

TL;DR (세 줄 요약)

  1. 레드-블랙 트리는 노드마다 빨강 또는 검정 색을 붙이고, 색에 대한 다섯 가지 규칙을 지키는 이진 탐색 트리입니다.
  2. 이 규칙 덕분에 트리의 높이가 log n 수준으로 유지됩니다. 그래서 탐색, 삽입, 삭제가 최악의 경우에도 O(log n) 시간에 끝납니다.
  3. 삽입이나 삭제로 규칙이 깨지면 색을 바꾸거나(재색칠) 회전으로 구조를 바꿔서 고칩니다. 삽입은 삼촌 노드의 색을, 삭제는 형제 노드의 색을 보고 처리 방법을 고릅니다.

이 글은 크래프톤 정글 4기 Part 2 "탐험 준비" 4주차에 레드-블랙 트리를 공부하면서 정리한 기본 개념입니다. 먼저 알아야 하는 개념, 다섯 가지 규칙, 회전, 삽입, 삭제 순서로 설명합니다.

화이트보드에 검은색 펜으로 모자를 쓴 사람 모양을 그리고 양손을 빨간색 동그라미로 칠한 뒤 아래에 Mr. RB Tree라고 쓴 그림
그림. 화이트보드에 그린 레드-블랙 트리 캐릭터 Mr. RB Tree

1. 레드-블랙 트리는 무엇인가요?

레드-블랙 트리(Red-Black Tree)는 균형 이진 탐색 트리의 한 종류입니다. 각 노드에 빨강 또는 검정 색을 붙입니다. 그리고 색에 대한 규칙을 지키면서 트리의 높이를 낮게 유지합니다.

이 구조는 실제 라이브러리에서 쓰입니다. C++ 표준 라이브러리의 map, set, multimap, multiset은 주요 구현(GCC의 libstdc++, LLVM의 libc++, Microsoft의 STL)에서 레드-블랙 트리로 만들어져 있습니다. Java의 TreeMap도 레드-블랙 트리로 만들어져 있습니다.

개념 자체는 많지 않습니다. 하지만 이해하려면 먼저 알아야 하는 것이 있습니다.

2. 먼저 무엇을 알아야 하나요?

트리는 노드(값을 담는 칸)를 부모와 자식 관계로 이은 자료구조입니다. 맨 위 노드를 루트라고 부릅니다. 루트에서 가장 먼 노드까지 내려가는 단계 수를 높이라고 부릅니다.

개념뜻
이진 트리각 노드가 자식을 최대 두 개까지 가지는 트리입니다.
이진 탐색 트리왼쪽 자식 < 부모 < 오른쪽 자식 순서를 지키는 이진 트리입니다. 값을 찾을 때 한 번 비교할 때마다 한쪽 서브트리를 통째로 제외할 수 있습니다.
균형왼쪽과 오른쪽의 높이가 크게 차이 나지 않는 상태입니다. 트리가 한쪽으로만 길게 늘어지면 높이가 n이 되어 탐색이 느려집니다. 균형을 유지하면 높이가 log n에 가까워집니다.
재귀함수가 자기 자신을 다시 호출하는 방식입니다. 트리의 삽입과 삭제를 구현할 때 자주 씁니다.
회전부모와 자식의 위치를 바꿔 트리 모양을 바꾸는 연산입니다. 노드의 값은 바꾸지 않고 구조만 바꿉니다.

여기서 n은 노드의 개수입니다. log n은 n을 몇 번 절반으로 나누면 1이 되는지를 나타내는 수입니다. 예를 들어 n이 1,024이면 log n은 10입니다.

3. 다섯 가지 규칙은 무엇인가요?

  1. 모든 노드는 빨강 또는 검정입니다.
  2. 루트는 검정입니다.
  3. 모든 리프(NIL)는 검정입니다. NIL은 값이 없는 끝 노드입니다. 자식이 없는 자리에 NIL이 있다고 봅니다.
  4. 빨강 노드의 자식은 모두 검정입니다. 그래서 빨강 노드가 위아래로 연속해서 나오지 않습니다.
  5. 어떤 노드에서 출발하든, 그 아래 리프까지 가는 모든 경로에 있는 검정 노드의 수가 같습니다.

이 규칙은 왜 높이를 제한하나요?

4번 규칙 때문에 한 경로에서 빨강 노드가 연속해서 나올 수 없습니다. 그래서 한 경로에서 빨강 노드의 수는 검정 노드의 수보다 많을 수 없습니다. 5번 규칙 때문에 모든 경로의 검정 노드 수가 같습니다.

두 규칙을 합치면, 가장 긴 경로도 가장 짧은 경로의 두 배를 넘지 않습니다. 경로가 가장 짧은 경우는 검정 노드만 있는 경우이고, 가장 긴 경우는 검정과 빨강이 번갈아 나오는 경우이기 때문입니다.

이 성질에서 노드가 n개인 레드-블랙 트리의 높이는 2 × log(n+1)을 넘지 않는다는 결과가 나옵니다. 탐색, 삽입, 삭제는 높이만큼만 내려가거나 올라가면 됩니다. 그래서 최악의 경우에도 O(log n) 시간에 끝납니다. O(log n)은 걸리는 시간이 log n에 비례해 늘어난다는 뜻입니다.

삽입과 삭제 중에 규칙이 깨지면 두 가지 방법으로 고칩니다.

  • 재색칠: 노드의 색을 바꿉니다.
  • 회전: 트리의 구조를 바꿉니다.

4. 회전은 어떻게 하나요?

회전은 한쪽으로 기울어진 부분을 반대쪽으로 넘기는 연산입니다. 기준 노드가 아래로 내려가고, 기준 노드의 자식 하나가 위로 올라옵니다. 회전한 뒤에도 "왼쪽 자식 < 부모 < 오른쪽 자식" 순서는 그대로 유지됩니다.

기본 회전은 오른쪽 회전과 왼쪽 회전 두 가지입니다. 이 둘을 한 번 쓰거나 두 번 이어 써서 네 가지 모양을 고칩니다.

아래 예시에서 a(b(d, e), c)는 다음을 뜻합니다. a의 왼쪽 자식이 b이고 오른쪽 자식이 c입니다. b의 왼쪽 자식이 d이고 오른쪽 자식이 e입니다.

이름기울어진 모양고치는 방법
LL 회전왼쪽 자식의 왼쪽이 깁니다.기준 노드를 오른쪽으로 한 번 회전합니다.
RR 회전오른쪽 자식의 오른쪽이 깁니다.기준 노드를 왼쪽으로 한 번 회전합니다.
LR 회전왼쪽 자식의 오른쪽이 깁니다.왼쪽 자식을 왼쪽으로 회전한 뒤, 기준 노드를 오른쪽으로 회전합니다.
RL 회전오른쪽 자식의 왼쪽이 깁니다.오른쪽 자식을 오른쪽으로 회전한 뒤, 기준 노드를 왼쪽으로 회전합니다.

LL 회전: 왼쪽-왼쪽으로 기울었을 때는 어떻게 하나요?

a(b(d, e), c)에서 a를 기준으로 오른쪽으로 회전하면 b(d, a(e, c))가 됩니다. b가 위로 올라옵니다. a는 b의 오른쪽 자식이 됩니다. b의 오른쪽 자식이던 e는 a의 왼쪽 자식으로 옮겨 갑니다.

RR 회전: 오른쪽-오른쪽으로 기울었을 때는 어떻게 하나요?

a(b, c(d, e))에서 a를 기준으로 왼쪽으로 회전하면 c(a(b, d), e)가 됩니다. c가 위로 올라옵니다. a는 c의 왼쪽 자식이 됩니다. c의 왼쪽 자식이던 d는 a의 오른쪽 자식으로 옮겨 갑니다.

LR 회전: 왼쪽 자식이 오른쪽으로 기울었을 때는 어떻게 하나요?

a(b(?, d(e, f)), c)처럼 왼쪽 자식 b의 오른쪽이 길면 두 단계가 필요합니다. 여기서 ?는 어떤 노드가 와도 상관없는 자리입니다.

  1. b를 기준으로 왼쪽 회전을 합니다. 그러면 LL 모양이 됩니다.
  2. a를 기준으로 오른쪽 회전을 합니다.

RL 회전: 오른쪽 자식이 왼쪽으로 기울었을 때는 어떻게 하나요?

LR의 좌우를 뒤집은 경우입니다.

  1. 오른쪽 자식을 기준으로 오른쪽 회전을 합니다. 그러면 RR 모양이 됩니다.
  2. 기준 노드를 왼쪽으로 회전합니다.

네 가지 회전의 목적은 모두 같습니다. 높이 차이를 줄여서 규칙을 다시 지키게 만드는 것입니다.

5. 삽입은 어떻게 하나요?

삽입은 두 단계입니다.

  1. 이진 탐색 트리와 같은 방식으로 자리를 찾아 값을 넣습니다.
  2. 새 노드를 빨강으로 칠합니다.

빨강으로 넣으면 5번 규칙(경로별 검정 수)은 깨지지 않습니다. 깨질 수 있는 규칙은 두 가지입니다.

  • 2번 규칙: 새 노드가 루트이면 루트가 빨강이 됩니다. 이때는 루트를 검정으로 바꾸면 됩니다.
  • 4번 규칙: 부모가 빨강이면 빨강 부모 아래에 빨강 자식이 생깁니다.

부모가 검정이면 고칠 것이 없습니다. 부모가 빨강이면 새 노드에서 위로 올라가며 규칙을 확인합니다. 이때 삼촌 노드의 색을 봅니다. 삼촌은 부모의 형제이고, 조부모는 부모의 부모입니다. 삼촌 자리가 NIL이면 검정으로 봅니다.

경우 1: 부모가 조부모의 왼쪽 자식일 때는 어떻게 하나요?

상황처리
삼촌이 빨강부모와 삼촌을 검정으로, 조부모를 빨강으로 바꿉니다. 회전은 필요 없습니다. 조부모가 빨강이 되어 조부모에서 같은 문제가 생길 수 있습니다. 그래서 조부모로 올라가 다시 확인합니다.
삼촌이 검정이고 새 노드가 부모의 오른쪽 자식부모를 기준으로 왼쪽 회전을 합니다. 그러면 아래 줄의 모양이 되므로 아래 줄의 처리로 넘어갑니다.
삼촌이 검정이고 새 노드가 부모의 왼쪽 자식부모를 검정으로, 조부모를 빨강으로 바꿉니다. 그리고 조부모를 기준으로 오른쪽 회전을 합니다. 여기서 조정이 끝납니다.

경우 2: 부모가 조부모의 오른쪽 자식일 때는 어떻게 하나요?

경우 1의 좌우를 뒤집은 것입니다.

  • 삼촌이 빨강이면 색만 바꾸고 조부모로 올라갑니다.
  • 삼촌이 검정이고 새 노드가 부모의 왼쪽 자식이면, 부모를 기준으로 오른쪽 회전을 한 번 합니다. 그리고 다음 줄의 처리로 넘어갑니다.
  • 삼촌이 검정이고 새 노드가 부모의 오른쪽 자식이면, 부모를 검정으로, 조부모를 빨강으로 바꿉니다. 그리고 조부모를 기준으로 왼쪽 회전을 합니다.

조정이 모두 끝나면 마지막에 루트를 검정으로 칠합니다. 삼촌이 빨강인 경우를 반복하다가 루트가 빨강이 될 수 있기 때문입니다.

6. 삭제는 어떻게 하나요?

삭제는 삽입보다 경우가 많습니다. 먼저 지울 노드를 찾습니다. 그다음 자식 수에 따라 다르게 처리합니다.

지울 노드의 자식 수처리
없거나 하나지울 노드의 자리를 자식으로 채우고 노드를 지웁니다. 자식이 없으면 그 자리는 NIL이 됩니다.
둘오른쪽 서브트리에서 가장 작은 노드를 찾습니다. 그 노드의 값을 지울 노드에 복사합니다. 지울 노드의 색은 그대로 둡니다. 그다음 가장 작은 노드를 대신 지웁니다. 이 노드는 왼쪽 자식이 없으므로, 삭제 문제가 자식이 하나 이하인 경우로 줄어듭니다.

그다음 트리에서 실제로 빠진 노드의 색을 봅니다.

  • 빠진 노드가 빨강이면 규칙이 깨지지 않습니다.
  • 빠진 노드가 검정이고 그 자리를 채운 자식이 빨강이면, 그 자식을 검정으로 바꾸면 됩니다.
  • 빠진 노드가 검정이고 그 자리를 채운 노드도 검정(NIL 포함)이면, 그 경로의 검정 수가 하나 줄어 5번 규칙이 깨집니다. 이때 자리를 채운 노드가 검정을 하나 더 가지고 있다고 보고 조정합니다. 이 상태를 이중 검정(double black)이라고 부릅니다.

삭제 후 조정 네 가지는 무엇인가요?

이중 검정 노드의 형제 색과, 형제의 두 자식 색을 보고 처리합니다. "가까운 자식"은 형제의 자식 중 이중 검정 노드 쪽에 있는 자식입니다. "먼 자식"은 반대쪽 자식입니다.

상황처리
형제가 빨강형제를 검정으로, 부모를 빨강으로 바꿉니다. 그리고 부모를 기준으로 이중 검정 노드 쪽으로 회전합니다. 그러면 새 형제가 검정이 되어 아래 세 경우 중 하나로 바뀝니다.
형제가 검정이고 형제의 두 자식이 모두 검정형제를 빨강으로 바꿉니다. 부모가 빨강이면 부모를 검정으로 바꾸고 끝냅니다. 부모가 검정이면 부모가 이중 검정이 되므로 부모에서 같은 조정을 다시 합니다.
형제가 검정이고 가까운 자식이 빨강, 먼 자식이 검정가까운 자식을 검정으로, 형제를 빨강으로 바꿉니다. 그리고 형제를 기준으로 이중 검정 노드의 반대쪽으로 회전합니다. 그러면 먼 자식이 빨강인 아래 경우가 됩니다.
형제가 검정이고 먼 자식이 빨강형제에게 부모의 색을 줍니다. 부모와 먼 자식을 검정으로 바꿉니다. 그리고 부모를 기준으로 이중 검정 노드 쪽으로 회전합니다. 여기서 조정이 끝납니다.

7. 한 번에 정리하면 어떻게 되나요?

  • 레드-블랙 트리는 값의 순서를 지키는 이진 탐색 트리에 색 규칙을 더해 높이를 낮게 유지합니다.
  • 삽입은 새 노드를 빨강으로 넣고, 삼촌의 색을 보고 처리합니다.
  • 삭제는 검정 노드가 빠졌을 때, 형제의 색과 형제 자식의 색을 보고 네 가지로 처리합니다.

규칙과 회전을 외우기보다 "왜 이 규칙이 높이를 제한하는가"를 먼저 이해하면 경우의 수를 정리하기 쉽습니다.

자주 묻는 질문 (FAQ)

Q1. 레드-블랙 트리는 왜 필요한가요?

이진 탐색 트리는 값이 정렬된 순서로 들어오면 한쪽으로 길게 늘어집니다. 이때 높이가 n이 되어 탐색에 n번에 가까운 비교가 필요합니다. 레드-블랙 트리는 색 규칙으로 높이를 log n 수준으로 유지합니다. 그래서 탐색, 삽입, 삭제를 O(log n) 시간에 끝냅니다.

Q2. AVL 트리와 무엇이 다른가요?

둘 다 균형 이진 탐색 트리입니다. AVL 트리는 모든 노드에서 왼쪽과 오른쪽 서브트리의 높이 차이를 1 이하로 엄격하게 유지합니다. 그래서 높이가 더 낮고 탐색이 조금 빠릅니다. 레드-블랙 트리는 색 규칙으로 균형을 더 느슨하게 유지합니다. 그래서 삽입과 삭제 때 회전이 적습니다. C++ 표준 라이브러리의 주요 구현은 map과 set에 레드-블랙 트리를 씁니다.

Q3. 삽입할 때 새 노드를 왜 빨강으로 넣나요?

검정으로 넣으면 새 노드를 지나는 경로만 검정 수가 하나 늘어납니다. 그러면 5번 규칙이 바로 깨집니다. 빨강으로 넣으면 경로별 검정 수는 그대로입니다. 부모가 빨강인 경우에만 4번 규칙을 고치면 됩니다.

수정 안내

이 글은 2026년 11월 21일에 다시 썼습니다. 이전 판에서 자식이 둘인 노드를 지울 때 "값과 색을 맞바꾼다"고 적은 것을 "값만 복사하고 색은 그대로 둔다"로 고쳤습니다. C++의 map, set이 레드-블랙 트리라는 설명은 표준이 정한 것이 아니라 주요 구현의 방식이므로 그렇게 고쳐 적었습니다. 삽입 조정의 마지막에 루트를 검정으로 칠하는 단계와, 삭제 조정에서 색을 바꾸는 단계를 보충했습니다.

참고 자료

같은 주제의 다른 글: [알고리즘] 최소 스패닝 트리(MST) 개념과 구현: 크루스칼 vs 프림 비교, [데이터베이스] DB 인덱스(Index) 핵심 원리: B-Tree 구조와 검색 성능 최적화, [알고리즘] 퀵 정렬(Quick Sort) 동작 원리와 시간 복잡도 분석: 피벗 선택과 분할 정복

728x90
728x90