Quick Comparison
| 연산 | 균형에 가까울 때 | 한쪽으로 치우칠 때 |
|---|---|---|
| 탐색 | O(log n) | O(n) |
| 삽입 | O(log n) | O(n) |
| 삭제 | O(log n) | O(n) |
| 중위 순회 | O(n) | O(n) |
왼쪽 서브트리 값 < 현재 값 < 오른쪽 서브트리 값직접 만든 BST는 균형을 잡지 않으면 정렬된 입력에서 연결 리스트처럼 무너집니다. 포함 검사만 빠르게 할 때는 해시, 정렬 순회나 범위 질의가 필요할 때는 균형 트리 계열을 먼저 비교합니다.
구조
이진 탐색 트리, BST는 각 노드가 정렬 규칙을 갖는 이진 트리입니다. 현재 값보다 작으면 왼쪽, 크면 오른쪽으로 내려갑니다.
sealed class Node
{
public int Value;
public Node? Left;
public Node? Right;
public Node(int value) => Value = value;
}
static bool Contains(Node? node, int target)
{
while (node != null)
{
if (target == node.Value) return true;
node = target < node.Value ? node.Left : node.Right;
}
return false;
}이 구조가 빠른 이유는 매 단계에서 탐색 후보를 한쪽 서브트리로 줄일 수 있기 때문입니다. 하지만 이 장점은 트리 높이가 낮을 때만 유지됩니다.
삽입과 삭제 정책
중복 값은 하나의 정책으로 고정해야 합니다. 아래 삽입은 중복을 허용하지 않고, 같은 값이면 아무것도 바꾸지 않습니다. 중복을 세려면 노드에 Count를 두거나, 항상 한쪽에 넣는 규칙을 탐색·삭제까지 일관되게 적용해야 합니다.
static Node Insert(Node? root, int value)
{
if (root == null) return new Node(value);
Node current = root;
while (true)
{
if (value == current.Value) return root;
if (value < current.Value)
{
if (current.Left == null)
{
current.Left = new Node(value);
return root;
}
current = current.Left;
}
else
{
if (current.Right == null)
{
current.Right = new Node(value);
return root;
}
current = current.Right;
}
}
}삭제할 노드는 자식이 없으면 제거하고, 자식이 하나면 그 자식으로 연결을 바꿉니다. 자식이 둘이면 오른쪽 서브트리의 최솟값(중위 후속자) 또는 왼쪽 서브트리의 최댓값으로 값을 바꾼 뒤, 그 노드를 다시 삭제합니다. 이 세 경우를 나누지 않으면 서브트리를 잃기 쉽습니다.
static Node? Remove(Node? root, int value)
{
if (root == null) return null;
if (value < root.Value)
{
root.Left = Remove(root.Left, value);
return root;
}
if (value > root.Value)
{
root.Right = Remove(root.Right, value);
return root;
}
if (root.Left == null) return root.Right;
if (root.Right == null) return root.Left;
Node successor = root.Right;
while (successor.Left != null) successor = successor.Left;
root.Value = successor.Value;
root.Right = Remove(root.Right, successor.Value);
return root;
}편향 트리
정렬된 값을 그대로 삽입하면 트리가 한쪽으로 길어질 수 있습니다.
1
\
2
\
3
\
4이 경우 BST는 사실상 연결 리스트처럼 동작해서 탐색이 O(n)이 됩니다. 그래서 실무 라이브러리는 균형 트리나 해시 테이블을 제공하고, 코테에서는 문제 조건에 따라 직접 구현 여부를 판단합니다.
언제 쓰나
| 상황 | 판단 |
|---|---|
| 정렬된 순회가 필요 | BST 중위 순회 가능 |
| 빠른 포함 검사만 필요 | 해시가 더 단순할 수 있음 |
| 범위 질의가 필요 | 균형 트리 계열 검토 |
| 입력이 정렬되어 들어옴 | 직접 BST는 위험 |
| 문제에서 노드 구조가 주어짐 | BST 성질 활용 |
C# 코테에서는 직접 BST를 구현하기보다 SortedSet<T>, SortedDictionary<TKey,TValue> 같은 정렬된 컬렉션을 검토하는 경우가 많습니다. SortedSet<T>은 중복을 저장하지 않고, SortedDictionary<TKey,TValue>는 키 기준으로 정렬된 키·값을 유지합니다. 값의 정렬 기준을 바꾸는 mutable key를 넣으면 순서와 검색 결과가 깨질 수 있습니다.
주의할 점
BST의 평균 O(log n)을 무조건 믿으면 안 됩니다. 균형을 잡지 않는 직접 구현 BST는 입력 순서에 따라 O(n)으로 무너질 수 있습니다.
또 중복 값을 왼쪽에 둘지, 오른쪽에 둘지, 카운트로 합칠지 정책을 정하지 않으면 삽입과 탐색 결과가 흔들립니다.
참고 링크
2 sources