🌳 트리 자료구조 (Tree)
트리는 계층적인 구조를 표현할 수 있는 비선형 자료구조입니다. 디렉토리 구조, 가계도, 게임 트리 등 다양한 곳에 활용됩니다.
트리 기본 개념
- 트리는 노드(node)와 간선(edge)으로 구성됩니다.
- 최상단의 노드를 루트(root) 노드라고 합니다.
- 자식이 없는 노드를 리프(leaf) 노드라고 합니다.
- 서브트리(subtree): 트리 내의 일부 트리 구조
- 트리의 높이(height): 루트에서 가장 깊은 리프 노드까지의 거리
트리 용어 요약
| 용어 | 설명 |
|---|---|
| 루트 노드 | 트리의 시작점 |
| 부모/자식 노드 | 간선으로 연결된 상하 노드 관계 |
| 리프 노드 | 자식이 없는 노드 |
| 서브트리 | 트리의 일부 |
| 레벨 | 루트로부터의 거리 (루트: 0) |
| 높이 | 가장 깊은 노드까지의 레벨 |
트리의 주요 종류
1. 이진 트리 (Binary Tree)
- 모든 노드가 최대 2개의 자식 노드를 가짐
A
/ \
B C
/ \ \
D E F
2. 이진 탐색 트리 (BST)
- 왼쪽 서브트리는 루트보다 작고, 오른쪽 서브트리는 루트보다 큰 값을 가짐
- 검색, 삽입, 삭제가 평균 O(log n)
5
/ \
3 8
/ \ \
2 4 10
3. 완전 이진 트리 (Complete Binary Tree)
- 마지막 레벨을 제외하고는 노드가 모두 채워져 있고, 왼쪽부터 순서대로 채워짐
1
/ \
2 3
/ \
4 5
4. 포화 이진 트리 (Full Binary Tree)
- 모든 내부 노드가 정확히 2개의 자식 노드를 가짐
1
/ \
2 3
/ \ / \
4 5 6 7
5. 균형 이진 트리 (Balanced Binary Tree)
- 트리의 높이가 최소화된 구조 (ex. AVL, Red-Black Tree)
6. 힙 (Heap)
- 완전 이진 트리이며, 부모 노드가 자식보다 크거나 작음
- 최대 힙: 부모 ≥ 자식
- 최소 힙: 부모 ≤ 자식
1
/ \
3 5
/ \
4 8
7. 트라이 (Trie)
- 문자열 검색을 위한 트리 구조
- prefix 검색에 최적화됨
8. N-진 트리 (N-ary Tree)
- 하나의 노드가 N개의 자식을 가질 수 있는 트리
이진 탐색 트리 (BST)의 주요 연산
- 검색(Search): O(log n) (평균), O(n) (최악)
- 삽입(Insert): O(log n)
- 삭제(Delete): 삭제할 노드의 자식 구조에 따라 케이스 나뉨
순회 방식
더 자세한 내용은 👉 트리 순회 정리 글을 참고하세요.
- 전위 순회 (Pre-order)
- 중위 순회 (In-order)
- 후위 순회 (Post-order)
- 레벨 순회 (Level-order)
활용 사례
- 이진 탐색: 정렬된 데이터에서 빠른 검색을 위해 사용
- 힙, 우선순위 큐: 우선순위가 중요한 데이터 처리(예: 작업 스케줄러)
- 자동 완성 / 문자열 검색 (트라이): 접두사 기반 검색에 최적화
- 컴파일러 파싱 트리: 소스코드의 구문 구조를 트리로 표현
- 게임 AI (Minimax Tree): 게임 상태 탐색 및 최적 전략 결정에 사용