핵심 정리
| 연산 | 균형에 가까울 때 | 한쪽으로 치우칠 때 |
|---|---|---|
| 탐색 | O(log n) | O(n) |
| 삽입 | O(log n) | O(n) |
| 삭제 | O(log n) | O(n) |
| 중위 순회 | O(n) | O(n) |
text
왼쪽 서브트리 값 < 현재 값 < 오른쪽 서브트리 값구조
이진 탐색 트리, BST는 각 노드가 정렬 규칙을 갖는 이진 트리입니다. 현재 값보다 작으면 왼쪽, 크면 오른쪽으로 내려갑니다.
csharp
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;
}이 구조가 빠른 이유는 매 단계에서 탐색 후보를 한쪽 서브트리로 줄일 수 있기 때문입니다. 하지만 이 장점은 트리 높이가 낮을 때만 유지됩니다.
편향 트리
정렬된 값을 그대로 삽입하면 트리가 한쪽으로 길어질 수 있습니다.
text
1
\
2
\
3
\
4이 경우 BST는 사실상 연결 리스트처럼 동작해서 탐색이 O(n)이 됩니다. 그래서 실무 라이브러리는 균형 트리나 해시 테이블을 제공하고, 코테에서는 문제 조건에 따라 직접 구현 여부를 판단합니다.
언제 쓰나
| 상황 | 판단 |
|---|---|
| 정렬된 순회가 필요 | BST 중위 순회 가능 |
| 빠른 포함 검사만 필요 | 해시가 더 단순할 수 있음 |
| 범위 질의가 필요 | 균형 트리 계열 검토 |
| 입력이 정렬되어 들어옴 | 직접 BST는 위험 |
| 문제에서 노드 구조가 주어짐 | BST 성질 활용 |
C# 코테에서는 직접 BST를 구현하기보다 SortedSet<T>, SortedDictionary<TKey,TValue> 같은 정렬된 컬렉션을 검토하는 경우가 많습니다. 단, 플랫폼과 런타임 버전에 따라 사용 가능 API는 확인해야 합니다.
주의할 점
BST의 평균 O(log n)을 무조건 믿으면 안 됩니다. 균형을 잡지 않는 직접 구현 BST는 입력 순서에 따라 O(n)으로 무너질 수 있습니다.
또 중복 값을 왼쪽에 둘지, 오른쪽에 둘지, 카운트로 합칠지 정책을 정하지 않으면 삽입과 탐색 결과가 흔들립니다.