Red-Black Tree(Red-Black 트리)는 이진 탐색 트리(BST)의 한 종류로, 삽입/삭제 이후에도 트리의 높이가 한쪽으로 치우치지 않도록 “색(Color) 규칙 + 회전(Rotation)”으로 균형을 유지하는 자기 균형(Self-Balancing) 트리입니다.
일반적인 BST는 입력 순서가 오름차순/내림차순처럼 특정 패턴을 가지면 트리가 한쪽으로 늘어져 탐색/삽입/삭제가 O(N)까지 악화될 수 있습니다. 반면 Red-Black 트리는 규칙 위반을 감지하면 회전과 색 변경으로 구조를 조정하여, 평균이 아니라 “최악에서도” O(log N) 범위를 유지하는 것이 목적입니다.
한쪽으로 치우친 BST (높이 ≈ n)
1
\
2
\
3
\
4
\
5
\
6
균형에 가까운 트리 (높이 ≈ log n)
4
/ \
2 6
/ \ /
1 3 5
이번 글에서는 Red-Black Tree의 개념과 동작 원리를 정리하고, C#으로 Red-Black Tree를 직접 구현한 뒤, Unity 테스트 코드로 균형 유지 동작을 확인해 보겠습니다.
트리(Tree)는 사이클이 없는 연결 그래프로 볼 수 있으며, 이진 트리는 각 노드가 최대 2개의 자식(Left/Right)을 갖습니다. BST는 여기에 “왼쪽은 작고 오른쪽은 크다”라는 정렬 규칙을 더한 구조입니다. Red-Black Tree는 BST에 “색 규칙”을 추가하여 높이 증가를 제한하고, 회전으로 균형을 복구합니다.
1. Red-Black Tree의 구조와 동작 방식
Red-Black Tree는 “정렬된 트리(BST)”라는 장점은 유지하면서, “입력 순서가 나쁘면 트리가 망가진다”는 단점을 색 규칙과 회전으로 해결하는 자료구조입니다. 핵심은 “높이를 완벽히 최소화”하는 것이 아니라, “최악의 경우에도 높이가 O(log N)을 넘지 않도록 상한을 강제”하는 데 있습니다.
기본 용어 정의는 다음과 같습니다.
- Node: 트리를 구성하는 단위이며 Key(값), Left/Right(자식), Parent(부모), Color(색)를 가집니다.
- Root: 트리의 최상단 노드입니다.
- Parent / Child: 부모-자식 관계를 갖는 인접 노드입니다.
- Leaf: 자식이 없는 노드입니다(Left/Right가 모두 null).
- NIL Leaf(RB 규칙에서의 leaf): Red-Black Tree 규칙에서의 Leaf는 실제 노드가 아니라, 자식이 없는 위치(null)를 개념적인 Black 노드(NIL) 로 취급한 것입니다. 이를 통해 모든 경로의 Black-height를 일관되게 계산할 수 있습니다.
- Sibling(형제 노드): 같은 부모를 가진 노드입니다.
- Depth: Root에서 특정 노드까지의 거리(간선 수 기준)입니다.
- Height: 특정 노드에서 가장 깊은 Leaf까지의 최대 거리(간선 수 기준 또는 노드 수 기준 중 하나)입니다. Red-Black Tree는 직접 Height를 저장하지 않고도 색 규칙으로 높이를 제한합니다.
※ 트리에 대한 기본적인 내용은 Unity 개발자를 위한 C# Tree(트리) 구현을 참고하세요.
Red-Black Tree는 다음 규칙을 만족합니다(표현은 구현마다 다를 수 있으나 의미는 동일합니다).
- 각 노드는 Red 또는 Black입니다.
- Root는 Black입니다.
- 모든 Leaf(null, NIL 노드)는 Black으로 취급합니다.
- Red 노드는 Red 자식을 가질 수 없습니다(연속 Red 금지).
- 어떤 노드에서든, 그 노드에서 아래로 내려가는 모든 경로는 “같은 개수의 Black 노드(Black-height)”를 가집니다.
아래 예시 트리를 보면서 각 규칙이 어떤 식으로 적용되는지 확인해 보겠습니다.
예시 트리(노드 옆 괄호는 색상: B=Black, R=Red)
10(B)
/ \
5(R) 15(R)
/ \ / \
2(B) 7(B) 12(B) 20(B)
√ 각 노드는 Red 또는 Black입니다.
- 예시에서 10(B), 2(B)처럼 Black인 노드가 있고, 5(R), 15(R)처럼 Red인 노드가 있습니다. 즉, 색은 두 가지로만 표현됩니다.
√ Root는 Black입니다.
- 루트는 트리의 최상단 노드이며, 예시에서는 10이 Root입니다. 10이 Black이므로 이 규칙을 만족합니다
√ 모든 Leaf(null, NIL 노드)는 Black으로 취급합니다.
- 여기서 “Leaf”라는 말이 두 가지로 혼동되기 쉬운데, Red-Black Tree 규칙에서 말하는 Leaf는 보통 “실제 데이터 노드”가 아니라, 각 자식 포인터가 가리키는 null(=NIL, Sentinel)을 의미합니다.
- 예를 들어 2(B)는 실제 자식 노드가 없으므로, 내부적으로는 다음처럼 Left/Right가 모두 null입니다. 이 null들을 NIL(Black)로 취급하면, 규칙 검증과 Black-height 계산이 깔끔해집니다.
2(B)
/ \
NIL(B) NIL(B)
√ Red 노드는 Red 자식을 가질 수 없습니다(연속 Red 금지).
- 예시에서 Red 노드는 5(R), 15(R)입니다. 이들의 자식은 각각 2(B), 7(B), 12(B), 20(B)로 모두 Black입니다.
- 즉, “빨간 노드 아래에 빨간 노드가 연속으로 붙는 상황”을 금지합니다. 이 규칙 하나만으로도 트리가 한쪽으로 무한히 늘어지는 것을 크게 제한할 수 있습니다.
√ 어떤 노드에서든, 그 노드에서 아래로 내려가는 모든 경로는 같은 개수의 Black 노드(Black-height)를 가집니다.
- Black-height는 “해당 노드에서 시작해 NIL까지 내려가는 경로에서 만나는 Black 노드의 개수”입니다. 이때 자식이 없는 위치는 NIL(Black)로 취급합니다.
- 이 글에서는 Black-height를 (시작 노드 포함) + (NIL 포함) 기준으로 셉니다.
- 예시에서 Root(10)에서 각 Leaf 방향으로 내려가는 경로를 세어보면 다음과 같습니다.
경로 A: 10(B) → 5(R) → 2(B) → NIL(B)
- Black 개수 : 3
경로 B: 10(B) → 5(R) → 7(B) → NIL(B)
- Black 개수 : 3
경로 C: 10(B) → 15(R) → 12(B) → NIL(B)
- Black 개수 : 3
경로 D: 10(B) → 15(R) → 20(B) → NIL(B)
- Black 개수 : 3
모든 경로의 Black 개수가 동일하게 3으로 맞아떨어집니다. 이 “Black-height 동일” 조건 때문에 Red-Black Tree는 어느 한쪽 경로만 과도하게 길어지는 상황을 방지할 수 있는 것입니다.
Red-Black Tree 구현에서는 Black-height를 실제로 계산하거나 저장하지 않습니다. 대신, Black-height 규칙이 깨질 수 있는 상황을 알고리즘적으로 제한하고, 삽입/삭제 시 국소적인 색 변경과 회전을 통해 결과적으로 모든 경로의 Black-height가 같도록 유지합니다.
Black-height 규칙은 “루트에서만 세는 규칙”이 아닙니다. “어떤 노드에서든” 그 노드에서 아래로 내려가는 모든 경로(해당 노드 → NIL까지)의 Black 노드 개수가 같아야 합니다. 이 규칙은 트리가 정이진트리여야 한다는 뜻이 아니며, 한쪽 자식이 없는 경우는 그 자리에 NIL(Black)이 있다고 보고 계산합니다.
※ 정이진 트리(Full Binary Tree)는 모든 노드의 자식 수가 0개(리프) 또는 2개(내부 노드)인 이진 트리입니다.
예시 트리(비대칭 구조, 정이진트리가 아님).
10(B)
/ \
5(R) 15(B)
/ /
2(B) 12(R)
이 트리는 “모든 노드가 자식 2개를 가진 형태”가 아닙니다. 예를 들어 5(R)도 오른쪽 자식이 없고, 15(B)도 오른쪽 자식이 없습니다. 그럼에도 Red-Black Tree 규칙에서는 “없는 자식 포인터”를 NIL(Black)로 취급하기 때문에, Black-height를 일관되게 셀 수 있습니다.
예를 들어, 노드 5(R)를 기준으로 아래 경로들의 Black 개수를 비교해 보겠습니다.
경로 1: 5(R) → 2(B) → NIL(B)
- Black 개수 : 2
경로 2: 5(R) → NIL(B)
- Black 개수 : 1
위처럼 “5(R) 기준”으로 보면 Black 개수가 다르므로, 이 상태는 Black-height 규칙을 만족하지 못합니다. 즉, “어떤 노드에서든”을 강조하면 루트에서만 세는 오해가 줄고, 실제로 규칙이 더 강한 제약임이 드러납니다.
그렇다면 “정이진트리가 아닌데도 Black-height가 성립하는” 예시는 어떻게 생겼을까요. 아래처럼 한쪽이 비어 있는 곳을 NIL(Black)로 보았을 때, 각 경로의 Black 개수가 맞아떨어지면 됩니다.
10(B)
/ \
5(B) 15(B)
/
2(R)
이제 노드 10(B)를 기준으로 경로를 비교하면, 왼쪽 경로: 10(B) → 5(B) → 2(R) → NIL(B), 오른쪽 경로: 10(B) → 15(B) → NIL(B) 처럼 내려가며 Black 노드 개수가 동일하게 맞춰질 수 있습니다. 중요한 점은 “모양이 완전히 대칭일 필요는 없고”, NIL을 포함해 계산했을 때 각 경로의 Black 개수가 같으면 된다는 것입니다.
Red-Black Tree의 여러 규칙들은 각각 독립적인 제약처럼 보이지만, 실제로는 모두 “모든 경로의 Black-height를 같게 유지한다”는 하나의 목표를 달성하기 위한 장치들입니다.
이러한 규칙들로 인해, Red-Black Tree의 높이는 O(log N)으로 제한됩니다. AVL 트리는 더 “강하게” 균형을 잡아 탐색 성능이 조금 더 좋은 경향이 있지만, Red-Black Tree는 삽입/삭제 시 회전 빈도가 상대적으로 낮아 갱신이 잦은 환경에서 유리한 선택이 되기도 합니다. 실제로 표준 라이브러리의 정렬 기반 컨테이너(예: 일부 언어의 TreeMap/TreeSet)는 Red-Black Tree 계열 구현이 흔합니다.
1.1 Red-Black Tree의 삽입과 삭제 알고리즘 개요
Red-Black Tree의 삽입과 삭제는 모두 BST 규칙으로 구조를 먼저 만든 뒤, 색 규칙이 깨졌는지를 검사하고 복구하는 방식으로 동작합니다. 다만 삽입은 문제의 형태가 단순하여 두 가지 패턴으로 정리할 수 있는 반면, 삭제는 Black-height 감소 문제를 다뤄야 하므로 네 가지 복구 케이스로 나뉩니다.
아래에서 설명하는 트리 상태 중 일부는 정상적인 Red-Black Tree가 아닌 중간 상태입니다. Red-Black Tree는 이러한 중간 상태를 허용한 뒤, 알고리즘적으로 다시 규칙을 만족하는 상태로 복구합니다.
1.2 삽입 시 동작
Red-Black Tree의 삽입은 항상 다음 순서로 진행됩니다.
- BST 규칙(왼쪽 < 부모 < 오른쪽)에 따라 Leaf 위치에 새 노드를 추가합니다.
- 새 노드는 항상 Red로 삽입됩니다.
- 삽입으로 인해 “연속 Red(부모가 Red)”가 생기면 FixInsert로 색 변경/회전을 수행합니다.
아래 예제들은 “삽입 직후(규칙 위반 가능)” 상태에서 시작하여, FixInsert가 적용된 “복구 이후” 상태까지 함께 보여줍니다.
Case 1) 부모(P)가 Red이고, 삼촌(U)도 Red인 경우 (색 뒤집기)
(1) 삽입 직후 상태: 새 노드 N이 Red로 삽입되었고, 부모 P도 Red라서 “연속 Red” 위반이 발생합니다.
10(B) = G
/ \
5(R)=U 15(R)=P
/
12(R)=N
(2) 복구 방법: 부모(P)와 삼촌(U)을 Black으로, 조부모(G)를 Red로 변경합니다. 이 처리는 Black-height를 유지하면서 “Red를 위로 밀어 올리는” 방식입니다.
- P(15): Red → Black
- U(5): Red → Black
- G(10): Black → Red
(3) 복구 이후 상태: 색 뒤집기의 결과로 조부모(G)는 Red로 변경됩니다. 이는 Red를 위로 전파하기 위한 정상적인 처리입니다. 다만 조부모가 Root인 경우, Red-Black Tree 규칙에 따라 Root는 항상 Black이어야 하므로, 최종 단계에서 Root의 색을 다시 Black으로 되돌립니다.
10(R) -> Root인 경우는 (B)
/ \
5(B) 15(B)
/
12(R)
Case 2) 부모(P)가 Red이고, 삼촌(U)은 Black인 경우 (회전 + 색 교환)
이 경우는 “색 뒤집기”만으로는 연속 Red를 해소할 수 없어, 회전으로 구조를 바꿔야 합니다. 회전 형태는 LL/LR/RL/RR로 나뉘지만, 핵심은 “회전 후 부모/조부모의 색을 교환하여 연속 Red를 끊는다”는 점입니다.
예시: LL 형태 (Right Rotation)
(1) 삽입 직후 상태: N이 삽입되면서 P와 N이 연속 Red가 되었습니다. 삼촌(U)은 NIL(Black)로 취급됩니다.
30(B)=G
/ \
20(R)=P NIL(B)=U
/
10(R)=N
(2) 복구 방법: 조부모(G)를 기준으로 Right Rotation을 수행하고, 회전 후 새 서브트리 루트가 될 P를 Black으로, G를 Red로 만듭니다.
- RotateRight(G=30)
- P(20): Red → Black
- G(30): Black → Red
(3) 복구 이후 상태: 연속 Red가 제거되고, Black-height도 유지됩니다.
20(B)
/ \
10(R) 30(R)
예시: LR 형태 (Left-Right Rotation)
(1) 삽입 직후 상태: N이 삽입되면서 부모(P)와 새 노드(N)가 연속 Red가 되었습니다. 삼촌(U)은 NIL(Black)로 취급됩니다.
30(B)=G
/
20(R)=P
\
25(R)=N
이 구조는 “왼쪽-오른쪽(LR)” 형태의 중간 상태입니다. 현재 상태에서는 한 번의 회전만으로는 연속 Red 위반을 제거할 수 없으므로, 두 단계 회전을 수행합니다.
(2-1) 1단계: 부모(P)를 기준으로 Left Rotation 수행
먼저 부모(P=20)를 기준으로 Left Rotation을 수행합니다. 이 회전의 목적은 구조를 LL 형태로 변환하는 것입니다. 이 단계에서는 색 변경은 아직 수행하지 않습니다.
30(B)=G
/
25(R)=N
/
20(R)=P
Left Rotation 이후, 새로 삽입된 노드 N(25)이 부모 위치로 올라가고, 기존 부모 P(20)는 그 왼쪽 자식이 됩니다. 이제 구조는 LL 형태가 되었습니다.
(2-2) 2단계: 조부모(G)를 기준으로 Right Rotation 수행 + 색 재배치
이제 조부모(G=30)를 기준으로 Right Rotation을 수행합니다. 회전 이후에는 색을 재배치하여 Red-Red 위반을 제거합니다.
- RotateRight(G=30)
- N(25): Red → Black (새 서브트리 루트)
- G(30): Black → Red
(3) 복구 이후 상태: 연속 Red 위반이 제거되었고, Black-height도 유지됩니다.
25(B)
/ \
20(R) 30(R)
이처럼 LR 형태는 첫 번째 회전으로 구조를 LL 형태로 정렬한 뒤, 두 번째 회전과 색 교환으로 Red-Red 위반을 제거하는 방식으로 처리됩니다. 두 번의 회전은 각각 역할이 다르며, 순서를 바꾸면 올바른 복구가 이루어지지 않습니다.
RL과 RR 형태는 위에서 설명한 LR과 LL 형태의 좌우가 뒤바뀐 경우입니다. 알고리즘의 핵심 로직은 완전히 동일하며, 적용되는 회전 방향만 반대가 됩니다.
- RR 형태: LL 형태의 좌우 반전 → Left Rotation + 색 교환
- RL 형태: LR 형태의 좌우 반전 → Right Rotation 후 Left Rotation
즉, 삽입 알고리즘은 “부모가 Red이고 삼촌이 Black일 때, 회전을 통해 Red-Red 관계를 끊는다”는 하나의 원칙을 가지며, LL / LR / RL / RR은 모두 이 원칙을 좌우 방향에 따라 적용한 결과입니다.
1.3 삭제 시 동작
Red-Black Tree의 삭제는 먼저 BST 규칙에 따라 노드를 제거한 뒤, 그 결과로 Red-Black 규칙이 깨졌는지를 검사하고 FixDelete로 복구하는 방식으로 동작합니다. 삭제 복구는 형제(w)의 색과 형제 자식들의 색 조합에 따라 4가지 케이스로 분류됩니다.
삭제 알고리즘이 특히 헷갈리는 이유는, 삽입과 달리 모든 케이스가 문제를 즉시 해결하지 않기 때문입니다. Red-Black Tree의 삭제는 한 번의 연산으로 끝나는 구조가 아니라, 문제를 표현하는 중간 상태를 만들고, 이를 위로 전파하거나 변환하면서 해결하는 방식을 사용합니다.
Double Black(이중 흑색) 개념
Red-Black Tree는 어떤 노드에서 시작하든, 그 노드에서 아래로 내려가는 모든 경로의 Black 노드 개수(Black-height)가 같아야 합니다. 그런데 Black 노드를 삭제하면, 해당 경로에서 Black 노드가 하나 줄어들어 Black-height 불일치가 발생할 수 있습니다. 이 상태를 그대로 두면 Red-Black Tree 규칙을 만족할 수 없기 때문에, 삭제 알고리즘은 이 문제를 명시적으로 표현하는 개념적 상태를 도입합니다. 이때 사용되는 개념이 Double Black입니다.
Double Black은 “Black이 하나 더 많다”는 뜻이 아니라, “Black이 하나 부족한 상태”를 논리적으로 표현하기 위한 개념적 표식입니다. 즉, 삭제된 위치(또는 그 자리를 대체한 노드)를 “Black 노드 하나가 더 필요하다”는 상태로 간주하고, 이를 Double Black 상태라고 부릅니다.
Double Black은 실제 색이 아니다
중요한 점은 Double Black이 실제 노드에 두 개의 Black 색이 칠해진 상태가 아니라는 것입니다. Red-Black Tree 구현에서는 Double Black이라는 색을 따로 두지 않으며, 노드에 실제로 “이중 색상”을 저장하지도 않습니다. Double Black은 오직 “Black-height가 하나 부족한 위치가 어디인지”를 설명하기 위한 추상적인 개념입니다. 구현에서는 이 상태를 현재 노드(x)와 그 부모(px)를 기준으로 추적하며, FixDelete 과정에서 형제(w)의 색과 구조를 이용해 점진적으로 해소합니다.
삭제 복구 알고리즘의 목표
삭제 복구 알고리즘의 목표는 단 하나입니다.
- Double Black 상태를 제거하여, 모든 경로의 Black-height를 다시 동일하게 만드는 것
이를 위해 삭제 복구는 다음과 같은 역할을 수행하는 케이스들로 구성됩니다.
- Double Black을 즉시 제거하는 케이스
- Double Black을 부모 방향으로 전파하는 케이스
- 해결 가능한 형태로 구조를 변환하는 케이스
이러한 역할 분담에 따라, 삭제 복구는 형제(w)와 그 자식의 색 조합에 따라 Case 1 ~ Case 4로 나뉘게 됩니다.
중간 상태를 허용하는 이유
삭제 과정에서 등장하는 일부 트리 상태는 정상적인 Red-Black Tree가 아닙니다. 하지만 이는 오류가 아니라, Double Black을 처리하기 위해 의도적으로 허용되는 중간 상태입니다. Red-Black Tree 삭제 알고리즘은 “항상 규칙을 만족하는 상태만 유지하는 방식”이 아니라, 일시적으로 규칙을 깨뜨린 뒤, 알고리즘적으로 복구하는 방식을 사용합니다.
이제부터 살펴볼 삭제 케이스 1~4는 Double Black 상태가 어떻게 이동하고, 변형되며, 최종적으로 제거되는지를 단계적으로 보여주는 과정입니다. 이 케이스들은 각각이 독립적인 해결책이 아니라, 하나의 문제(Double Black)를 처리하기 위해 서로 이어지는 흐름으로 이해하는 것이 중요합니다. 어떤 케이스는 문제를 바로 해결하지 않고 다음 단계로 넘기거나, 해결 가능한 형태로 변환하는 역할만 수행합니다.
Case 1) 형제(w)가 Red인 경우
- 이 케이스는 Double Black을 직접 해결하지 않습니다. 형제(w)가 Red이면 먼저 회전과 색 변경을 통해 형제를 Black으로 만드는 구조로 변환합니다.
- 이 단계의 목적은 이후 케이스(Case 2~4)를 적용할 수 있는 형태를 만드는 것이며, 처리 이후에도 Double Black은 그대로 유지되고 알고리즘은 계속 진행됩니다.
Case 2) 형제(w)가 Black이고, 형제의 자식이 모두 Black인 경우
- 이 케이스는 문제를 부모 방향으로 전파하는 단계입니다.
- 형제(w)를 Red로 바꾸어 현재 서브트리 기준의 Black-height는 맞추지만, 전체 경로의 Black-height 불일치는 해소되지 않습니다. 따라서 Double Black을 부모로 올려, 상위 노드에서 동일한 복구 과정을 반복합니다.
Case 3) 형제(w)가 Black이고, 가까운 자식이 Red인 경우
- 이 케이스는 바로 종료할 수 없는 중간 단계입니다.
- 한 번의 회전과 색 조정을 통해 “형제의 먼 자식이 Red인 형태”로 구조를 변환하며, 이후 Case 4를 적용할 수 있는 상태를 만드는 역할을 합니다.
Case 4) 형제(w)가 Black이고, 먼 자식이 Red인 경우
- 이 케이스는 삭제 복구 케이스들 중에서 ‘회전과 색 재배치’로 Double Black을 즉시 제거하고 종료되는 유일한 케이스입니다.
- 회전과 색 재배치를 통해 Black-height가 복구되고, Double Black이 제거되며 알고리즘이 종료됩니다.
다시 말해, Red-Black Tree 삭제는 네 가지 케이스 중 하나를 선택해 바로 해결하는 방식이 아니라, Double Black 상태를 위로 전파하거나 형태를 바꾸며 진행하다가, Case 4에서 비로소 문제를 종료하는 과정입니다.
아래 예제들은 “삭제 직후(규칙 위반 가능)” 상태에서 시작하여, FixDelete가 적용된 “복구 이후” 상태까지 함께 보여줍니다.
Case 1) 형제(w)가 Red인 경우 (회전으로 형태 변환 후 진행)
(1) 삭제 직후 상태: [DB]는 삭제된 위치(NIL)에 남아 있는 상태 표식이며, Black-height가 하나 부족한 상태를 의미합니다. 형제(w)가 Red인 경우, 이 상태는 바로 해결하지 않고, 먼저 회전을 통해 구조를 변환하여 이후 케이스(2~4)를 적용할 수 있는 형태로 만듭니다.
10(B)=P
/ \
[DB] 20(R)=w
/ \
15(B) 25(B)
(2) 복구 방법: 부모(P)를 기준으로 Left Rotation을 수행한 뒤, 색을 조정합니다. 이 단계의 목적은 Red인 형제(w)를 Black으로 만들어, 삭제 복구를 진행할 수 있는 구조로 변환하는 것입니다.
- RotateLeft(P = 10)
- w(20): Red → Black
- P(10): Black → Red
(3) 복구 이후 상태: 이 단계에서 [DB]는 제거되지 않았으며, 단지 구조만 변환되었습니다. 이제 [DB]의 새로운 형제를 기준으로 다시 색 상태를 검사하고, 케이스 2~4 중 하나로 삭제 복구가 이어집니다.
20(B)
/ \
10(R) 25(B)
/ \
[DB] 15(B)
Case 2) 형제(w)가 Black이고, 형제(w)의 자식도 모두 Black (전파)
(1) 삭제 직후 상태: 형제(w)가 Black이고, 형제의 자식도 모두 Black인 경우에는 회전으로 즉시 [DB]를 제거할 수 없습니다.
10(B)=P
/ \
[DB] 20(B)=w
/ \
NIL(B) NIL(B)
(2) 복구 방법: 형제(w)를 Red로 바꿔 w 쪽 경로의 Black을 1 줄여 현재 서브트리에서의 불균형을 정리하고, [DB]를 부모(P)로 전파합니다.
- w(20): Black → Red
- [DB] ← P(10) (상태 전파)
(3) 복구 이후 상태(전파 1회 결과): 이 단계는 삭제 복구의 종료가 아니라, [DB] 상태가 부모 노드로 이동한 상태입니다. 실제 트리 구조가 자기 자신을 참조하는 것은 아니며, 문제의 위치만 상위로 이동했음을 의미합니다.
10(B)=P ← 새 [DB]
/ \
NIL 20(R)
DB가 부모(P)로 전파된 이후에는, 부모 P의 색에 따라 이후 흐름이 달라집니다. 위 예시는 P(10)이 Black인 경우입니다.
- P(10)가 Black인 경우: Black 부족 상태([DB])가 계속 남아 있으므로, 삭제 복구 루프가 이어집니다. 이때 [DB]는 더 상위로 전파되거나, 구조에 따라 Case 3 → Case 4로 진행될 수 있습니다.
- P(10)가 Red인 경우: P를 Black으로 바꾸는 것만으로 현재 경로의 Black-height가 맞춰지므로 추가 회전 없이 Double Black이 제거되고 삭제 복구가 종료됩니다. 이는 Case 4에 의한 종료가 아니라, Case 2에서 부모로 전파된 Double Black이 Red 부모에서 흡수되는 종료 조건입니다. 구현 관점에서는, Case 2 이후 Double Black이 부모(P)로 이동하면 다음 반복에서 루프 조건이 더 이상 성립하지 않아 복구 루프가 종료되며, 마지막 단계에서 P를 Black으로 변경함으로써 Black-height 불일치가 해소됩니다.
Case 3) 형제(w)가 Black이고, 형제(w)의 가까운 자식이 Red (케이스 4로 변환)
(1) 삭제 직후 상태: 형제(w)는 Black이고, [DB]와 가까운 쪽 자식(c)이 Red인 경우입니다. 이 형태는 바로 종결할 수 없으므로, 케이스 4 형태로 변환합니다.
10(B)=P
/ \
[DB] 20(B)=w
/
15(R)=c
(2) 복구 방법: 형제(w)를 기준으로 Right Rotation을 수행하고, 색을 조정하여 케이스 4 형태를 만듭니다.
- RotateRight(w = 20)
- c(15): Red → Black
- w(20): Black → Red
(3) 복구 이후 상태: 이제 형제(w)의 먼 자식이 Red인 케이스 4 형태가 됩니다.
10(B)=P
/ \
[DB] 15(B)
\
20(R)
Case 4) 형제(w)가 Black이고, 형제(w)의 먼 자식이 Red (종결)
(1) 케이스 4 시작 상태: 형제(w)는 Black이고, 먼 자식(f)이 Red인 경우입니다. 이 경우는 회전과 색 재배치로 즉시 [DB]를 제거할 수 있습니다.
10(B)=P
/ \
[DB] 15(B)=w
\
20(R)=f
(2) 복구 방법: 형제(w)의 색을 부모(P)의 색으로 맞추고, 부모와 먼 자식을 Black으로 만든 뒤, 부모 기준으로 Left Rotation을 수행합니다.
- w(15): Color ← Color(P = 10)
- P(10): → Black
- f(20): → Black
- RotateLeft(P = 10)
(3) 복구 이후 상태: Black-height가 복구되며, [DB] 상태가 제거되어 삭제 복구가 종료됩니다.
15(B)
/ \
10(B) 20(B)
삭제 복구가 종료되는 경우는 크게 두 가지입니다.
- Case 4에서 회전+색 재배치로 Double Black이 제거되는 경우
- Case 2로 전파된 Double Black이 Red 부모(P)에서 P를 Black으로 바꾸며 흡수되는 경우
1.3.1 삭제 전체 흐름 예제 (케이스가 실제로 적용되는 과정)
앞에서 Case 1 ~ Case 4를 각각 독립적으로 살펴보았지만, 실제 삭제 과정에서는 하나의 트리에서 여러 케이스가 연속적으로 적용되는 경우가 많습니다. 이 섹션에서는 정상적인 Red-Black Tree 상태에서 시작하여, 특정 노드를 삭제하면서 어떤 Case가 선택되고, 그 결과 트리가 어떻게 변하는지를 흐름 단위로 살펴봅니다.
중요한 점은, 삭제 알고리즘이 “지금 이 케이스 하나로 끝난다”가 아니라, Double Black을 이동시키고 형태를 바꾸면서 최종 상태로 수렴하는 과정이라는 점입니다.
초기 트리 상태 (정상적인 Red-Black Tree)
20(B)
/ \
10(B) 30(B)
/ \ / \
5(B) 15(B) 25(B) 40(B)모든 경로의 Black-height는 동일하며, Red-Black Tree 규칙을 모두 만족하는 정상 상태입니다.
Step 1) Black Leaf 노드 삭제 → Double Black 발생
노드 5(B)를 삭제한다고 가정해 보겠습니다. 5는 Black Leaf이므로 삭제 직후 해당 위치에는 Black-height가 하나 부족한 상태가 발생하며, 이를 Double Black([DB])으로 표현합니다.
20(B)
/ \
10(B) 30(B)
/ \ / \
[DB] 15(B) 25(B) 40(B)이제 [DB]의 부모는 10(B), 형제(w)는 15(B)입니다.
Step 2) Case 2 적용 (형제 Black + 형제 자식 Black)
형제 15(B)와 그 자식(NIL)은 모두 Black이므로, 이 상황은 Case 2에 해당합니다.
- 형제(w)를 Red로 변경
- Double Black을 부모로 전파
20(B)
/ \
10(B)←[DB] 30(B)
\ / \
15(R) 25(B) 40(B)이 단계에서는 문제가 해결되지 않았고, Double Black이 부모(10)로 이동했을 뿐입니다. 삭제 복구는 계속 진행됩니다.
Step 3) 다시 Case 판별 → Case 2 재적용 (전파)
이제 [DB]의 부모는 20(B), 형제는 30(B)입니다. 또한 형제 30의 자식 25(B), 40(B) 역시 모두 Black이므로, 이 상태도 Case 2에 해당합니다.
- 형제(w=30)를 Red로 변경
- Double Black을 부모(20)로 전파
20(B)←[DB]
/ \
10(B) 30(R)
\ / \
15(R) 25(B) 40(B)
Step 4) 루트에서 루프 종료 → 마지막 정리로 마무리
Step 3에서 Double Black이 루트(20)로 올라오면, 코드의 FixDelete 루프 조건 (x != root)가 더 이상 성립하지 않아 반복이 종료됩니다. 그 다음 마지막 단계에서 SetColor(x, Black)이 호출되어 루트가 Black으로 정리됩니다.
이 예제에서는 루트 20이 원래도 Black이므로 색은 그대로이며, 결과적으로 아래 트리는 Red-Black 규칙을 만족하는 정상 상태가 됩니다.
20(B)
/ \
10(B) 30(R)
\ / \
15(R) 25(B) 40(B)
Black-height를 (시작 노드 포함 + NIL 포함) 기준으로 보면, 모든 경로의 Black 개수가 동일하게 유지됩니다.
- 20(B)→10(B)→NIL(B) : Black 3개
- 20(B)→10(B)→15(R)→NIL(B) : Black 3개
- 20(B)→30(R)→25(B)→NIL(B) : Black 3개
- 20(B)→30(R)→40(B)→NIL(B) : Black 3개
이 예제에서 확인할 수 있는 핵심 포인트
- 삭제는 하나의 Case로 끝나지 않고 여러 Case가 연속 적용될 수 있습니다.
- Case 2는 [DB]를 즉시 제거하지 않고 위로 전파시키는 단계입니다.
- 이 예제의 종료는 Case 4가 아니라, [DB]가 루트까지 올라가 루프 조건이 종료되는 방식입니다.
1.3.2 삭제 전체 흐름 예제 (Case 3 → Case 4로 실제로 변환되는 과정)
이번 예제는 정상적인 Red-Black Tree에서 시작하여, Black 노드 삭제 이후 발생하는 복구 과정을 개념적 흐름 중심으로 따라갑니다. 삭제 직후에는 Double Black 상태가 만들어지고, 이를 해결하는 과정에서 Case 2 → Case 3 → Case 4가 연속적으로 적용되며 트리가 점진적으로 정상 상태로 되돌아옵니다. 이 예제의 핵심은, 그중에서도 Case 3이 Case 4로 변환되는 순간을 구조 변화 관점에서 명확히 보여주는 데 있습니다.
초기 트리 상태 (정상적인 Red-Black Tree)
10(B)
/ \
5(B) 20(B)
/ \ / \
2(B) 7(B) 15(R) 25(B)
/ \
13(B) 17(B)위 트리는 모든 경로의 Black-height가 같고, Red-Black 규칙을 모두 만족하는 정상 상태입니다.
Step 1) 2(B) 삭제 → [DB] 발생
이제 2(B)를 삭제해 보겠습니다. 2는 Black Leaf이므로, 삭제 직후 그 자리는 NIL(Black)이지만, 경로의 Black이 하나 줄어든 상태가 됩니다. 이 “Black이 하나 부족한 상태”를 [DB]로 표시합니다.
10(B)
/ \
5(B) 20(B)
/ \ / \
[DB] 7(B) 15(R) 25(B)
/ \
13(B) 17(B)현재 [DB]의 부모(px)는 5(B), 형제(w)는 7(B)입니다.
Step 2) Case 2 적용 (형제 Black + 형제 자식 모두 Black) → 전파
w=7(B)의 자식은 모두 NIL(Black)이므로 이 상태는 Case 2입니다. Case 2는 [DB]를 즉시 제거하지 못하고, w를 Red로 바꾼 뒤 [DB]를 부모로 올려 전파합니다.
- w(7): Black → Red
- [DB] ← px(5) (x = px로 이동)
10(B)
/ \
5(B)←[DB] 20(B)
\ / \
7(R) 15(R) 25(B)
/ \
13(B) 17(B)여기서 중요한 포인트는, [DB]가 “NIL 자리”에만 붙는 게 아니라 FixDelete 루프 안에서는 x가 바뀌면서 [DB]가 상위 노드로 이동할 수 있다는 점입니다. 지금은 [DB]가 노드 5로 올라간 상태입니다.
Step 3) Case 3 발생 (가까운 자식 Red, 먼 자식 Black) → Case 4로 변환
이제 [DB]의 부모(px)는 10(B), 형제(w)는 20(B)입니다. 또한 [DB]는 px의 왼쪽에 있으므로, w 기준으로
- 가까운 자식(near) = w.Left = 15(R)
- 먼 자식(far) = w.Right = 25(B)
즉, w는 Black, near는 Red, far는 Black이므로 이 상태가 바로 Case 3입니다. Case 3의 목적은 [DB]를 없애는 것이 아니라, 회전 1회로 Case 4 형태(먼 자식 Red)로 바꾸는 것입니다.
Case 3에서 수행
- RotateRight(w = 20)
- near(15): Red → Black
- w(20): Black → Red
Case 3 적용 후 상태 (이제 Case 4 형태가 됨)
10(B)
/ \
5(B)←[DB] 15(B)
\ / \
7(R) 13(B) 20(R)
/ \
17(B) 25(B)이제 형제(w)는 15(B)로 재평가되며, w의 먼 자식(far = w.Right)이 20(R)로 Red가 되었으므로 다음 단계는 Case 4로 이어집니다.
Step 4) Case 4 적용 (먼 자식 Red) → [DB] 제거 및 종료
Case 4는 회전 + 색 재배치로 [DB]를 즉시 제거하고 종료하는 단계입니다. (아래는 [DB]가 px=10 기준 왼쪽에 있는 상황의 전형적인 처리 흐름입니다.)
- w(15): Color ← Color(px=10) (여기서는 둘 다 Black이므로 변화 없음)
- px(10): → Black (이미 Black)
- far(20): → Black
- RotateLeft(px = 10)
최종 복구 상태 (정상 RB 트리로 복귀)
15(B)
/ \
10(B) 20(B)
/ \ / \
5(B) 13(B) 17(B) 25(B)
\
7(R)이제 [DB]가 제거되었고, 모든 경로의 Black-height가 다시 동일해져 트리는 정상적인 Red-Black Tree 규칙을 만족합니다.
이 예제에서 확인할 수 있는 핵심 포인트
- Case 3은 종결 케이스가 아니라, Case 4로 “변환”하는 단계입니다.
- 실제로는 삭제 1회 후 FixDelete 루프 안에서 Case 2 → Case 3 → Case 4처럼 연속 적용되는 흐름이 자주 나옵니다.
- 따라서 삭제 복구는 “케이스 암기”보다 [DB](x)가 어디로 이동했고, w(형제)가 누구로 바뀌었는지를 추적하는 관점이 훨씬 직관적입니다.
1.4 정리
정리하면, 삽입은 “삼촌이 Red면 색 뒤집기, Black이면 회전”이라는 두 패턴으로 귀결되며, 삭제는 형제(w)와 그 자식 색 조합에 따라 네 가지 케이스로 복구됩니다. 삭제는 [DB] 상태를 이동·변환·제거하는 과정을 거쳐, 최종적으로 모든 Red-Black Tree 규칙을 만족하는 트리로 되돌리는 절차입니다.
※ 동작을 시각적으로 확인해보기
아래 링크는 Red-Black Tree의 삽입(Insertion)과 삭제(Deletion) 시 발생하는 색 변경과 회전 과정을 단계별로 시각화해 주는 도구입니다. 노드가 추가되거나 제거될 때, Black-height를 유지하기 위해 어떤 규칙이 적용되고, 어떤 케이스(Case 1~4)로 구조가 복구되는지를 직접 확인할 수 있습니다.
https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
2. Red-Black Tree가 활용되는 대표적인 사례
Unity/게임 클라이언트에서 Red-Black Tree를 직접 구현해 쓰는 경우는 많지 않습니다. 대부분은 List 정렬, Dictionary, HashSet, PriorityQueue(일반적으로 힙으로 구현) 등으로 충분하기 때문입니다. 그럼에도 Red-Black Tree가 의미를 가지는 경우는 분명히 존재하며, 핵심은 “정렬된 상태 유지 + 잦은 갱신 + 최악 성능 회피”입니다.
- 정렬된 상태로의 순회가 항상 필요하고, 삽입/삭제가 자주 발생하는 경우
- 범위 기반 조회(예: 특정 값 이상/이하, 구간 처리)가 자주 필요한 경우
- 이 글에서 구현한 Red-Black Tree에는 범위 기반 조회를 위한 전용 메서드는 포함되어 있지 않습니다. 이는 Red-Black Tree의 핵심인 삽입/삭제 시의 균형 유지와 복구 알고리즘에 집중하기 위한 의도적인 선택입니다.
- 범위 조회는 트리의 구조나 색 규칙을 변경하지 않으며, 중위 순회(InOrder)를 기반으로 조건만 추가하면 쉽게 확장할 수 있는 응용 기능에 해당합니다.
게임 실무 관점 예시는 다음과 같습니다.
- 랭킹/점수 보조 인덱스: 점수가 계속 갱신되면서도 “정렬된 순서”로 일부 구간을 빠르게 뽑아야 하는 경우
- 시간 기반 스케줄(타임라인) 보조 인덱스: 특정 시간 구간의 이벤트를 범위 조회로 걸러야 하는 경우
- 서버 및 개발용 내부 도구에서의 정렬 컨테이너: 콘텐츠 빌드 툴, 데이터 검증 툴에서 반복 삽입/삭제와 정렬 순회가 동시에 필요한 경우
다만, Unity 런타임에서 GC/할당 민감도가 높다면 노드 기반 트리 구조는 객체 할당이 많아질 수 있습니다. 프로젝트 특성에 따라 풀링(Object Pooling)이나 구조체 기반 대체 설계가 필요할 수 있습니다. 이 글의 목적은 실전 적용보다 “왜 균형 트리가 필요하고, 어떻게 동작하는지”를 정확히 이해하는 데에 있습니다.
3. Red-Black Tree가 제공하는 기능(구현 기준)
이번에 구현할 RedBlackTree<T>는 다음 기능을 제공합니다.
- Count: 현재 저장된 노드 개수(중복 없음)
- Add: 키 삽입(중복이면 false)
- Remove: 키 삭제(삭제 성공 여부 반환)
- Contains / TryGetValue: 키 존재 여부 확인 및 값 반환
- Min / Max: 최솟값/최댓값
- InOrder: 중위 순회(오름차순)
4. Red-Black Tree의 내부 동작 방식
이 섹션에서는 “개념”이 아니라, 구현 관점에서 내부가 어떤 규칙을 유지하고 어떤 순서로 호출되는지를 설명합니다. Red-Black Tree에서 성능과 정확성을 좌우하는 포인트는 크게 3가지입니다.
- 삽입/삭제는 먼저 BST 규칙대로 처리하여 정렬을 유지합니다.
- 삽입/삭제로 깨진 Red-Black 규칙을 색 변경(Recolor)과 회전(Rotation)으로 복구합니다.
- null을 NIL(Black)로 취급하되, 삭제 보정에서는 x가 null일 수 있으므로 부모(px)를 함께 추적하는 구조가 안전합니다.
4.1 null을 NIL(Black)로 취급하는 방식
Red-Black Tree 규칙에서는 “모든 Leaf(NIL)는 Black”으로 취급합니다. 실제 구현에서 매번 NIL 노드를 따로 만들면 포인터와 메모리 관리가 복잡해질 수 있으므로, 많은 구현은 null을 NIL로 간주합니다. 이때 핵심은 다음 한 줄입니다.
GetColor(null) = Black
즉, 자식 포인터가 null이면 “그 자리에 Black NIL이 있다”고 생각하고 규칙을 검사합니다. 이 구현도 동일하며, 다음과 같은 형태로 안전하게 처리합니다.
private static Color GetColor(Node n) => n?.Color ?? Color.Black;
private static void SetColor(Node n, Color c)
{
if (n != null)
{
n.Color = c;
}
}이 방식의 장점은, 삽입/삭제 보정에서 “자식이 없을 때도 Black으로 동작”하도록 코드를 단순화할 수 있다는 점입니다. 다만 삭제 보정에서는 x가 null이 될 수 있으므로, x.Parent에 직접 접근하면 null 참조 위험이 생깁니다. 그래서 이 구현은 FixDelete(x, px) 형태로 부모(px)를 별도로 전달합니다.
4.2 회전(Rotation) 처리
회전은 트리의 “정렬 규칙”을 깨지 않으면서 연결 관계만 바꾸는 연산입니다. 아래 예시는 회전이 구조만 조정하고, BST 정렬 규칙(왼쪽 < 부모 < 오른쪽)은 유지된다는 점을 보여줍니다.
LL 형태(우회전)
30 20
/ → / \
20 10 30
/
10
RR 형태(좌회전)
10 20
\ → / \
20 10 30
\
30
10(x) 20(y)
\ → / \
20(y) 10(x) 30
/ \ \
15 30 15- 20 왼쪽 자식으로 15가 있는 경우, 15는 10의 오른쪽 자식이 됨
private void RotateLeft(Node x)
{
Node y = x.Right;
x.Right = y.Left;
if (y.Left != null)
{
y.Left.Parent = x;
}
y.Parent = x.Parent;
if (x.Parent == null)
{
_root = y;
}
else if (x == x.Parent.Left)
{
x.Parent.Left = y;
}
else
{
x.Parent.Right = y;
}
y.Left = x;
x.Parent = y;
}
4.3 삽입 코드 흐름
삽입은 크게 2단계로 나뉩니다.
- 1단계: BST 삽입 - 비교기로 내려가며 null 자리에 새 노드를 붙입니다.
- 2단계: 복구 - 새 노드를 Red로 삽입한 뒤, 연속 Red(부모-자식 Red) 위반을 FixInsert로 복구합니다.
1) BST 삽입은 일반 BST와 동일합니다. 루트에서 시작해 key를 비교하며 내려가고, 같은 키면 삽입하지 않습니다. 삽입되는 새 노드는 기본적으로 Red입니다.
public bool Add(T key)
{
// 표준 BST 삽입 위치 탐색
Node y = null; // 부모 후보
Node x = _root; // 탐색 포인터
while (x != null)
{
int c = _cmp.Compare(key, x.Key);
if (c == 0)
{
return false; // 중복 금지
}
y = x;
x = (c < 0) ? x.Left : x.Right;
}
// 새 노드는 항상 Red로 삽입
Node z = new Node(key, Color.Red) { Parent = y };
if (y == null)
{
_root = z;
}
else if (_cmp.Compare(key, y.Key) < 0)
{
y.Left = z;
}
else
{
y.Right = z;
}
// 삽입으로 깨진 RB 규칙 복구
FixInsert(z);
_count++;
return true;
}
2) FixInsert(z)의 핵심은 “부모가 Red인 동안 반복”입니다. 새 노드를 Red로 넣으면 Black-height는 깨지지 않지만, 부모가 Red이면 연속 Red 금지 규칙이 깨질 수 있습니다. 이 위반은 삼촌(uncle)의 색에 따라 두 패턴으로 해결됩니다.
- 삼촌이 Red: 색 뒤집기(Recolor)로 위반을 위로 올립니다.
- 삼촌이 Black(NIL 포함): 회전(LL/LR/RR/RL) + 색 교환으로 위반을 즉시 제거합니다.
FixInsert는 부모(p)와 조부모(g), 삼촌(y)를 잡아 케이스를 분기합니다. 좌/우는 대칭이며, 한쪽만 이해하면 다른 쪽은 방향만 반대입니다.
private void FixInsert(Node z)
{
// 부모가 Red인 동안만 위반 가능
while (z != _root && GetColor(z.Parent) == Color.Red)
{
Node p = z.Parent;
Node g = p.Parent;
if (p == g.Left)
{
Node y = g.Right; // 삼촌
if (GetColor(y) == Color.Red)
{
// Case 1: 부모/삼촌 Red → 색 뒤집기
SetColor(p, Color.Black);
SetColor(y, Color.Black);
SetColor(g, Color.Red);
z = g;
}
else
{
if (z == p.Right)
{
// Case 2: 내부형 → 외부형으로 변환
z = p;
RotateLeft(z);
p = z.Parent;
g = p.Parent;
}
// Case 3: 외부형 → 회전 + 색 교환
SetColor(p, Color.Black);
SetColor(g, Color.Red);
RotateRight(g);
break;
}
}
else
{
// 좌우 대칭 케이스
Node y = g.Left;
if (GetColor(y) == Color.Red)
{
SetColor(p, Color.Black);
SetColor(y, Color.Black);
SetColor(g, Color.Red);
z = g;
}
else
{
if (z == p.Left)
{
z = p;
RotateRight(z);
p = z.Parent;
g = p.Parent;
}
SetColor(p, Color.Black);
SetColor(g, Color.Red);
RotateLeft(g);
break;
}
}
}
// 루트는 항상 Black
SetColor(_root, Color.Black);
}마지막에 Root를 Black으로 강제하는 이유는, 색 뒤집기 과정에서 조부모가 Red로 바뀌며 위로 전파될 수 있기 때문입니다. 조부모가 Root인 상황에서는 “조부모를 Red로 만들려던 의도”가 있어도 Root는 규칙상 Black이어야 하므로 최종적으로 Black으로 되돌립니다.
4.4 삭제 코드 흐름
삭제는 크게 2단계로 나뉩니다.
- 1단계: BST 삭제 - 자식 0/1/2개 케이스를 표준 BST 규칙으로 처리합니다.
- 2단계: 복구 - 제거된 노드가 Black이었다면 Black-height가 깨질 수 있어 FixDelete로 보정합니다.
삭제 코드를 보기 전에 Transplant 함수에 대해서 잠깐 알아보겠습니다.
Transplant(u, v)의 역할과 동작 원리
Transplant(u, v)는 “노드 u가 있던 자리를 노드 v로 통째로 교체”하는 유틸 함수입니다. 값(Key)을 복사하는 것이 아니라, 부모가 가진 자식 포인터(Left/Right)를 v로 바꾸어 서브트리 연결을 갈아 끼우는 역할을 합니다.
BST/Red-Black Tree 삭제 구현에서 자식 0개/1개 케이스는 물론, 자식 2개 케이스에서 successor를 이동시키는 과정에서도 반복적으로 사용됩니다. 이 함수 자체는 정렬 규칙(BST)만 유지하도록 “링크”만 바꾸며, Red-Black 색 규칙 복구(FixDelete)는 별도 단계에서 수행합니다.
private void Transplant(Node u, Node v)
{
if (u.Parent == null)
{
_root = v;
}
else if (u == u.Parent.Left)
{
u.Parent.Left = v;
}
else
{
u.Parent.Right = v;
}
if (v != null)
{
v.Parent = u.Parent;
}
}
동작 순서(코드 관점)
- u가 Root면, 트리의 루트(_root)를 v로 교체합니다.
- u가 부모의 Left 자식이면, 부모의 Left 포인터를 v로 교체합니다.
- u가 부모의 Right 자식이면, 부모의 Right 포인터를 v로 교체합니다.
- v가 null이 아니라면, v.Parent를 u.Parent로 갱신합니다.
즉 “부모 입장에서 자식 포인터를 u에서 v로 바꾸고, v의 Parent도 그에 맞게 정리하는 함수”입니다. u의 Left/Right는 건드리지 않으며, u를 메모리에서 제거하지도 않습니다(그 이후 GC 대상이 될 뿐입니다).
예시 1) u가 Root인 경우
u가 루트라면, 루트 포인터가 v로 바뀝니다.
Before:
10(u)
/ \
5 20(v)
Transplant(u=10, v=20)
After:
20(v)
이 경우 (u.Parent == null) 분기가 실행되며, _root = v가 됩니다.
예시 2) u가 부모의 Left 자식인 경우
u가 부모의 왼쪽 자식이었다면, 부모의 Left 포인터만 v로 교체됩니다.
Before:
30
/
20(u)
\
25(v)
Transplant(u=20, v=25)
After:
30
/
25(v)
이 경우 (u == u.Parent.Left) 분기가 실행되어 u.Parent.Left = v로 바뀌며, 이어서 v.Parent = u.Parent가 적용됩니다.
예시 3) u가 부모의 Right 자식인 경우
u가 부모의 오른쪽 자식이었다면, 부모의 Right 포인터가 v로 교체됩니다.
Before:
10
\
20(u)
/
15(v)
Transplant(u=20, v=15)
After:
10
\
15(v)
이 경우 else 분기가 실행되어 u.Parent.Right = v로 바뀌고, v.Parent도 10으로 갱신됩니다.
예시 4) v가 null인 경우(Leaf 삭제)
v가 null이면 “그 자리를 비운다”는 의미입니다. 즉, u를 부모에서 떼어내고 그 링크를 null(NIL)로 만듭니다.
Before:
10
\
20(u)
Transplant(u=20, v=null)
After:
10
v가 null이므로 v.Parent 갱신은 실행되지 않습니다. 결과적으로 부모의 자식 포인터가 null이 됩니다.
주의 사항: Transplant는 “구조”만 바꿉니다
- Key(값)를 복사하지 않습니다. 링크만 교체합니다.
- Red/Black 색 규칙을 복구하지 않습니다. (FixDelete / FixInsert가 담당)
- 삭제 로직에서는 Transplant로 BST 구조를 먼저 맞춘 뒤, 필요하면 색/회전을 통해 Red-Black 규칙을 복구합니다.
BST 삭제는 다음 순서로 진행됩니다. 삭제 대상 z를 찾은 뒤 실제로 트리에서 제거되는 노드를 y로 두고, y의 자리를 대체할 노드를 x로 둡니다.
- z: 삭제하고 싶은 노드
- y: 실제로 트리에서 제거되는 노드(초기에는 z, 2자식이면 successor로 변경)
- x: y의 자리를 대체하는 노드(또는 null/NIL)
- yOriginal: y의 원래 색(Black이면 보정 필요 가능성)
public bool Remove(T key)
{
Node z = FindNode(key);
if (z == null)
{
return false;
}
// y: 실제로 트리 구조에서 제거될 노드
Node y = z;
Color yOriginal = y.Color;
// x: y가 제거된 자리를 대체하는 노드 (또는 null = NIL)
Node x;
Node px; // x의 부모 (x가 null일 수 있으므로 명시적으로 관리)
if (z.Left == null)
{
x = z.Right;
px = z.Parent;
Transplant(z, z.Right);
}
else if (z.Right == null)
{
x = z.Left;
px = z.Parent;
Transplant(z, z.Left);
}
else
{
// 중위 후속자(successor)로 대체
y = Minimum(z.Right);
yOriginal = y.Color;
x = y.Right;
if (y.Parent == z)
{
px = y;
}
else
{
px = y.Parent;
Transplant(y, y.Right);
y.Right = z.Right;
if (y.Right != null)
{
y.Right.Parent = y;
}
}
Transplant(z, y);
y.Left = z.Left;
if (y.Left != null)
{
y.Left.Parent = y;
}
// 논리적 노드(z)의 색을 그대로 유지
y.Color = z.Color;
}
// 제거된 노드가 Black이면 black-height 깨짐 → 보정 필요
if (yOriginal == Color.Black)
{
FixDelete(x, px);
}
_count--;
return true;
}
삭제 보정이 필요한 조건은 yOriginal이 Black인 경우입니다. Red 노드를 제거하면 Black-height는 변하지 않지만, Black 노드를 제거하면 해당 경로에서 Black이 하나 줄어들 수 있습니다. 이 부족 상태를 개념적으로 “Double Black([DB])”로 설명할 수 있으며, 구현에서는 x와 px를 통해 그 위치를 추적하며 보정합니다.
FixDelete(x, px)에서 x는 “Black 부족 상태가 붙어 있을 수 있는 위치”이며, x가 null일 수 있으므로 부모(px)를 함께 넘겨 형제(w)를 안전하게 구합니다. 루프는 x가 루트가 아니고 x가 Black(또는 NIL)인 동안 반복되며, 형제(w)의 색과 w의 자식 색 조합에 따라 케이스가 분기됩니다.
private void FixDelete(Node x, Node px)
{
// x가 Double-Black 상태일 수 있음
while (x != _root && GetColor(x) == Color.Black)
{
if (px == null)
{
x = _root;
break;
}
if (x == px.Left)
{
Node w = px.Right; // 형제
// [추가] 형제가 null(NIL)인 경우 = Case 2로 취급(전파)
if (w == null)
{
x = px;
px = x.Parent;
continue;
}
// Case 1: 형제가 Red
if (GetColor(w) == Color.Red)
{
SetColor(w, Color.Black);
SetColor(px, Color.Red);
RotateLeft(px);
w = px.Right;
// [추가] 회전 후 형제가 null(NIL)일 수 있음 = Case 2로 취급(전파)
if (w == null)
{
x = px;
px = x.Parent;
continue;
}
}
// Case 2: 형제 + 형제 자식 모두 Black
if (GetColor(w?.Left) == Color.Black &&
GetColor(w?.Right) == Color.Black)
{
SetColor(w, Color.Red);
x = px;
px = x.Parent;
}
else
{
// Case 3:
// 형제(w)는 Black
// x와 가까운 형제의 자식(near = w.Left)은 Red
// 먼 자식(far = w.Right)은 Black
// → 회전으로 Case 4 형태(먼 자식 Red)로 변환
if (GetColor(w?.Right) == Color.Black)
{
SetColor(w.Left, Color.Black);
SetColor(w, Color.Red);
RotateRight(w);
w = px.Right;
// [추가] 회전 후 형제가 null(NIL)일 수 있음 = Case 2로 취급(전파)
if (w == null)
{
x = px;
px = x.Parent;
continue;
}
}
// Case 4:
// 형제(w)는 Black
// 먼 자식(far = w.Right)이 Red
// → 회전 + 색 재배치로 Double Black 제거 (종결 케이스)
SetColor(w, GetColor(px));
SetColor(px, Color.Black);
SetColor(w.Right, Color.Black);
RotateLeft(px);
x = _root;
break;
}
}
else
{
// 좌우 대칭
Node w = px.Left;
// [추가] 형제가 null(NIL)인 경우 = Case 2로 취급(전파)
if (w == null)
{
x = px;
px = x.Parent;
continue;
}
if (GetColor(w) == Color.Red)
{
SetColor(w, Color.Black);
SetColor(px, Color.Red);
RotateRight(px);
w = px.Left;
// [추가] 회전 후 형제가 null(NIL)일 수 있음 = Case 2로 취급(전파)
if (w == null)
{
x = px;
px = x.Parent;
continue;
}
}
if (GetColor(w?.Right) == Color.Black &&
GetColor(w?.Left) == Color.Black)
{
SetColor(w, Color.Red);
x = px;
px = x.Parent;
}
else
{
if (GetColor(w?.Left) == Color.Black)
{
SetColor(w.Right, Color.Black);
SetColor(w, Color.Red);
RotateLeft(w);
w = px.Left;
// [추가] 회전 후 형제가 null(NIL)일 수 있음 = Case 2로 취급(전파)
if (w == null)
{
x = px;
px = x.Parent;
continue;
}
}
SetColor(w, GetColor(px));
SetColor(px, Color.Black);
SetColor(w.Left, Color.Black);
RotateRight(px);
x = _root;
break;
}
}
}
if (x != null)
{
SetColor(x, Color.Black);
}
}
삭제 보정에서 중요한 점은 Case 2(전파)가 구조적으로 문제를 해결하는 단계는 아니라는 것입니다. 형제(w)와 그 자식이 모두 Black인 경우에는 회전으로 Double Black을 즉시 제거할 수 없기 때문에, w를 Red로 바꾸고 Black 부족 상태를 부모(px)로 전파합니다(x = px). 이 전파 과정은 반복되며, 부모가 Red인 상태에서 Case 2가 적용되면 부모를 Black으로 바꾸는 것만으로 Double Black이 해소되어 종료될 수 있습니다. 반대로 부모가 Black이면 전파가 계속되거나, 이후 Case 3 또는 Case 4로 변환되어 최종적으로 Case 4에서 구조적 복구가 이루어집니다.
4.5 AVL과의 비교: 무엇을 “유지 값”으로 삼는가
AVL 트리는 각 노드가 Height를 저장하고 Balance Factor로 불균형을 판별한 뒤 회전으로 즉시 복구합니다. 반면 Red-Black Tree는 Height를 저장하지 않고, “연속 Red 금지”와 “Black-height 일치” 규칙을 유지하여 높이의 상한을 제한합니다. 결과적으로 AVL은 더 강한 균형으로 탐색 경로가 짧은 경향이 있고, Red-Black Tree는 삽입/삭제 시 회전과 조정이 상대적으로 덜 발생하는 경향이 있어 갱신이 잦은 환경에서 유리할 수 있습니다.
5. C# 기반 Red-Black Tree 직접 구현 코드
아래는 RedBlackTree<T> 전체 코드입니다.
using System;
using BCL = System.Collections.Generic; // BCL - Base Class Library
namespace Daebak.Common.Collections
{
/// <summary>
/// Red-Black Tree
/// - BST 성질을 유지하면서 삽입/삭제 시 자동으로 균형을 맞추는 자가 균형 이진 트리
/// - 모든 경로의 black-height를 동일하게 유지
/// </summary>
public class RedBlackTree<T>
{
// Red-Black Tree 노드 색상
private enum Color { Red, Black }
/// <summary>
/// 트리의 기본 노드
/// null 노드는 개념적으로 NIL(Black) 노드로 취급
/// </summary>
private sealed class Node
{
public T Key;
public Node Left;
public Node Right;
public Node Parent;
public Color Color;
public Node(T key, Color color)
{
Key = key;
Color = color;
}
}
private Node _root;
private readonly BCL.IComparer<T> _cmp;
private int _count;
public int Count => _count;
public RedBlackTree(BCL.IComparer<T> comparer = null)
{
_cmp = comparer ?? BCL.Comparer<T>.Default;
}
/// <summary>
/// 키 삽입 (중복 불가)
/// </summary>
public bool Add(T key)
{
// 표준 BST 삽입 위치 탐색
Node y = null; // 부모 후보
Node x = _root; // 탐색 포인터
while (x != null)
{
int c = _cmp.Compare(key, x.Key);
if (c == 0)
{
return false; // 중복 금지
}
y = x;
x = (c < 0) ? x.Left : x.Right;
}
// 새 노드는 항상 Red로 삽입
Node z = new Node(key, Color.Red) { Parent = y };
if (y == null)
{
_root = z;
}
else if (_cmp.Compare(key, y.Key) < 0)
{
y.Left = z;
}
else
{
y.Right = z;
}
// 삽입으로 깨진 RB 규칙 복구
FixInsert(z);
_count++;
return true;
}
public bool Contains(T key)
{
return FindNode(key) != null;
}
public bool TryGetValue(T key, out T found)
{
var n = FindNode(key);
if (n != null)
{
found = n.Key;
return true;
}
found = default;
return false;
}
/// <summary>
/// 키 삭제
/// </summary>
public bool Remove(T key)
{
Node z = FindNode(key);
if (z == null)
{
return false;
}
// y: 실제로 트리 구조에서 제거될 노드
Node y = z;
Color yOriginal = y.Color;
// x: y가 제거된 자리를 대체하는 노드 (또는 null = NIL)
Node x;
Node px; // x의 부모 (x가 null일 수 있으므로 명시적으로 관리)
if (z.Left == null)
{
x = z.Right;
px = z.Parent;
Transplant(z, z.Right);
}
else if (z.Right == null)
{
x = z.Left;
px = z.Parent;
Transplant(z, z.Left);
}
else
{
// 중위 후속자(successor)로 대체
y = Minimum(z.Right);
yOriginal = y.Color;
x = y.Right;
if (y.Parent == z)
{
px = y;
}
else
{
px = y.Parent;
Transplant(y, y.Right);
y.Right = z.Right;
if (y.Right != null)
{
y.Right.Parent = y;
}
}
Transplant(z, y);
y.Left = z.Left;
if (y.Left != null)
{
y.Left.Parent = y;
}
// 논리적 노드(z)의 색을 그대로 유지
y.Color = z.Color;
}
// 제거된 노드가 Black이면 black-height 깨짐 → 보정 필요
if (yOriginal == Color.Black)
{
FixDelete(x, px);
}
_count--;
return true;
}
public void Clear()
{
_root = null;
_count = 0;
}
/// <summary>
/// 중위 순회 (정렬된 순서)
/// </summary>
public BCL.IEnumerable<T> InOrder()
{
if (_root == null)
{
yield break;
}
var st = new BCL.Stack<Node>();
Node cur = _root;
while (cur != null || st.Count > 0)
{
while (cur != null)
{
st.Push(cur);
cur = cur.Left;
}
cur = st.Pop();
yield return cur.Key;
cur = cur.Right;
}
}
public T Min()
{
if (_root == null)
{
throw new InvalidOperationException("Tree is empty.");
}
return Minimum(_root).Key;
}
public T Max()
{
if (_root == null)
{
throw new InvalidOperationException("Tree is empty.");
}
return Maximum(_root).Key;
}
// ===== 내부 유틸 =====
/// <summary>
/// BST 탐색
/// </summary>
private Node FindNode(T key)
{
Node cur = _root;
while (cur != null)
{
int c = _cmp.Compare(key, cur.Key);
if (c == 0)
{
return cur;
}
cur = (c < 0) ? cur.Left : cur.Right;
}
return null;
}
private Node Minimum(Node n)
{
while (n.Left != null)
{
n = n.Left;
}
return n;
}
private Node Maximum(Node n)
{
while (n.Right != null)
{
n = n.Right;
}
return n;
}
/// <summary>
/// 좌회전
/// </summary>
private void RotateLeft(Node x)
{
Node y = x.Right;
x.Right = y.Left;
if (y.Left != null)
{
y.Left.Parent = x;
}
y.Parent = x.Parent;
if (x.Parent == null)
{
_root = y;
}
else if (x == x.Parent.Left)
{
x.Parent.Left = y;
}
else
{
x.Parent.Right = y;
}
y.Left = x;
x.Parent = y;
}
/// <summary>
/// 우회전
/// </summary>
private void RotateRight(Node x)
{
Node y = x.Left;
x.Left = y.Right;
if (y.Right != null)
{
y.Right.Parent = x;
}
y.Parent = x.Parent;
if (x.Parent == null)
{
_root = y;
}
else if (x == x.Parent.Right)
{
x.Parent.Right = y;
}
else
{
x.Parent.Left = y;
}
y.Right = x;
x.Parent = y;
}
/// <summary>
/// u 위치를 v 서브트리로 교체
/// </summary>
private void Transplant(Node u, Node v)
{
if (u.Parent == null)
{
_root = v;
}
else if (u == u.Parent.Left)
{
u.Parent.Left = v;
}
else
{
u.Parent.Right = v;
}
if (v != null)
{
v.Parent = u.Parent;
}
}
/// <summary>
/// 삽입 후 Red-Black Tree 규칙 복구
/// </summary>
private void FixInsert(Node z)
{
// 부모가 Red인 동안만 위반 가능
while (z != _root && GetColor(z.Parent) == Color.Red)
{
Node p = z.Parent;
Node g = p.Parent;
if (p == g.Left)
{
Node y = g.Right; // 삼촌
if (GetColor(y) == Color.Red)
{
// Case 1: 부모/삼촌 Red → 색 뒤집기
SetColor(p, Color.Black);
SetColor(y, Color.Black);
SetColor(g, Color.Red);
z = g;
}
else
{
if (z == p.Right)
{
// Case 2: 내부형 → 외부형으로 변환
z = p;
RotateLeft(z);
p = z.Parent;
g = p.Parent;
}
// Case 3: 외부형 → 회전 + 색 교환
SetColor(p, Color.Black);
SetColor(g, Color.Red);
RotateRight(g);
break;
}
}
else
{
// 좌우 대칭 케이스
Node y = g.Left;
if (GetColor(y) == Color.Red)
{
SetColor(p, Color.Black);
SetColor(y, Color.Black);
SetColor(g, Color.Red);
z = g;
}
else
{
if (z == p.Left)
{
z = p;
RotateRight(z);
p = z.Parent;
g = p.Parent;
}
SetColor(p, Color.Black);
SetColor(g, Color.Red);
RotateLeft(g);
break;
}
}
}
// 루트는 항상 Black
SetColor(_root, Color.Black);
}
/// <summary>
/// 삭제 후 Red-Black Tree 규칙 복구
/// </summary>
private void FixDelete(Node x, Node px)
{
// x가 Double-Black 상태일 수 있음
while (x != _root && GetColor(x) == Color.Black)
{
if (px == null)
{
x = _root;
break;
}
if (x == px.Left)
{
Node w = px.Right; // 형제
// [추가] 형제가 null(NIL)인 경우 = Case 2로 취급(전파)
if (w == null)
{
x = px;
px = x.Parent;
continue;
}
// Case 1: 형제가 Red
if (GetColor(w) == Color.Red)
{
SetColor(w, Color.Black);
SetColor(px, Color.Red);
RotateLeft(px);
w = px.Right;
// [추가] 회전 후 형제가 null(NIL)일 수 있음 = Case 2로 취급(전파)
if (w == null)
{
x = px;
px = x.Parent;
continue;
}
}
// Case 2: 형제 + 형제 자식 모두 Black
if (GetColor(w?.Left) == Color.Black &&
GetColor(w?.Right) == Color.Black)
{
SetColor(w, Color.Red);
x = px;
px = x.Parent;
}
else
{
// Case 3:
// 형제(w)는 Black
// x와 가까운 형제의 자식(near = w.Left)은 Red
// 먼 자식(far = w.Right)은 Black
// → 회전으로 Case 4 형태(먼 자식 Red)로 변환
if (GetColor(w?.Right) == Color.Black)
{
SetColor(w.Left, Color.Black);
SetColor(w, Color.Red);
RotateRight(w);
w = px.Right;
// [추가] 회전 후 형제가 null(NIL)일 수 있음 = Case 2로 취급(전파)
if (w == null)
{
x = px;
px = x.Parent;
continue;
}
}
// Case 4:
// 형제(w)는 Black
// 먼 자식(far = w.Right)이 Red
// → 회전 + 색 재배치로 Double Black 제거 (종결 케이스)
SetColor(w, GetColor(px));
SetColor(px, Color.Black);
SetColor(w.Right, Color.Black);
RotateLeft(px);
x = _root;
break;
}
}
else
{
// 좌우 대칭
Node w = px.Left;
// [추가] 형제가 null(NIL)인 경우 = Case 2로 취급(전파)
if (w == null)
{
x = px;
px = x.Parent;
continue;
}
if (GetColor(w) == Color.Red)
{
SetColor(w, Color.Black);
SetColor(px, Color.Red);
RotateRight(px);
w = px.Left;
// [추가] 회전 후 형제가 null(NIL)일 수 있음 = Case 2로 취급(전파)
if (w == null)
{
x = px;
px = x.Parent;
continue;
}
}
if (GetColor(w?.Right) == Color.Black &&
GetColor(w?.Left) == Color.Black)
{
SetColor(w, Color.Red);
x = px;
px = x.Parent;
}
else
{
if (GetColor(w?.Left) == Color.Black)
{
SetColor(w.Right, Color.Black);
SetColor(w, Color.Red);
RotateLeft(w);
w = px.Left;
// [추가] 회전 후 형제가 null(NIL)일 수 있음 = Case 2로 취급(전파)
if (w == null)
{
x = px;
px = x.Parent;
continue;
}
}
SetColor(w, GetColor(px));
SetColor(px, Color.Black);
SetColor(w.Left, Color.Black);
RotateRight(px);
x = _root;
break;
}
}
}
if (x != null)
{
SetColor(x, Color.Black);
}
}
private static Color GetColor(Node n) => n?.Color ?? Color.Black;
private static void SetColor(Node n, Color c)
{
if (n != null)
{
n.Color = c;
}
}
}
}6. Unity 환경에서 테스트 해보기
using UnityEngine;
using Daebak.Common.Collections;
public class Test_RedBlackTree : MonoBehaviour
{
void Start()
{
RedBlackTree<int> tree = new RedBlackTree<int>();
Debug.Log("=== Red-Black Tree 테스트 시작 ===");
// 회전/색 보정이 발생하기 쉬운 삽입 순서
int[] insert = { 30, 20, 10, 25, 40, 50, 22, 5, 35, 45, 60 };
foreach (int v in insert)
{
bool ok = tree.Add(v);
Debug.Log($"Add({v}) = {ok}");
}
Debug.Log($"Count = {tree.Count}");
Debug.Log("InOrder(오름차순):");
foreach (int v in tree.InOrder())
{
Debug.Log(v);
}
Debug.Log($"Contains(22) = {tree.Contains(22)}");
Debug.Log($"Contains(99) = {tree.Contains(99)}");
Debug.Log($"Min = {tree.Min()}");
Debug.Log($"Max = {tree.Max()}");
// 삭제: Leaf/1자식/2자식 케이스가 섞이도록 선택
Debug.Log($"Remove(20) = {tree.Remove(20)}");
Debug.Log($"Remove(45) = {tree.Remove(45)}");
Debug.Log($"Remove(30) = {tree.Remove(30)}");
Debug.Log($"Remove(30) (이미 삭제됨) = {tree.Remove(30)}");
Debug.Log("After Remove InOrder:");
foreach (int v in tree.InOrder())
{
Debug.Log(v);
}
Debug.Log("=== Red-Black Tree 테스트 종료 ===");
}
}
실행 결과
실행 결과는 삽입/삭제 순서에 따라 로그 순서가 달라질 수 있으나, 핵심 체크 포인트는 다음과 같습니다.
- InOrder가 항상 오름차순으로 출력된다(BST 정렬 규칙 유지).
- Count가 삽입/삭제 개수와 일치한다.
=== Red-Black Tree 테스트 시작 ===
Add(30) = True
Add(20) = True
...
Count = 11
InOrder(오름차순):
5
10
20
22
25
30
35
40
45
50
60
Contains(22) = True
Contains(99) = False
Min = 5
Max = 60
Remove(20) = True
Remove(45) = True
Remove(30) = True
Remove(30) (이미 삭제됨) = False
After Remove InOrder:
5
10
22
25
35
40
50
60
=== Red-Black Tree 테스트 종료 ===마무리
Red-Black Tree는 BST의 정렬 장점을 유지하면서, 삽입/삭제 이후에도 색 규칙과 회전으로 높이 상한을 제한해 최악의 경우에도 O(log N) 성능을 제공하는 자기 균형 트리입니다. AVL 트리보다 균형 조건이 덜 엄격한 대신, 삽입/삭제에서 회전이 덜 발생하는 경향이 있어 갱신이 잦은 환경에서 실용적인 선택이 될 수 있습니다.
Unity/게임 개발에서는 “정렬 유지 + 범위 조회 + 잦은 갱신”이 동시에 필요한 로직에서 활용 가치를 가질 수 있습니다. 반대로 “정렬”이 아니라 “최솟값/최댓값 우선 처리”가 목적이라면, PriorityQueue가 더 단순하고 적합합니다. 요구사항이 ‘정렬 유지’인지 ‘우선순위 추출’인지에 따라 자료구조를 선택하는 것이 중요합니다.
※ 다음 글에서는 Big O 표기법을 살펴보며, Red-Black Tree를 포함해 지금까지 다룬 자료구조들의 시간 복잡도와 성능 특성을 하나의 기준으로 비교하는 방법을 정리합니다.
'자료 구조' 카테고리의 다른 글
| Unity 개발자를 위한 정렬(Sort) 개념과 시간 복잡도 이해 (0) | 2026.01.13 |
|---|---|
| Unity 개발자를 위한 시간 복잡도(Big O) 개념 정리 (0) | 2026.01.13 |
| Unity 개발자를 위한 C# AVL(자기 균형 이진 탐색 트리) 구현 (0) | 2025.12.24 |
| Unity 개발자를 위한 C# BST(Binary Search Tree, 이진 탐색 트리) 구현 (0) | 2025.12.11 |
| Unity 개발자를 위한 C# Tree(트리) 구현 (0) | 2025.12.10 |
