이진 탐색 트리(Binary Search Tree, 이하 BST)는 이진 트리 구조에 정렬 규칙을 더한 자료구조입니다. 각 노드는 최대 두 개의 자식을 가지며, 모든 노드에 대해 다음 조건을 만족합니다.
- 어떤 노드 X에 대해, 왼쪽 서브 트리의 모든 키 < X의 키 (X의 왼쪽 자식들은 전부 X보다 작음)
- 어떤 노드 X에 대해, 오른쪽 서브트리의 모든 키 > X의 키 (X의 오른쪽 자식들은 전부 X보다 큼)
이 규칙 덕분에 BST는 탐색(Search), 삽입(Insert), 삭제(Remove)를 평균적으로 O(log n)에 수행할 수 있습니다. 다만 삽입과 삭제가 반복되면서 트리가 한쪽으로 심하게 치우치면, 높이가 커지면서 최악의 경우 O(n)까지 성능이 나빠질 수 있습니다. 이런 한계를 줄이기 위해 AVL(Adelson-Velsky and Landis) 트리, Red-Black 트리와 같은 균형 이진 탐색 트리가 함께 사용됩니다.
한쪽으로 치우친 트리 (높이 ≈ n)
|
균형에 가까운 트리 (높이 ≈ log n)
|
※ 위 그림은 BST가 입력 순서에 따라 구조가 크게 달라질 수 있음을 보여주는 예시입니다. 일반적인 BST는 스스로 균형을 유지하지 않기 때문에, 삽입 순서에 따라 한쪽으로 치우친 트리가 되어 성능이 저하될 수 있습니다.
트리 구조 자체에 대한 보다 기초적인 내용(루트/리프/부모/자식/깊이/높이 등)은 아래 글에 정리해 두었습니다. 트리를 처음 접하시는 경우 먼저 읽어 보시면 BST를 이해하는 데 도움이 됩니다.
Unity 개발자를 위한 C# Tree(트리) 구현
BST는 이런 일반적인 트리개념 위에 “왼쪽 < 현재 < 오른쪽” 정렬 규칙을 추가한 형태이고, 힙(Heap)·우선순위 큐(PriorityQueue) 같은 다른 트리 기반 자료구조와 비교했을 때 정렬된 상태를 유지하면서탐색과 삭제를 자주 수행해야 하는 상황에 적합합니다.
1. BST의 구조와 동작 방식
BST의 핵심은 “왼쪽 서브 트리의 키들은 항상 더 작고, 오른쪽 서브 트리의 키들은 항상 더 크다”는 정렬 규칙입니다.
1.1 삽입(Insert)의 개념적 흐름
BST 삽입은 “루트에서 시작해서 비교하면서 내려가다가, 비어 있는 자리에 꽂는 과정”으로 이해하면 됩니다.
- 현재 노드보다 작으면 왼쪽 자식으로 이동
- 현재 노드보다 크면 오른쪽 자식으로 이동
- 이동하려는 자리가 null이면 그 위치에 새 노드를 생성
- 이미 같은 키를 만나면 – 이번 구현에서는 중복을 허용하지 않고 삽입을 취소
위 규칙만 지키면, 삽입 후에도 왼쪽 < 현재 < 오른쪽 성질이 항상 유지됩니다.
예를 들어, 다음 순서로 정수를 삽입한다고 가정하겠습니다.
- 삽입 순서: 8, 3, 10, 1, 6, 14
※ 새로 삽입된 노드는 파란색으로 표시됩니다.
1) 8 삽입 – 트리가 비어 있으므로 루트가 됩니다.
| 8 (root) |
2) 3 삽입: 3 < 8 이므로 8의 왼쪽 자리에 배치됩니다.
| 8 / 3 |
3) 10 삽입: 10 > 8 이므로 8의 오른쪽 자리에 배치됩니다.
| 8 / \ 3 10 |
4) 1 삽입: 1 < 8 → 3, 1 < 3 → 3의 왼쪽에 배치됩니다.
| 8 / \ 3 10 / 1 |
5) 6 삽입: 6 < 8 → 3, 6 > 3 → 3의 오른쪽에 배치됩니다.
| 8 / \ 3 10 / \ 1 6 |
6) 14 삽입: 14 > 8 → 10, 14 > 10 → 10의 오른쪽에 배치됩니다.
| 8 / \ 3 10 / \ \ 1 6 14 |
※ 위 다이어그램은 BST 삽입 규칙(왼쪽 < 부모 < 오른쪽)을 단계별로 보여 주기 위한 예시입니다. 줄 간 공백은 를 사용해 위치를 맞춘 것이므로, 환경에 따라 약간의 차이는 있을 수 있습니다.
1.2 삭제(Remove)의 개념적 흐름
삭제 연산은 크게 세 가지 경우로 나눌 수 있습니다. 이 흐름을 그림으로 먼저 이해해 두면, 실제 코드를 읽을 때 훨씬 수월합니다.
- 자식이 없는 노드(리프) 삭제
- 자식이 1개인 노드 삭제
- 자식이 2개인 노드 삭제 (Hibbard Deletion)
① 자식이 없는 노드(리프) 삭제
리프 노드는 부모가 가리키는 Left 또는 Right를 null로 설정하기만 하면 됩니다.
예) 값 1(리프) 삭제
삭제 전
|
삭제 후
|
코드 관점에서는 부모 노드가 자식을 가리키던 참조를 null로 바꾸는 것만으로 삭제가 완료됩니다.
② 자식이 1개인 노드 삭제
자식이 하나뿐인 노드는, 부모가 삭제 대상 대신 그 자식을 직접 가리키도록 링크만 바꿔주면 됩니다.
예) 값 3(오른쪽 자식만 있는 노드) 삭제
삭제 전
|
삭제 후
|
위 경우에는 부모 8의 Left를 3 대신 6으로 바꿔 주면 됩니다. 3 노드는 더 이상 어느 곳에서도 참조되지 않기 때문에 GC 대상이 됩니다.
③ 자식이 2개인 노드 삭제 (Hibbard Deletion)
자식이 두 개 있는 노드 삭제가 BST에서 가장 중요한 케이스입니다. 한쪽 자식만 올려 버리면 정렬 규칙이 깨질 수 있기 때문에, 오른쪽 서브 트리의 최솟값(후계자, Successor)을 찾아 키를 교체한 후, 그 후계자를 한 번 더 삭제하는 방식을 사용합니다.
예) 값 3(왼쪽, 오른쪽 두 자식을 모두 가진 노드) 삭제
삭제 전
|
삭제 후
|
위 예시는 다음 순서로 진행됩니다.
- 삭제 대상 노드 3의 오른쪽 서브 트리로 이동합니다.
- 그 서브 트리에서 가장 왼쪽으로 내려가며 최솟값(후계자, Successor)을 찾습니다. 예시에서는 값 4입니다.
- 삭제 대상 노드(3)의 키를 후계자(4)의 키로 교체합니다. 이 시점에서 트리 구조 상의 “3”은 사라지고, “4”가 그 자리를 대체합니다.
- 오른쪽 서브 트리에서 원래 후계자 노드(4)를 한 번 더 삭제합니다. 이 노드는 보통 리프이거나 자식이 하나뿐이어서, 앞에서 본 ① 또는 ② 규칙으로 간단히 삭제할 수 있습니다.
이 알고리즘이 바로 Hibbard Deletion이며, 기본 BST 구현에서 가장 널리 사용되는 삭제 방식입니다. 실제 코드에서는 RemoveNode 같은 재귀 함수 안에서 위 세 가지 경우(리프, 자식 1개, 자식 2개)를 분기 처리하게 됩니다.
1.3 정렬된 리스트 얻기
트리의 모든 노드를 방문하는 방법을 트리 순회(Tree Traversal)라고 합니다. 대표적인 네 가지 방식은 다음과 같습니다.
- 전위 순회 (PreOrder): Root → Left → Right
- 중위 순회 (InOrder): Left → Root → Right
- 후위 순회 (PostOrder): Left → Right → Root
- 레벨 순회 (LevelOrder): 루트에서 시작해 같은 깊이의 노드를 왼쪽부터 오른쪽으로, 레벨 단위로 방문
※ 트리 순회에 대해 좀 더 상세한 설명은 Unity 개발자를 위한 C# Tree(트리) 구현 을 참고하시기 바랍니다.
BST에서는 특히 중위 순회(InOrder) 결과가 항상 정렬된 데이터라는 점이 중요합니다. 정렬된 리스트가 필요할 때, 전체 자료구조를 재정렬하지 않고 한 번 순회하는 것만으로 결과를 얻을 수 있습니다.
아래 그림에서 중위 순회로 데이터를 꺼내면 오름차순으로 정렬된 리스트를 얻을 수 있습니다.
- (안의 숫자가) 순회 순서입니다.
- 정렬된 리스트: 1, 3, 4, 6, 8, 10, 14
8(5)
/ \
3(2) 10(6)
/ \ \
1(1) 6(4) 14(7)
/
4(3)
※ 동작을 시각적으로 확인해보기
아래 링크는 이진 탐색 트리(Binary Search Tree)의 삽입 / 탐색 / 삭제 동작을 단계별로 시각화해 주는 도구입니다. 값의 크기에 따라 노드가 왼쪽/오른쪽으로 분기되는 과정을 직접 확인할 수 있습니다.
https://www.cs.usfca.edu/~galles/visualization/BST.html
2. BST가 활용되는 대표적인 사례
실제 게임/Unity 개발에서는 HashSet이나 Dictionary처럼 해시 기반 컨테이너를 더 자주 사용하지만, 정렬된 상태를 유지하면서 검색/삽입/삭제를 모두 자주 수행해야 하는 상황에서는 BST 또는 균형 BST가 적합합니다.
- 정렬된 리더보드 / 점수 테이블
- 점수를 기준으로 플레이어를 정렬한 상태로 유지
- 특정 점수 이상/이하 범위의 플레이어만 순회할 때 유리
- 특정 속성 기준으로 정렬된 오브젝트 목록
- 예: 몬스터의 레벨, 거리, HP 등을 기준으로 정렬
- “가장 가까운 N개”, “HP가 특정 구간에 있는 오브젝트” 등을 빠르게 추출
- 툴/디버그용 자료 구조
- 런타임에 생성된 객체들을 정렬된 상태로 모니터링하는 디버그 창
- 에디터 툴에서 특정 키(이름, ID, 우선순위)에 따라 정렬된 목록 유지
- 자료구조/알고리즘 학습 및 응용
- 힙(Heap), 우선순위 큐(PriorityQueue), 균형 트리 등 상위 구조의 기반 개념
- 트리 기반 탐색(DFS, BFS), 재귀/반복 패턴 연습
실제 상용 코드에서는 C#의 SortedDictionary<TKey, TValue>, SortedSet<T>처럼 내부적으로 균형 트리를 사용하는 컨테이너를 그대로 활용하는 경우가 많습니다. 여기서는 트리의 동작 원리를 이해하고, 필요하다면 직접 응용할 수 있는 수준을 목표로 합니다.
3. BST가 제공하는 기능(구현 기준)
이번에 구현한 Bst<T>는 학습 목적에 맞게 핵심 기능 위주로 구성했습니다. BST를 직접 구현할 때 “최소 이 정도는 제공하면 좋다”는 기준으로 보시면 됩니다.
- Count
- 트리에 포함된 노드(키)의 개수
- Insert(T key)
- 새 키 삽입
- 이미 같은 키가 있으면 삽입하지 않고 false 반환 (중복 무시)
- Contains(T key)
- 해당 키가 트리에 존재하는지 여부 반환
- TryFind(T key, out T found)
- 동일한 키가 존재하면
found에 실제 저장된 값 할당
- 동일한 키가 존재하면
- Remove(T key)
- 해당 키를 가진 노드를 삭제
- 삭제 성공 시 true, 없으면 false
- Min / Max / TryMin / TryMax
- 트리 전체의 최솟값/최댓값 조회
- 예외를 던지는 버전과 Try 패턴 버전 제공
- Height()
- 트리의 높이 반환 (빈 트리 -1, 루트만 있으면 0)
- Clear()
- 모든 노드 제거, 루트 참조만 끊어 GC 대상이 되도록 처리
- Traversal / IEnumerable<T>
- InOrder() : 중위 순회 (오름차순)
- PreOrder() : 전위 순회
- PostOrder() : 후위 순회
- LevelOrder() : 레벨 순회 (BFS)
- IEnumerable<T> 구현 : 기본 foreach는 InOrder를 사용
필요하다면 각 노드에 “서브 트리 크기”를 저장해 두고, k번째 원소 찾기, 구간 개수 세기 같은 고급 기능도 확장할 수 있습니다.
4. BST의 내부 동작 방식
이제 실제 C# 코드 관점에서 Bst<T>가 어떻게 동작하는지 살펴보겠습니다. 앞에서 본 개념적인 동작 흐름이 코드에서 어떻게 구현되는지 연결해서 보시면 이해하기 좋습니다.
4-1. Node 구조와 Comparer(비교기)
각 노드는 키와 왼쪽/오른쪽 자식에 대한 참조를 가지고 있습니다.
private sealed class Node
{
// 노드에 저장된 키
public T Key;
// 왼쪽 자식 노드
public Node Left;
// 오른쪽 자식 노드
public Node Right;
public Node(T key)
{
Key = key;
}
}
// 루트 노드
private Node _root;
// 키 비교용 비교기
private readonly BCL.IComparer<T> _cmp;
Comparer(비교기)는 생성자의 인자로 지정할 수 있으며, 지정하지 않으면 Comparer<T>.Default를 사용합니다. 이렇게 해 두면 커스텀 정렬 기준을 적용한 BST도 쉽게 만들 수 있습니다.
4-2. Insert 내부 흐름
Insert는 루트에서 시작해서 비교 결과에 따라 왼쪽/오른쪽으로 내려가다가, 비어 있는 자리에 새 노드를 생성합니다. 이미 같은 키를 만나면 false를 반환합니다.
public bool Insert(T key)
{
// 트리가 비어 있으면 루트로 삽입
if (_root == null)
{
_root = new Node(key);
Count = 1;
return true;
}
// 루트부터 내려가며 삽입 위치 탐색
Node cur = _root;
while (true)
{
int c = _cmp.Compare(key, cur.Key);
if (c == 0)
{
// 이미 동일한 키가 존재하는 경우 → 삽입하지 않음
return false;
}
else if (c < 0)
{
// 더 작은 키 → 왼쪽 서브 트리로 이동
if (cur.Left == null)
{
// 왼쪽 자리가 비어 있으면 여기 삽입
cur.Left = new Node(key);
++Count;
return true;
}
cur = cur.Left;
}
else
{
// 더 큰 키 → 오른쪽 서브 트리로 이동
if (cur.Right == null)
{
// 오른쪽 자리가 비어 있으면 여기 삽입
cur.Right = new Node(key);
++Count;
return true;
}
cur = cur.Right;
}
}
}
이 구현은 재귀를 사용하지 않고, while 루프 하나로 처리합니다. 깊이가 깊어져도 call stack을 소비하지 않는다는 점에서 Unity 환경에서 비교적 안전한 패턴입니다.
4-3. Remove와 Hibbard Deletion 구현
삭제는 Remove에서 RemoveNode라는 재귀 함수로 위임됩니다. 실제 삭제 로직은 Hibbard Deletion을 사용합니다.
public bool Remove(T key)
{
bool removed;
// 루트부터 시작해 재귀적으로 삭제 수행
_root = RemoveNode(_root, key, out removed);
if (removed)
{
--Count;
}
return removed;
}
핵심 로직은 RemoveNode입니다.
private Node RemoveNode(Node root, T key, out bool removed)
{
if (root == null)
{
// 더 내려갈 노드가 없으면 삭제 실패
removed = false;
return null;
}
int c = _cmp.Compare(key, root.Key);
if (c < 0)
{
// 삭제 대상 키가 더 작으면 왼쪽 서브 트리에서 삭제 시도
root.Left = RemoveNode(root.Left, key, out removed);
return root;
}
else if (c > 0)
{
// 삭제 대상 키가 더 크면 오른쪽 서브 트리에서 삭제 시도
root.Right = RemoveNode(root.Right, key, out removed);
return root;
}
else
{
// 삭제 대상 노드를 찾은 경우
removed = true;
// 자식이 0개 또는 1개인 경우: 해당 자식을 그대로 올려보냄
if (root.Left == null)
{
return root.Right;
}
if (root.Right == null)
{
return root.Left;
}
// 자식이 2개인 경우:
// 오른쪽 서브 트리에서 최솟값(후계자, successor)을 찾아 현재 노드의 키를 교체
Node s = LeftMost(root.Right);
root.Key = s.Key;
// 후계자 노드를 오른쪽 서브 트리에서 다시 삭제
root.Right = RemoveNode(root.Right, s.Key, out _);
return root;
}
}
자식 수에 따른 처리 방식은 1번 섹션에서 본 개념 그대로이며, 코드에서는 그 로직을 재귀적으로 표현하고 있습니다. 삭제 연산도 평균적으로 O(log n) 정도를 기대할 수 있지만, 트리가 심하게 기울어지면 O(n)까지 나빠질 수 있습니다.
4-4. 탐색(Contains / FindNode) 구현
탐색은 Insert와 거의 같은 흐름입니다. 다만 새 노드를 만들지 않고, 동일한 키를 찾을 때까지 왼쪽/오른쪽으로 내려가다가, 찾지 못하면 null을 반환합니다.
private Node FindNode(T key)
{
Node cur = _root;
// 현재 노드와 비교하면서 왼쪽/오른쪽으로 내려감
while (cur != null)
{
int c = _cmp.Compare(key, cur.Key);
if (c == 0)
{
// 키 일치 → 노드 반환
return cur;
}
else if (c < 0)
{
// 더 작은 키 → 왼쪽으로 이동
cur = cur.Left;
}
else
{
// 더 큰 키 → 오른쪽으로 이동
cur = cur.Right;
}
}
// 찾지 못한 경우
return null;
}
4-5. 순회 구현 (InOrder / PreOrder / PostOrder / LevelOrder)
이번 구현에서는 재귀(recursion) 대신 스택(Stack)과 큐(Queue)를 사용하는 반복형(iterative) 순회를 사용했습니다. 재귀는 코드가 간단하다는 장점이 있지만, 트리가 한쪽으로 치우친 경우 호출 깊이가 커져 스택 오버플로우(StackOverflow) 위험이 생길 수 있습니다. 반복형 순회는 명시적으로 자료구조(스택/큐)를 관리하므로, “현재 어디를 방문 중인지” 상태 변화를 눈으로 따라가기 쉽고, 재귀 깊이에 대한 부담을 줄일 수 있습니다.
아래 예제는 동일한 트리를 기준으로 스택/큐 상태가 어떻게 변하는지 보여준 뒤, 실제 C# 코드(반복형 구현)를 바로 이어서 제공합니다.
공통 예제 트리:
A
/ \
B C
/ \ \
D E F
4.5.1 PreOrder (전위 순회) - 반복형
PreOrder(전위 순회)는 Root → Left → Right 순서로 방문합니다. 반복형 구현에서는 스택에 루트를 넣고, Pop하면서 방문한 뒤 자식 노드를 Push하는 방식으로 진행합니다.
- 방문 순서: Root → Left → Right
- 핵심 규칙: Pop 후 방문, 그리고 오른쪽 자식 → 왼쪽 자식 순으로 Push (그래야 왼쪽이 먼저 Pop됨)
스택 상태 변화 (오른쪽이 top):
초기
Stack = [A]
Result = []
Step 1) Pop A 방문, Push(C), Push(B)
Stack = [C, B]
Result = [A]
Step 2) Pop B 방문, Push(E), Push(D)
Stack = [C, E, D]
Result = [A, B]
Step 3) Pop D 방문
Stack = [C, E]
Result = [A, B, D]
Step 4) Pop E 방문
Stack = [C]
Result = [A, B, D, E]
Step 5) Pop C 방문, Push(F)
Stack = [F]
Result = [A, B, D, E, C]
Step 6) Pop F 방문
Stack = []
Result = [A, B, D, E, C, F]
최종 PreOrder:
A → B → D → E → C → F
PreOrder 반복형 구현 코드:
public BCL.IEnumerable<T> PreOrder()
{
if (_root == null)
{
yield break;
}
BCL.Stack<Node> st = new();
st.Push(_root);
// 스택을 이용해 재귀 없이 전위 순회
while (st.Count > 0)
{
Node n = st.Pop();
yield return n.Key;
// 스택 특성상 오른쪽을 먼저 push해야 왼쪽이 먼저 처리됩니다.
if (n.Right != null)
{
st.Push(n.Right);
}
if (n.Left != null)
{
st.Push(n.Left);
}
}
}
4.5.2 InOrder (중위 순회) - 반복형
InOrder(중위 순회)는 Left → Root → Right 순서로 방문합니다. 반복형 구현에서는 “왼쪽 끝까지 내려가며 Push”한 뒤, 더 내려갈 수 없으면 Pop하여 방문하고, 방문한 노드의 오른쪽으로 이동하는 흐름을 반복합니다.
- 방문 순서: Left → Root → Right
- 핵심 규칙: cur를 왼쪽으로 끝까지 이동하며 Push, Pop하여 방문 후 cur = Right로 이동
스택 상태 변화 (오른쪽이 top):
초기
cur = A
Stack = []
Result = []
1) 왼쪽 끝까지 Push: A, B, D
Stack = [A, B, D]
cur = null
2) Pop D 방문
Stack = [A, B]
Result = [D]
cur = D.Right(null)
3) Pop B 방문, cur = B.Right(E)
Stack = [A]
Result = [D, B]
cur = E
4) E 왼쪽 처리: Push E
Stack = [A, E]
cur = null
5) Pop E 방문
Stack = [A]
Result = [D, B, E]
cur = E.Right(null)
6) Pop A 방문, cur = A.Right(C)
Stack = []
Result = [D, B, E, A]
cur = C
7) Push C
Stack = [C]
cur = null
8) Pop C 방문, cur = C.Right(F)
Stack = []
Result = [D, B, E, A, C]
cur = F
9) Push F, Pop F 방문
Stack = []
Result = [D, B, E, A, C, F]
최종 InOrder:
D → B → E → A → C → F
InOrder 반복형 구현 코드:
public BCL.IEnumerable<T> InOrder()
{
if (_root == null)
{
yield break;
}
BCL.Stack<Node> st = new();
Node cur = _root;
// 재귀 대신 스택을 사용하는 반복 구현
while (cur != null || st.Count > 0)
{
// 왼쪽 끝까지 내려가며 스택에 push
while (cur != null)
{
st.Push(cur);
cur = cur.Left;
}
// 가장 왼쪽 노드부터 처리
cur = st.Pop();
yield return cur.Key;
// 오른쪽 서브 트리로 이동
cur = cur.Right;
}
}
4.5.3 PostOrder (후위 순회) - 반복형
PostOrder(후위 순회)는 Left → Right → Root 순서로 방문합니다. 재귀로는 간단하지만, 반복형으로는 상태 관리가 필요합니다. 여기서는 두 개의 스택을 사용해 구현합니다.
- 방문 순서: Left → Right → Root
- 핵심 규칙:
- Stack1에서 Pop한 노드를 Stack2에 Push
- Stack1에는 Left/Right를 Push하면서 “Root → Left/Right”를 확장
- 마지막에 Stack2를 Pop하면 결과가 “Left → Right → Root”가 됩니다.
스택 상태 변화 (오른쪽이 top):
초기
st1 = [A]
st2 = []
Result = []
Step 1) st1 Pop(A) → st2 Push(A)
st1 Push(B), st1 Push(C)
st1 = [B, C]
st2 = [A]
Step 2) st1 Pop(C) → st2 Push(C)
st1 Push(F)
st1 = [B, F]
st2 = [A, C]
Step 3) st1 Pop(F) → st2 Push(F)
st1 = [B]
st2 = [A, C, F]
Step 4) st1 Pop(B) → st2 Push(B)
st1 Push(D), st1 Push(E)
st1 = [D, E]
st2 = [A, C, F, B]
Step 5) st1 Pop(E) → st2 Push(E)
st1 = [D]
st2 = [A, C, F, B, E]
Step 6) st1 Pop(D) → st2 Push(D)
st1 = []
st2 = [A, C, F, B, E, D]
이제 st2를 Pop하면서 방문:
Pop D, E, B, F, C, A
최종 PostOrder:
D → E → B → F → C → A
PostOrder 반복형 구현 코드 (스택 2개):
public BCL.IEnumerable<T> PostOrder()
{
if (_root == null)
{
yield break;
}
// 스택 2개 생성
BCL.Stack<Node> st1 = new();
BCL.Stack<Node> st2 = new();
st1.Push(_root); // st1에 root 삽입
// st1에서 꺼내 st2에 쌓은 뒤, st2를 역순으로 꺼내면 후위 순회 순서가 됩니다.
while (st1.Count > 0)
{
// st1에서 Pop하고, st2에 Push
Node n = st1.Pop();
st2.Push(n);
// 노드 자식들 st1에 Push
if (n.Left != null)
{
st1.Push(n.Left);
}
if (n.Right != null)
{
st1.Push(n.Right);
}
}
// 왼쪽 → 오른쪽 → 루트 순서로 출력
while (st2.Count > 0)
{
yield return st2.Pop().Key;
}
}
4.5.4 LevelOrder (레벨 순회) - 반복형
LevelOrder(레벨 순회)는 루트에서 시작해 같은 깊이(level)의 노드를 왼쪽에서 오른쪽으로 방문하는 방식입니다. 너비 우선 탐색(BFS)과 동일한 패턴이며 큐(Queue)를 사용합니다.
- 방문 순서: 레벨(깊이) 단위로 왼쪽 → 오른쪽
- 핵심 규칙: Dequeue하며 방문, 자식은 Enqueue
큐 상태 변화 (왼쪽이 front, 오른쪽이 rear):
초기
Queue = [A]
Result = []
Step 1) Dequeue A 방문, Enqueue(B), Enqueue(C)
Queue = [B, C]
Result = [A]
Step 2) Dequeue B 방문, Enqueue(D), Enqueue(E)
Queue = [C, D, E]
Result = [A, B]
Step 3) Dequeue C 방문, Enqueue(F)
Queue = [D, E, F]
Result = [A, B, C]
Step 4) Dequeue D 방문
Queue = [E, F]
Result = [A, B, C, D]
Step 5) Dequeue E 방문
Queue = [F]
Result = [A, B, C, D, E]
Step 6) Dequeue F 방문
Queue = []
Result = [A, B, C, D, E, F]
최종 LevelOrder:
A → B → C → D → E → F
LevelOrder 반복형 구현 코드 (큐 사용):
public BCL.IEnumerable<T> LevelOrder()
{
if (_root == null)
{
yield break;
}
BCL.Queue<Node> q = new();
q.Enqueue(_root);
// 큐를 사용해 위에서 아래, 왼쪽에서 오른쪽 순으로 순회
while (q.Count > 0)
{
Node n = q.Dequeue();
yield return n.Key;
if (n.Left != null)
{
q.Enqueue(n.Left);
}
if (n.Right != null)
{
q.Enqueue(n.Right);
}
}
}
4-6. 높이 계산과 성능
트리의 높이는 재귀적으로 계산합니다.
private static int Height(Node n)
{
if (n == null)
{
// 빈 서브 트리의 높이는 -1로 정의
return -1;
}
int lh = Height(n.Left);
int rh = Height(n.Right);
// 더 큰 쪽에 1을 더한 값이 현재 서브 트리의 높이
return (lh > rh ? lh : rh) + 1;
}
BST의 탐색/삽입/삭제 시간은 이 높이에 직접적으로 영향을 받습니다. 따라서 데이터를 어떤 순서로 넣느냐에 따라 성능이 크게 달라질 수 있고, 안정적인 성능이 필요하다면 균형 BST를 사용하는 것이 좋습니다.
5. C# 기반 BST 직접 구현 코드
아래는 Bst<T> 전체 코드입니다. 앞에서 설명한 개념과 흐름이 모두 이 클래스 안에 정리되어 있습니다.
using System;
using System.Collections;
using BCL = System.Collections.Generic; // BCL - Base Class Library
namespace Daebak.Common.Collections
{
/// <summary>
/// Binary Search Tree (BST)
/// - 중복 키: 무시 (Insert 시 false 반환)
/// - 기본 비교: IComparer<T> 또는 Comparer<T>.Default
/// - 순회: InOrder / PreOrder / PostOrder / LevelOrder
/// </summary>
public class Bst<T> : BCL.IEnumerable<T>
{
/// <summary> 트리 내부에서 사용하는 노드 타입 </summary>
private sealed class Node
{
// 노드에 저장된 키
public T Key;
// 왼쪽 자식 노드
public Node Left;
// 오른쪽 자식 노드
public Node Right;
public Node(T key)
{
Key = key;
}
}
// 루트 노드
private Node _root;
// 키 비교용 비교기
private readonly BCL.IComparer<T> _cmp;
/// <summary> 트리에 포함된 노드(키)의 개수 </summary>
public int Count { get; private set; }
/// <summary>
/// BST 인스턴스를 생성합니다. comparer를 지정하지 않으면 Comparer<T>.Default를 사용합니다.
/// </summary>
public Bst(BCL.IComparer<T> comparer = null)
{
_cmp = comparer ?? BCL.Comparer<T>.Default;
}
/// <summary>
/// 키를 삽입합니다. 이미 같은 키가 있으면 false를 반환하고 삽입하지 않습니다.
/// </summary>
public bool Insert(T key)
{
// 트리가 비어 있으면 루트로 삽입
if (_root == null)
{
_root = new Node(key);
Count = 1;
return true;
}
// 루트부터 내려가며 삽입 위치 탐색
Node cur = _root;
while (true)
{
int c = _cmp.Compare(key, cur.Key);
if (c == 0)
{
// 이미 동일한 키가 존재하는 경우 → 삽입하지 않음
return false;
}
else if (c < 0)
{
// 더 작은 키 → 왼쪽 서브 트리로 이동
if (cur.Left == null)
{
// 왼쪽 자리가 비어 있으면 여기 삽입
cur.Left = new Node(key);
++Count;
return true;
}
cur = cur.Left;
}
else
{
// 더 큰 키 → 오른쪽 서브 트리로 이동
if (cur.Right == null)
{
// 오른쪽 자리가 비어 있으면 여기 삽입
cur.Right = new Node(key);
++Count;
return true;
}
cur = cur.Right;
}
}
}
/// <summary>
/// 해당 키가 트리에 존재하는지 여부를 반환합니다.
/// </summary>
public bool Contains(T key)
{
// FindNode 결과가 null인지로 존재 여부 판단
return FindNode(key) != null;
}
/// <summary>
/// 동일한 키가 존재하면 그 키를 out 매개변수로 반환합니다.
/// </summary>
public bool TryFind(T key, out T found)
{
Node n = FindNode(key);
if (n != null)
{
// 트리에 실제 저장된 키를 그대로 돌려줌
found = n.Key;
return true;
}
found = default;
return false;
}
/// <summary>
/// 키를 삭제합니다. 삭제에 성공하면 true를 반환합니다.
/// </summary>
public bool Remove(T key)
{
bool removed;
// 루트부터 시작해 재귀적으로 삭제 수행
_root = RemoveNode(_root, key, out removed);
if (removed)
{
--Count;
}
return removed;
}
/// <summary>
/// 최솟값 키를 반환합니다. 트리가 비어 있으면 InvalidOperationException을 발생시킵니다.
/// </summary>
public T Min()
{
if (_root == null)
{
throw new InvalidOperationException("트리가 비어 있습니다.");
}
// 항상 왼쪽으로만 내려가면 최솟값
return LeftMost(_root).Key;
}
/// <summary>
/// 최댓값 키를 반환합니다. 트리가 비어 있으면 InvalidOperationException을 발생시킵니다.
/// </summary>
public T Max()
{
if (_root == null)
{
throw new InvalidOperationException("트리가 비어 있습니다.");
}
// 항상 오른쪽으로만 내려가면 최댓값
return RightMost(_root).Key;
}
/// <summary>
/// 최솟값 키를 out 매개변수로 반환합니다. 실패하면 false를 반환합니다.
/// </summary>
public bool TryMin(out T min)
{
if (_root == null)
{
min = default;
return false;
}
min = LeftMost(_root).Key;
return true;
}
/// <summary>
/// 최댓값 키를 out 매개변수로 반환합니다. 실패하면 false를 반환합니다.
/// </summary>
public bool TryMax(out T max)
{
if (_root == null)
{
max = default;
return false;
}
max = RightMost(_root).Key;
return true;
}
/// <summary>
/// 트리의 높이를 반환합니다.
/// 빈 트리는 -1, 루트 하나만 있을 때는 0입니다.
/// </summary>
public int Height()
{
return Height(_root);
}
/// <summary>
/// 모든 노드를 제거합니다.
/// </summary>
public void Clear()
{
// 루트 참조만 끊어도 나머지는 GC 대상으로 수거됩니다.
_root = null;
Count = 0;
}
/// <summary>
/// 전위 순회(PreOrder)로 키를 열거합니다.
/// </summary>
public BCL.IEnumerable<T> PreOrder()
{
if (_root == null)
{
yield break;
}
BCL.Stack<Node> st = new();
st.Push(_root);
// 스택을 이용해 재귀 없이 전위 순회
while (st.Count > 0)
{
Node n = st.Pop();
yield return n.Key;
// 스택 특성상 오른쪽을 먼저 push해야 왼쪽이 먼저 처리됩니다.
if (n.Right != null)
{
st.Push(n.Right);
}
if (n.Left != null)
{
st.Push(n.Left);
}
}
}
/// <summary>
/// 중위 순회(InOrder)로 키를 열거합니다. (오름차순)
/// </summary>
public BCL.IEnumerable<T> InOrder()
{
if (_root == null)
{
yield break;
}
BCL.Stack<Node> st = new();
Node cur = _root;
// 재귀 대신 스택을 사용하는 반복 구현
while (cur != null || st.Count > 0)
{
// 왼쪽 끝까지 내려가며 스택에 push
while (cur != null)
{
st.Push(cur);
cur = cur.Left;
}
// 가장 왼쪽 노드부터 처리
cur = st.Pop();
yield return cur.Key;
// 오른쪽 서브 트리로 이동
cur = cur.Right;
}
}
/// <summary>
/// 후위 순회(PostOrder)로 키를 열거합니다.
/// </summary>
public BCL.IEnumerable<T> PostOrder()
{
if (_root == null)
{
yield break;
}
// 스택 2개 생성
BCL.Stack<Node> st1 = new();
BCL.Stack<Node> st2 = new();
st1.Push(_root); // st1에 root 삽입
// st1에서 꺼내 st2에 쌓은 뒤, st2를 역순으로 꺼내면 후위 순회 순서가 됩니다.
while (st1.Count > 0)
{
// st1에서 Pop하고, st2에 Push
Node n = st1.Pop();
st2.Push(n);
// 노드 자식들 st1에 Push
if (n.Left != null)
{
st1.Push(n.Left);
}
if (n.Right != null)
{
st1.Push(n.Right);
}
}
// 왼쪽 → 오른쪽 → 루트 순서로 출력
while (st2.Count > 0)
{
yield return st2.Pop().Key;
}
}
/// <summary>
/// 레벨 순회(너비 우선 탐색, BFS)로 키를 열거합니다.
/// </summary>
public BCL.IEnumerable<T> LevelOrder()
{
if (_root == null)
{
yield break;
}
BCL.Queue<Node> q = new();
q.Enqueue(_root);
// 큐를 사용해 위에서 아래, 왼쪽에서 오른쪽 순으로 순회
while (q.Count > 0)
{
Node n = q.Dequeue();
yield return n.Key;
if (n.Left != null)
{
q.Enqueue(n.Left);
}
if (n.Right != null)
{
q.Enqueue(n.Right);
}
}
}
/// <summary>
/// 기본 열거자는 InOrder(오름차순) 순서를 사용합니다.
/// </summary>
public BCL.IEnumerator<T> GetEnumerator()
{
return InOrder().GetEnumerator();
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
// 키에 해당하는 노드를 찾습니다.
private Node FindNode(T key)
{
Node cur = _root;
// 현재 노드와 비교하면서 왼쪽/오른쪽으로 내려감
while (cur != null)
{
int c = _cmp.Compare(key, cur.Key);
if (c == 0)
{
// 키 일치 → 노드 반환
return cur;
}
else if (c < 0)
{
// 더 작은 키 → 왼쪽으로 이동
cur = cur.Left;
}
else
{
// 더 큰 키 → 오른쪽으로 이동
cur = cur.Right;
}
}
// 찾지 못한 경우
return null;
}
// 주어진 서브 트리에서 가장 왼쪽(최솟값) 노드를 찾습니다.
private static Node LeftMost(Node n)
{
while (n.Left != null)
{
n = n.Left;
}
return n;
}
// 주어진 서브 트리에서 가장 오른쪽(최댓값) 노드를 찾습니다.
private static Node RightMost(Node n)
{
while (n.Right != null)
{
n = n.Right;
}
return n;
}
/// <summary>
/// Hibbard Deletion 로직으로 노드를 삭제합니다.
/// - 자식이 0개 또는 1개일 경우, 해당 자식 노드를 반환하여 부모의 링크를 대체합니다.
/// - 자식이 2개일 경우, 오른쪽 서브 트리의 최솟값(후계자, Successor)으로 현재 노드의 값을 대체한 후,
/// 후계자 노드를 재귀적으로 삭제합니다.
/// </summary>
private Node RemoveNode(Node root, T key, out bool removed)
{
if (root == null)
{
// 더 내려갈 노드가 없으면 삭제 실패
removed = false;
return null;
}
int c = _cmp.Compare(key, root.Key);
if (c < 0)
{
// 삭제 대상 키가 더 작으면 왼쪽 서브 트리에서 삭제 시도
root.Left = RemoveNode(root.Left, key, out removed);
return root;
}
else if (c > 0)
{
// 삭제 대상 키가 더 크면 오른쪽 서브 트리에서 삭제 시도
root.Right = RemoveNode(root.Right, key, out removed);
return root;
}
else
{
// 삭제 대상 노드를 찾은 경우
removed = true;
// 자식이 0개 또는 1개인 경우: 해당 자식을 그대로 올려보냄
if (root.Left == null)
{
return root.Right;
}
if (root.Right == null)
{
return root.Left;
}
// 자식이 2개인 경우:
// 오른쪽 서브 트리에서 최솟값(후계자, successor)을 찾아 현재 노드의 키를 교체
Node s = LeftMost(root.Right);
root.Key = s.Key;
// 후계자 노드를 오른쪽 서브 트리에서 다시 삭제
root.Right = RemoveNode(root.Right, s.Key, out _);
return root;
}
}
// 서브 트리의 높이를 재귀적으로 계산합니다.
private static int Height(Node n)
{
if (n == null)
{
// 빈 서브 트리의 높이는 -1로 정의
return -1;
}
int lh = Height(n.Left);
int rh = Height(n.Right);
// 더 큰 쪽에 1을 더한 값이 현재 서브 트리의 높이
return (lh > rh ? lh : rh) + 1;
}
}
}6. 유니티(Unity) 환경에서 테스트해 보기
아래는 Bst<int>를 Unity에서 테스트하는 예제입니다. 몇 개의 정수를 삽입한 이후, 다양한 순회 결과와 Min/Max, Height, Remove 동작을 확인합니다.
using System.Text;
using UnityEngine;
using Daebak.Common.Collections;
public class Test_Bst : MonoBehaviour
{
void Start()
{
Bst<int> tree = new Bst<int>();
Debug.Log("=== BST 테스트 시작 ===");
// 1) 삽입
int[] values = { 8, 3, 10, 1, 6, 14, 4, 7, 13 };
foreach (int v in values)
{
bool inserted = tree.Insert(v);
Debug.Log($"Insert({v}) = {inserted}");
}
Debug.Log($"Count = {tree.Count}");
Debug.Log($"Height = {tree.Height()}");
// 2) Min / Max
Debug.Log($"Min = {tree.Min()}");
Debug.Log($"Max = {tree.Max()}");
// 3) Contains 테스트
Debug.Log($"Contains(7) = {tree.Contains(7)}");
Debug.Log($"Contains(5) = {tree.Contains(5)}");
// 4) 순회 결과 출력
Debug.Log($"InOrder = {Join(tree.InOrder())}");
Debug.Log($"PreOrder = {Join(tree.PreOrder())}");
Debug.Log($"PostOrder = {Join(tree.PostOrder())}");
Debug.Log($"LevelOrder = {Join(tree.LevelOrder())}");
// 5) 삭제 테스트 (예: 3, 8 삭제)
Debug.Log("=== Remove(3) ===");
Debug.Log($"Remove(3) = {tree.Remove(3)}");
Debug.Log($"InOrder = {Join(tree.InOrder())}");
Debug.Log($"Height = {tree.Height()}");
Debug.Log("=== Remove(8) (루트 삭제) ===");
Debug.Log($"Remove(8) = {tree.Remove(8)}");
Debug.Log($"InOrder = {Join(tree.InOrder())}");
Debug.Log($"Height = {tree.Height()}");
Debug.Log("=== BST 테스트 종료 ===");
}
private string Join(System.Collections.Generic.IEnumerable<int> seq)
{
StringBuilder sb = new StringBuilder();
bool first = true;
foreach (int v in seq)
{
if (!first)
{
sb.Append(", ");
}
sb.Append(v);
first = false;
}
return sb.ToString();
}
}
실행 결과
=== BST 테스트 시작 ===
Insert(8) = True
Insert(3) = True
Insert(10) = True
Insert(1) = True
Insert(6) = True
Insert(14) = True
Insert(4) = True
Insert(7) = True
Insert(13) = True
Count = 9
Height = 3
Min = 1
Max = 14
Contains(7) = True
Contains(5) = False
InOrder = 1, 3, 4, 6, 7, 8, 10, 13, 14
PreOrder = 8, 3, 1, 6, 4, 7, 10, 14, 13
PostOrder = 1, 4, 7, 6, 3, 13, 14, 10, 8
LevelOrder = 8, 3, 10, 1, 6, 14, 4, 7, 13
=== Remove(3) ===
Remove(3) = True
InOrder = 1, 4, 6, 7, 8, 10, 13, 14
Height = 3
=== Remove(8) (루트 삭제) ===
Remove(8) = True
InOrder = 1, 4, 6, 7, 10, 13, 14
Height = 2
=== BST 테스트 종료 ===
이 결과를 통해 다음과 같은 점을 확인할 수 있습니다.
- InOrder 순회 결과는 항상 오름차순으로 정렬되어 있습니다.
- PreOrder, PostOrder, LevelOrder는 같은 트리를 서로 다른 관점에서 방문합니다.
- 자식이 2개인 노드(3, 8)를 삭제해도 BST 성질이 유지됩니다.
- 삭제에 따라 높이(Height)가 감소하는 모습을 통해 트리 구조의 변화를 간접적으로 파악할 수 있습니다.
마무리
이진 탐색 트리(BST)는 정렬 규칙을 가진 이진 트리로, 탐색/삽입/삭제를 평균적으로 O(log n)에 처리할 수 있는 자료구조입니다. 이번 글에서는 BST의 개념과 삽입/삭제/순회 동작을 그림으로 살펴보고, C# 제네릭 기반 Bst<T> 구현과 Unity 테스트 코드까지 함께 정리했습니다.
BST 자체는 실무에서 직접 구현해 쓰기보다는, 균형 트리, 힙, PriorityQueue, SortedDictionary 같은 상위 자료구조를 이해하기 위한 기반 개념으로 활용되는 경우가 많습니다. 하지만 내부 동작을 한 번 직접 구현해 보면:
- 트리/그래프 기반 알고리즘(DFS, BFS, 순회 패턴)에 대한 감각을 키울 수 있고
- 정렬과 검색 성능을 구조적으로 이해하게 되며
- Unity 프로젝트에서 성능과 메모리를 고려한 자료구조 선택을 더 명확하게 할 수 있습니다.
필요하다면 이 코드를 바탕으로 균형 트리, 범위 검색, k번째 원소 조회 등으로 확장해 보시는 것도 좋은 연습이 됩니다.
※ 다음 글에서는 AVL Tree 구조를 살펴보며, BST에서 발생할 수 있는 불균형 문제를 회전(rotation)을 통해 어떻게 자동으로 보정하는지를 중심으로 정리합니다.
'자료 구조' 카테고리의 다른 글
| Unity 개발자를 위한 C# Red-Black Tree(레드 블랙 트리) 구현 (0) | 2025.12.27 |
|---|---|
| Unity 개발자를 위한 C# AVL(자기 균형 이진 탐색 트리) 구현 (0) | 2025.12.24 |
| Unity 개발자를 위한 C# Tree(트리) 구현 (0) | 2025.12.10 |
| Unity 개발자를 위한 Graph(그래프)의 이해 (0) | 2025.12.10 |
| Unity 개발자를 위한 C# PriorityQueue(우선순위 큐) 구현 (0) | 2025.12.10 |
