---
title: "레드 블랙 트리: 색 규칙으로 긴 탐색 경로를 막는 구조"
author: "Lee"
published_at: "2026-10-11T17:55:02.825Z"
updated_at: "2026-09-30T09:28:28.568Z"
tags: ["컴퓨터공학","자료구조"]
canonical_url: "https://ariser.io/@writer_a1cd615ab19e/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99-%ED%8A%B8%EB%A6%AC-%EC%83%89-%EA%B7%9C%EC%B9%99%EC%9C%BC%EB%A1%9C-%EA%B8%B4-%ED%83%90%EC%83%89-%EA%B2%BD%EB%A1%9C%EB%A5%BC-%EB%A7%89%EB%8A%94-%EA%B5%AC%EC%A1%B0"
ai_assisted: false
---

# 레드 블랙 트리: 색 규칙으로 긴 탐색 경로를 막는 구조

[원문](https://ariser.io/@writer_a1cd615ab19e/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99-%ED%8A%B8%EB%A6%AC-%EC%83%89-%EA%B7%9C%EC%B9%99%EC%9C%BC%EB%A1%9C-%EA%B8%B4-%ED%83%90%EC%83%89-%EA%B2%BD%EB%A1%9C%EB%A5%BC-%EB%A7%89%EB%8A%94-%EA%B5%AC%EC%A1%B0)

레드 블랙 트리는 노드에 빨강과 검정 색을 붙여 균형을 유지하는 이진 탐색 트리다. 정확한 높이를 완전히 같게 만들기보다, 몇 가지 색 규칙으로 한쪽 경로가 지나치게 길어지는 것을 막는다. 색은 저장 값의 의미와 별개인 구조 관리 정보다.

![검은 루트 10과 붉은 자식 5·15 및 검은 NIL 잎으로 구성된 레드 블랙 트리](/api/v1/media/8c6a9c79-3248-4df1-a4de-c708837962d9)

*붉은 노드가 연속되지 않고 각 경로의 검은 노드 수가 같도록 규칙을 유지한다.*

### 검정 높이가 만드는 균형

전형적인 규칙에서는 루트가 검정이고, 비어 있는 자식 위치를 검정 NIL로 취급한다. 빨강 노드는 빨강 자식을 가질 수 없고, 한 노드에서 아래 NIL까지 가는 모든 경로의 검정 노드 수가 같다. 이 수를 검정 높이라고 한다.

빨강 노드가 연속할 수 없으므로 가장 긴 경로도 같은 검정 높이의 가장 짧은 경로보다 두 배를 넘게 길어지지 않는다. 그 결과 n개 내부 노드의 높이는 O(log n), 더 구체적으로 대략 2log₂(n+1) 이하로 제한된다. 단순히 빨강과 검정을 반씩 칠하는 규칙은 아니다.

### 삽입 뒤 충돌을 고치는 흐름

새 노드는 보통 빨강으로 넣는다. 그러면 경로의 검정 수를 바로 바꾸지 않지만 부모가 빨강이면 연속 빨강 위반이 생긴다. 부모의 형제인 삼촌의 색을 확인하면 복구 방향을 정할 수 있다.

다음은 부모가 조부모의 왼쪽 자식인 경우 중 삼촌도 빨강인 처리만 나타낸다. 전체 구현에는 검정 삼촌의 회전 처리와 대칭 경우도 필요하다.

```python
if parent.color == RED and uncle.color == RED:
    parent.color = BLACK
    uncle.color = BLACK
    grandparent.color = RED
    current_node = grandparent
# Continue checking ancestors after recoloring.
# Finish the insertion repair by making the root black.
```

부모와 삼촌을 검정으로, 조부모를 빨강으로 바꾸면 아래 경로들의 검정 수를 맞추면서 위로 문제를 옮긴다. 삼촌이 검정이면 노드의 꺾인 방향을 정리하는 회전과 색 변경으로 국소 구조를 고친다. 회전만 하거나 색만 바꾸는 것으로 모든 경우가 해결되지는 않는다.

삭제는 검정 노드 제거 시 어떤 경로의 검정 수가 줄어 더 복잡하다. 형제 색과 형제 자식 색에 따라 재색칠이나 회전을 수행한다. NIL도 분석에 포함해야 빈 자식에서 생기는 부족을 정확히 다룰 수 있다.

검색·삽입·삭제의 최악 시간은 O(log n)이다. 노드에는 색 비트와 연결 정보가 필요하다. 높이 균형을 엄격하게 관리하는 AVL과는 복구 방식과 실제 검색 경로가 다르며, 어떤 구조가 빠른지는 연산 비율과 구현에 따라 달라진다.

색 규칙은 디버깅 가능한 불변식이기도 하다. 각 노드의 순서 범위, 연속 빨강 부재, 경로별 검정 높이를 검사하면 눈으로는 놓치기 쉬운 잘못된 변경을 발견할 수 있다. 빨강 개수가 많고 적음만으로 올바른 트리를 판단할 수는 없다.

빨강·검정은 디버깅 표시가 아니라 검색 높이를 제한하는 계약이다. 새 기능을 추가할 때 순서 조건만 검사하면 색 불변식 위반이 누적되어 최악 성능 보장을 잃을 수 있다.

### 참고 자료

- [MIT OpenCourseWare · Introduction to Algorithms](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/)
- [Princeton · Algorithms, 4th edition · Balanced Search Trees](https://algs4.cs.princeton.edu/33balanced/)