트리 자료구조 핸드북
핵심 요약 트리 자료구조는 계층적 데이터 표현을 위해 고안된 비선형 구조로, 빠른 검색·삽입·삭제를 지원한다. 본 핸드북은 트리의 정의, 구성 요소, 주요 유형, 연산 및 활용법을 3단계 심화 구조로 설명한다.
1. 트리 자료구조의 개요
1.1 설계 배경
트리 자료구조는 파일 시스템, DOM 모델, 계층적 분류 등 실세계의 계층 구조를 컴퓨터 메모리 상에 효율적으로 표현하기 위해 고안되었다1.
1.2 구조적 특징
- 노드(Node): 데이터와 자식 노드를 가리키는 링크(간선)를 포함
- 간선(Edge): 부모-자식 관계를 연결
- 루트(Root): 트리 최상위 노드(부모 없음)
- 내부 노드(Internal Node): 자식이 있는 노드
- 단말 노드(Leaf Node): 자식이 없는 노드
- 차수(Degree): 노드의 자식 수. 트리 전체의 차수는 최대 자식 수1.
1.3 용어 정리
| 용어 | 설명 |
|---|---|
| 깊이(Depth) | 루트에서 해당 노드까지 경로의 간선 수1 |
| 높이(Height) | 해당 노드에서 가장 먼 단말 노드까지 경로의 간선 수1 |
| 레벨(Level) | 루트로부터의 거리 = 깊이1 |
| 크기(Size) | 트리의 총 노드 수1 |
| 서브트리(Subtree) | 어떤 노드를 루트로 하는 부분 트리1 |
2. 주요 트리 유형
트리는 자식 수 제약, 균형 여부 등에 따라 다양하게 분류된다2.
2.1 기본 유형
| 유형 | 제약 | 특징 | 예시 |
|---|---|---|---|
| 이진 트리(Binary Tree) | 최대 2자식 | 구현 단순·순회 쉬움 | 완전 이진 트리, 포화 이진 트리 |
| N-진 트리(N-ary Tree) | 최대 N자식 | 일반적인 계층 구조 표현 | 제네릭 트리 |
| 텀네리 트리(Ternary Tree) | 최대 3자식 | 3방향 탐색 가능 | 텀네리 서치 트리 |
2.2 이진 탐색 트리 변종
| 유형 | 균형 조건 | 특징 |
|---|---|---|
| AVL 트리 | 왼·오른쪽 높이 차 ≤1 | 엄격 균형 유지, 빠른 검색 |
| 레드-블랙 트리 | 루트→단말 경로에 검은색 노드 수 동일 | 완화된 균형, 삽입·삭제 성능 우수 |
| B-트리/B+트리 | 다중 차수 제어 | 디스크 기반 데이터베이스 색인 구조 |
2.3 기타 특수 트리
- 세그먼트 트리: 구간 합·최댓값 질의 최적화
- 펜윅 트리(이진 색인 트리): 누적 합 업데이트 최적화
- 힙(Heap): 완전 이진 트리 기반 우선순위 큐 구성
3. 기본 연산 및 순회
3.1 핵심 연산
- 삽입(Insert): 특정 위치에 노드 추가
- 삭제(Delete): 노드 또는 서브트리 제거
- 검색(Search): 값 또는 키 탐색
- 탐색(Traversal): 모든 노드 방문
3.2 순회 방법
| 순회 | 방식 | 용도 |
|---|---|---|
| 전위 순회(Pre-order) | 부모 → 좌→우 | 트리 복제, 식 표현식 생성 |
| 중위 순회(In-order) | 좌 → 부모 → 우 | 이진 탐색 트리 오름차순 출력 |
| 후위 순회(Post-order) | 좌 → 우 → 부모 | 서브트리 삭제, 후위 표기법 |
| 레벨 순회(Level-order) | 높이별 좌→우 | 최단 경로 탐색, 너비 우선 탐색 |
4. 활용 예시 및 사용법
4.1 파일 시스템
디렉토리와 파일을 트리 노드로 표현, 깊이 우선 탐색으로 전체 탐색 수행1.
4.2 데이터베이스 인덱스
B-트리 계열로 디스크 블록 단위 색인 최적화, 대용량 데이터 검색 가속.
4.3 컴파일러
소스 코드를 **추상 구문 트리(AST)**로 파싱하여 구문 분석 및 최적화 수행.
4.4 네트워크 라우팅
라우팅 테이블을 트리 구조로 표현, 최단 경로 계산에 활용.
5. 결론 및 권장 사항
- 사용처 선정: 계층적 데이터 표현, 범위 질의, 우선순위 큐 등에 적합.
- 균형 유지: 빈번한 삽입·삭제 환경에서는 AVL 또는 레드-블랙 트리 권장.
- 메모리 관리: 동적 할당 시 포인터 오버헤드 고려.
- 순회 활용: 목적에 맞는 순회 방법 선택으로 알고리즘 단순화.
트리 자료구조는 효율적인 계층적 데이터 관리의 핵심이므로, 목적에 맞는 유형과 연산 방식을 숙지하여 최적의 성능을 도출해야 한다.
1 [Tree (abstract data type) - Wikipedia] 2 [Types of Trees in Data Structures - GeeksforGeeks]
⁂