[자료구조] 레드 블랙 트리(Red-Black Tree) 정리 (1) - 삽입

∙2026년 4월 25일

레드-블랙 트리(Red-Black Tree) 공부하기

전에 게임 프로그래밍 면접에서 레드-블랙 트리에 대한 질문을 받았는데 답변을 못해서 매우 당황했던 기억이...
학교 다니면서 AVL트리에 대해서만 공부했기 때문에 레드-블랙 트리 질문이 나올줄은 상상도 못했음..
그렇게 레드-블랙 트리에 대해 정리를 시작하게 됐습니다

아래 포스트를 참고하여 작성했습니다.
https://code-lab1.tistory.com/62

레드-블랙 트리를 공부해야하는 이유

C#에서 SortedDictionary<K, V>와 SortedSet 가 내부적으로 레드-블랙 트리로 구현되어 있다.

우선 레드-블랙 트리는 자가 균형 이진 탐색 트리이다. 이진 트리가 스스로 균형을 맞춘다는 말인데 이게 왜 필요한지 알아보자

일반 이진 탐색 트리(BST)의 단점은 데이터가 정렬된 순서로 들어오면 다음과 같이 한쪽으로 쭉 늘어진 이진 편향 트리가 된다.

이렇게 되면 탐색 시간이 **O(n)**으로 떨어져 연결리스트와 다를 바가 없어진다. 이 문제를 해결하기 위해 자기 균형 이진 탐색 트리가 등장했다. 레드-블랙 트리는 그 중 가장 널리 사용되는 구조로, 어떤 순서로 데이터를 삽입하더라도 트리의 높이를 **O(log n)**으로 유지한다.

레드-블랙 트리의 5가지 규칙

레드-블랙 트리는 이진 탐색 트리에 다음과 같은 5가지 규칙을 추가한다
이 규칙들이 모두 만족될 때 트리는 "유효한 레드-블랙 트리"가 된다

모든 노드는 빨간색 혹은 검은색이다.
루트 노드는 검은색이다
모든 리프 노드는 검정색이다 (NIL : null leaf, 자료를 갖지 않고 트리의 끝을 나타냄)
빨간색 노드의 자식은 검은색이다 = No Double Red(빨간색 노드가 연속으로 나올 수 없다)
모든 리프 노드에서 Black Depth는 같다 = 리프 노드에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다

레드-블랙 트리 삽입 과정

레드 - 블랙 트리에 새로운 노드를 삽입할 때 새로운 노드는 항상 빨간색으로 삽입한다
위의 예시에서는 3을 넣었을 때 Double Red가 발생한다

레드-블랙 트리는 Double Red 문제를 해결하기 위해 2가지 전략을 사용한다

N : 새로 삽입할 노드
P : 부모 노드
U 삼촌 노드(부모 노드의 형제)
G : 조부모 노드

Double Red가 발생했을 때

삼촌 노드가 검은색 : Restructuring
삼촌 노드가 빨간색 : Recoloring

Restructuring

Resturcturing의 과정

새로운 노드(N), 부모 노드(P), 조상 노드(G)를 오름차순으로 정렬한다
셋 중 중간값을 부모로 만들고 나머지 둘을 자식으로 만든다
새로 부모가 된 노드를 검은색으로 만들고 나머지 자식들을 빨간색으로 만든다

1단계 - 3(N)을 넣었을 때 Double Red가 발생한다
이때 7(U)가 검은색이라 Restructuring을 수행한다

2단계 - 먼저 3(N), 2(P), 5(G)를 오름차순으로 정렬한다 -> 3이 중간값이 된다
중간값인 3을 부모 노드로 바꾸고 나머지 2(P)와 5(G)를 자식 노드로 바꾼다 (이때 회전으로 진행)
이때 5(G)의 오른쪽 자식 노드였던 7(U)는 그대로 5(G)의 오른쪽 자식 노드가 된다

3단계 - 새롭게 부모가 된 3을 검은색으로 바꿔주고 나머지 두 자식의 2, 5의 색을 빨간색으로 바꿔준다
여기서 2는 규칙 3을 만족하지 않는것처럼 보이지만 빨간색이 리프노드처럼 보일때는 NIL을 2개 가지고 있다고 생각하면 된다

Recoloring

Recoloring의 과정

새로운 노드(N)의 부모(P)와 삼촌(U)을 검은색으로 바꾸고 조상(G)을 빨간색으로 바꾼다
조상(G)이 루트 노드라면 검은색으로 바꾼다
조상(G)을 빨간색으로 바꿨을 때 또 다시 Double Red가 발생하면 또 다시 Restructuring 혹은 Recoloring을 진행해서 Double Red 문제가 발생하지 않을 때까지 반복한다