🌳
트리
BST 삽입/탐색/삭제·균형
강의 18: 이진 탐색 트리 (Binary Search Tree)
이진 탐색 트리의 핵심 연산을 구현하고 균형이 깨졌을 때의 한계를 이해합니다.
BST이진 탐색 트리
소요 시간
⏱ 약 1시간
난이도
📊 중급
선수 조건
🎯 단원 17
결과물
이진 탐색 트리의 핵심 연산을 구현하고 균형이 깨졌을 때의 한계를 이해합니다.
이 강의에서 배우는 것
- 1BST 속성을 이해하고, 삽입/탐색/삭제를 Python으로 구현할 수 있다.
- 2BST의 중위 순회가 정렬된 결과를 주는 이유를 설명하고, k번째 최솟값을 구할 수 있다.
- 3균형 트리(AVL, Red-Black)의 필요성을 이해하고, BST 검증 함수를 작성할 수 있다.
소개
이진 탐색 트리(BST)는 다음 **BST 속성**을 만족하는 이진 트리입니다:
💡
**왼쪽 서브트리의 모든 노드 < 현재 노드 < 오른쪽 서브트리의 모든 노드**
이 속성 덕분에 삽입/탐색/삭제가 평균 **O(log n)**에 가능합니다. 단, 삽입 순서에 따라 트리가 편향(skewed)되면 최악 **O(n)**까지 저하됩니다.
text
왜 BST인가?
─────────────────────────────────────────────────────────────
연산 정렬 배열 해시맵 BST(균형) BST(최악)
─────────────────────────────────────────────────────────────
탐색 O(log n) O(1) O(log n) O(n)
삽입 O(n) O(1) O(log n) O(n)
삭제 O(n) O(1) O(log n) O(n)
최솟값/최댓값 O(1) O(n) O(log n) O(n)
순서 출력 O(n) O(n log n) O(n) O(n)
범위 쿼리 O(log n+k) O(n) O(log n+k) O(n+k)
─────────────────────────────────────────────────────────────핵심 개념
BST 텍스트 아트
text
8 ← 루트
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
BST 속성 확인:
- 3의 왼쪽(1) < 3 < 3의 오른쪽(6) ✓
- 6의 왼쪽(4) < 6 < 6의 오른쪽(7) ✓
- 중위 순회: 1 3 4 6 7 8 10 13 14 ← 오름차순!삽입 알고리즘
text
insert(root, val):
if root is None:
return TreeNode(val) ← 빈 자리 발견 → 삽입
if val < root.val:
root.left = insert(root.left, val) ← 왼쪽으로
elif val > root.val:
root.right = insert(root.right, val) ← 오른쪽으로
# val == root.val: 중복 무시 (또는 count 증가)
return root삭제 알고리즘 (3가지 경우)
text
경우 1: 리프 노드 → 그냥 제거
8 8
/ \ 삭제 1 / \
3 10 ────────▶ 3 10
/ \ \ / \ \
1 6 14 [X] 6 14
경우 2: 자식 1개 → 자식으로 대체
8 8
/ \ 삭제 10 / \
3 10 ────────▶ 3 14
/ \ \ / \
1 6 14 1 6
경우 3: 자식 2개 → 후계자(in-order successor: 오른쪽 서브트리 최솟값)로 대체
8 9
/ \ 삭제 8 / \
3 10 ────────▶ 3 10
/ \ / \ / \ \
1 6 9 14 1 6 14복잡도 정리
text
┌──────────────┬──────────────┬──────────────┐
│ 연산 │ 평균 │ 최악 (편향) │
├──────────────┼──────────────┼──────────────┤
│ 탐색 │ O(log n) │ O(n) │
│ 삽입 │ O(log n) │ O(n) │
│ 삭제 │ O(log n) │ O(n) │
│ 최솟값 │ O(log n) │ O(n) │
│ 중위 순회 │ O(n) │ O(n) │
└──────────────┴──────────────┴──────────────┘
공간 복잡도: O(n) (트리 저장)AVL 트리 (균형 트리 개념)
균형 인수(Balance Factor) = 왼쪽 높이 - 오른쪽 높이
- |BF| ≤ 1: 균형 상태 (AVL 조건)
- |BF| > 1: 회전(rotation) 필요
Python에서는 `sortedcontainers.SortedList` 또는 표준 라이브러리의 `heapq`/`bisect`로 균형 트리의 효과를 낼 수 있습니다.
예제로 보기
| 파일 | 내용 |
|---|---|
| `src/01_bst_insert_search.py` | BST 삽입, 탐색, 중위 순회 |
| `src/02_bst_delete.py` | BST 삭제 (3가지 경우) |
| `src/03_bst_validate.py` | BST 검증, k번째 최솟값 |
| `src/04_bst_applications.py` | BST 정렬, 범위 쿼리, floor/ceil |
자주 하는 실수
- **중복 처리 미결정**: BST에서 중복 값을 어떻게 처리할지(무시/왼쪽/오른쪽/카운트) 명확히 정하지 않으면 논리 오류 발생
- **삭제 시 후계자 찾기 오류**: 두 자식이 있을 때 후계자는 **오른쪽 서브트리의 최솟값** (가장 왼쪽 노드)임을 기억
- **범위 검증 누락**: BST 검증 시 단순히 `node.left.val < node.val < node.right.val`만 확인하면 틀림 — 상위 경계값도 고려해야 함
- **편향 트리 성능 무시**: 정렬된 배열을 순서대로 삽입하면 O(n) 편향 트리가 됨 — 랜덤 삽입 또는 균형 트리 필요
- **Python 재귀 깊이**: 편향 트리 + 재귀 탐색 시 n > 1000이면 `sys.setrecursionlimit()` 필수
정리
- BST는 **왼쪽 < 현재 < 오른쪽** 속성으로 O(log n) 평균 성능
- **중위 순회 = 정렬된 출력** (BST의 핵심 활용)
- 삭제는 3가지 경우(리프, 자식 1개, 자식 2개) 처리
- 균형 트리(AVL, Red-Black)는 최악도 O(log n) 보장
직접 해 보기
- BST에서 두 노드의 **최소 공통 조상(LCA)** 구하기
- BST를 정렬된 배열로 변환하는 함수 구현
- 두 개의 BST를 합쳐 하나의 정렬된 배열 만들기 (O(m+n))
과제
📂 `homework/README.md` 참조
- 백준 5639 (이진 검색 트리) — Gold V
- 백준 2957 (이진 탐색 트리) — Gold I