이진 트리(Binary Tree)는 각 노드가 최대 2개의 자식 노드(왼쪽·오른쪽) 를 갖는 계층적 자료구조다. 계층 구조를 표현하거나 효율적인 탐색·정렬에 사용하며, 이진 탐색 트리(BST), 힙(Heap), AVL 트리 등 다양한 파생 구조의 기반이 된다.
기본 용어
[8] ← 루트(Root)
/ \
[3] [10] ← 내부 노드(Internal Node)
/ \ \
[1] [6] [14]
/ \ /
[4] [7] [13] ← 리프(Leaf): 자식 없음
| 용어 | 설명 |
|---|
| 루트(Root) | 트리의 최상위 노드 |
| 리프(Leaf) | 자식이 없는 노드 |
| 높이(Height) | 루트에서 가장 깊은 리프까지 거리 |
| 깊이(Depth) | 루트에서 특정 노드까지 거리 |
| 부모/자식 | 연결된 상위/하위 노드 |
이진 탐색 트리 (BST)
이진 트리에 탐색 효율을 위한 정렬 조건을 추가한 구조.
- •왼쪽 서브트리: 부모보다 작은 값
- •오른쪽 서브트리: 부모보다 큰 값
탐색: 찾는 값이 8인 루트보다 크면 오른쪽, 작으면 왼쪽
→ O(log n) 평균 (균형 트리 기준)
| 연산 | 평균 | 최악(편향) |
|---|
| 탐색 | O(log n) | O(n) |
| 삽입 | O(log n) | O(n) |
| 삭제 | O(log n) | O(n) |
순회 방법 (Traversal)
트리:
[4]
/ \
[2] [6]
/ \ / \
[1][3][5][7]
| 순회 방식 | 방문 순서 | 결과 | 활용 |
|---|
| 전위(Pre-order) | 루트→왼→오른 | 4,2,1,3,6,5,7 | 트리 복사, 직렬화 |
| 중위(In-order) | 왼→루트→오른 | 1,2,3,4,5,6,7 | BST 정렬 출력 |
| 후위(Post-order) | 왼→오른→루트 | 1,3,2,5,7,6,4 | 트리 삭제, 크기 계산 |
| 레벨(BFS) | 레벨 순서 | 4,2,6,1,3,5,7 | 최단 경로 탐색 |
python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = self.right = None
def inorder(node):
if node is None: return
inorder(node.left) # 왼쪽
print(node.val) # 루트
inorder(node.right) # 오른쪽
이진 트리의 종류
| 종류 | 조건 | 특징 |
|---|
| 이진 탐색 트리(BST) | 좌 < 루트 < 우 | O(log n) 탐색 |
| 완전 이진 트리 | 마지막 레벨 제외 모두 채움 | 힙 구현 기반 |
| 포화 이진 트리 | 모든 리프 동일 깊이, 모두 채움 | 이론적 이상형 |
| 균형 이진 트리(AVL) | 좌우 높이 차 ≤ 1 | 최악도 O(log n) |
| 레드-블랙 트리 | 색깔 조건으로 균형 유지 | Java TreeMap, C++ map |
| 힙(Heap) | 부모 ≥ 자식 (최대 힙) | 우선순위 큐 |
완전 이진 트리와 배열 표현
완전 이진 트리는 배열로 효율적으로 표현 가능하다.
인덱스: 0 1 2 3 4 5 6
배열: [10, 6, 8, 2, 4, 7, 5]
부모(i)의 자식: 왼쪽 = 2i+1, 오른쪽 = 2i+2
자식(i)의 부모: (i-1) // 2
→ 힙 정렬, 우선순위 큐의 기반 구조.
주요 활용
해시 vs 이진 트리
| 항목 | 해시맵 | 이진 탐색 트리 |
|---|
| 탐색 | O(1) 평균 | O(log n) |
| 순서 | ✗ 없음 | ✓ 정렬 순서 유지 |
| 범위 탐색 | ✗ 불가 | ✓ 효율적 |
| 구현 복잡도 | 낮음 | 높음 (균형 유지) |
관련 개념
참고문헌
- •Cormen et al. (2009). Introduction to Algorithms — Chapter 12: Binary Search Trees
- •Sedgewick & Wayne. Algorithms, 4th Edition — Chapter 3
