이진 트리 핸드북
주요 개요 및 활용
핸드북 목적 이 문서는 이진 트리(Binary Tree)의 개념적 배경, 구조적 특성, 주요 유형, 연산 방법 및 활용 사례를 통합 정리하여 학습자 및 개발자가 이진 트리를 체계적으로 이해하고 실무에 적용할 수 있도록 돕기 위해 작성되었다.
핸드북 구성
- 이진 트리의 개념과 생성 배경
- 구조 및 주요 용어
- 이진 트리의 유형
- 핵심 속성 및 수식
- 주요 연산(삽입·삭제·탐색·순회)
- 구현 기법과 저장 방식
- 실전 활용 예시
- 참고 및 심화 학습 방향
1. 이진 트리의 개념과 생성 배경
이진 트리는 각 노드가 최대 두 개의 자식(왼쪽·오른쪽)을 갖는 계층적 자료 구조이다.
- 탄생 배경: 탐색·정렬·색인·계산식 파싱 등에서 효율적 데이터 관리 필요성 제기
- 주요 응용:
- 이진 탐색 트리를 통한 O(log n) 탐색
- 힙(Heap) 기반 우선순위 큐
- 표현식 트리로 수식 평가
- 압축 알고리즘(허프만 트리)
2. 구조 및 주요 용어
- 루트(Root): 트리의 최상위 노드
- 내부 노드(Internal Node): 자식이 하나 이상인 노드
- 리프(Leaf): 자식 노드가 없는 말단 노드
- 레벨(Level): 루트가 0, 자식이 한 단계씩 증가
- 높이(Height): 루트에서 가장 먼 리프까지의 레벨 수
- 부모·자식 관계: 상위 노드를 부모, 하위 노드를 자식이라 함
- 서브트리(Subtree): 특정 노드를 루트로 하는 하위 트리
3. 이진 트리의 유형
구조적 특성과 노드 분포 기준으로 구분된다.
| 구분 기준 | 유형 | 설명 |
|---|---|---|
| 자식 수 | 포화 이진 트리(Full) | 모든 노드가 0개 또는 2개 자식 보유 |
| 편향 트리(Skewed) | 모든 내부 노드가 한 방향으로만 자식(왼쪽 또는 오른쪽) | |
| 퇴화 트리(Degenerate) | 마치 단일 연결 리스트처럼 한 자식만 반복 | |
| 레벨 완성도 | 완전 트리(Complete) | 마지막 레벨을 제외한 모든 레벨이 포화, 마지막은 좌측 정렬 |
| 완벽 트리(Perfect) | 모든 내부 노드가 2개 자식, 모든 리프가 동일 레벨 | |
| 거의 완전 트리(Almost Complete) | 완전 트리 정의 완화판 | |
| 균형성 | 균형 트리(Balanced) | 모든 노드에 대해 왼·오 서브트리 높이 차 ≤ 1 |
4. 핵심 속성 및 수식
- 레벨 l의 최대 노드 수:
- 높이 h의 최대 노드 수:
- 높이 h의 최소 노드 수:
- 리프 수와 내부 노드 수 관계:
- 최소 높이: (n = 노드 수)
- 간선 수:
5. 주요 연산
5.1 삽입(Insertion)
- 리프 삽입: 부모 노드의 해당 자식 포인터에 새 노드 연결
- 내부 노드 사이 삽입: 기존 자식 연결을 새 노드로 우선 연결 후, 새 노드가 기존 자식을 자식으로 연결
5.2 삭제(Deletion)
- 자식 0개 or 1개인 노드: 부모 연결만 끊거나 자식과 재연결
- 자식 2개인 노드: 삭제 불가능(→BST 등 특수 규칙에 따라 후속 노드로 대체)
5.3 탐색(Search)
- 이진 탐색 트리: 값 비교를 통해 O(h) 시간(균형 시 O(log n))
5.4 순회(Traversal)
- 전위(Pre-order): 루트→왼쪽→오른쪽
- 중위(In-order): 왼쪽→루트→오른쪽
- 후위(Post-order): 왼쪽→오른쪽→루트
- 레벨 순회(Level-order): 너비 우선 탐색 방식
6. 구현 기법과 저장 방식
6.1 포인터 기반
- 노드 구조체: 데이터, 왼쪽·오른쪽 포인터(선택적 부모 포인터)
- 장점: 직관적, 동적 크기 지원
- 단점: 빈 포인터 메모리 낭비
6.2 배열 기반
- 완전 트리 전용: 인덱스 i의 자식—2·i+1, 2·i+2
- 장점: 메모리 연속성, 캐시 친화적
- 단점: 비완전 트리에는 비효율적
7. 실전 활용 예시
- 이진 탐색 트리(BST): 사전(딕셔너리) 구현, 정렬된 데이터 관리
- 힙(Heap): 우선순위 큐, 힙 정렬
- 허프만 트리: 가변 길이 부호화
- 표현식 트리: 수식 파싱 및 후위 표기법 변환
- 균형 트리(AVL, 레드블랙): 균형 유지로 일관된 탐색 성능
8. 심화 학습 방향
- 셀프-밸런싱 트리: AVL, 레드블랙 트리 알고리즘
- 고급 트리 구조: B-트리, B+트리, 세그먼트 트리, 펜윅 트리
- 메타컴퓨팅 응용: 트라이(trie), 압축 트리, 공간 분할 트리
이 핸드북을 통해 이진 트리의 본질과 구조, 구현 및 활용을 체계적으로 숙지할 수 있으며, 데이터 구조 설계 및 알고리즘 최적화에 유용하게 활용할 수 있다.
⁂