트리(Tree)란?
1. 트리의 정의
- 트리(Tree): 정점(노드)와 간선(링크)으로 구성된, 사이클이 없는 그래프의 한 형태.
- 특징:
- 노드(Node): 데이터를 저장하는 기본 단위.
- 링크(Link): 노드 간의 연결을 나타냄.
- 사이클 없음: 특정 경로를 따라 출발점으로 다시 돌아올 수 없음.
2. 트리 관련 용어 정리
트리의 구조와 특성을 이해하기 위한 주요 용어들:
| 용어 | 설명 |
|---|---|
| 루트 노드 | 트리의 최상단 노드. 트리의 시작점이며, 단 하나만 존재. |
| 단말 노드 | 자식 노드가 없는 노드. 잎 노드(Leaf Node) 또는 터미널 노드(Terminal Node)라고도 함. |
| 비단말 노드 | 자식 노드가 있는 노드. |
| 조상 노드 | 특정 노드까지의 경로에 있는 모든 상위 노드. |
| 자식 노드 | 특정 노드에 연결된 바로 다음 단계의 하위 노드. |
| 형제 노드 | 같은 부모 노드를 공유하는 노드. |
| 부모 노드 | 특정 노드를 바로 위에서 연결하는 상위 노드. |
| 레벨(Level) | 트리의 계층 구조를 나타냄. 루트 노드는 레벨 1로 시작하며, 아래로 내려갈수록 레벨 증가. |
| 깊이(Depth) | 트리의 최대 레벨. 트리의 가장 깊은 노드가 있는 레벨 값. |
| 차수(Degree) | 특정 노드에서 뻗어나간 가지(자식 노드)의 수. |
| 트리의 차수 | 트리 전체에서 가장 높은 차수를 가진 노드의 차수. |
| 서브트리 | 트리의 하위 부분. 특정 노드와 그 자손들로 이루어진 트리. |
| 포레스트(Forest) | 트리에서 루트 노드를 제거하여 생긴 여러 개의 서브트리 집합. |
3. 트리의 특성
- 노드 수와 간선 수:
- 트리의 노드 수 = (N)
- 트리의 간선 수 = (N-1)
- 트리의 순환 없음:
- 특정 노드에서 시작하여 다시 자기 자신으로 돌아올 수 없음.
- 트리의 계층 구조:
- 루트 노드에서 시작하여 아래로 레벨별로 확장.
4. 트리의 유형
- 이진 트리 (Binary Tree):
- 각 노드가 최대 두 개의 자식 노드를 가짐.
- 왼쪽 자식, 오른쪽 자식으로 구분.
- 완전 이진 트리 (Complete Binary Tree):
- 모든 레벨이 꽉 차 있으며, 마지막 레벨의 노드들은 왼쪽부터 채워짐.
- 포화 이진 트리 (Full Binary Tree):
- 모든 노드가 두 개의 자식 노드를 가지거나, 자식이 없는 단말 노드인 트리.
- 균형 이진 트리 (Balanced Binary Tree):
- 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하인 트리.
- N진 트리 (N-ary Tree):
- 각 노드가 최대 (N)개의 자식 노드를 가질 수 있는 트리.
5. 트리 관련 연산
트리 구조에서 자주 수행되는 연산들:
| 연산 | 설명 |
|---|---|
| 삽입 | 트리에 새로운 노드를 추가. |
| 삭제 | 특정 노드를 트리에서 제거하며, 자식 노드들의 처리를 결정. |
| 탐색 | 특정 데이터를 가진 노드를 찾기 위해 트리를 순회. |
| 순회 | 트리의 모든 노드를 방문하는 과정. |
| 트리 순회 유형 | - 전위 순회 (Preorder): 루트 → 왼쪽 서브트리 → 오른쪽 서브트리 - 중위 순회 (Inorder): 왼쪽 서브트리 → 루트 → 오른쪽 서브트리 - 후위 순회 (Postorder): 왼쪽 서브트리 → 오른쪽 서브트리 → 루트 |
6. 트리의 활용 예
트리는 다양한 분야에서 활용됩니다.
아래는 트리 구조가 사용되는 대표적인 사례들:
| 활용 분야 | 설명 |
|---|---|
| 디렉토리 구조 | 운영 체제의 파일 및 폴더 구조를 표현. |
| HTML 구조 | HTML 문서의 DOM(Document Object Model)을 트리로 표현. |
| 이진 탐색 트리 | 데이터의 빠른 검색, 삽입, 삭제를 지원. |
| 네트워크 라우팅 | 라우팅 경로 탐색 및 구성. |
| 게임 개발 | 게임 상태와 결정 트리. |
7. 요약
- 트리는 사이클이 없는 계층적 그래프의 특수 형태.
- 트리의 핵심은 노드 간의 관계와 레벨 기반 구조.
- 주요 용어(루트, 단말 노드, 차수 등)를 반드시 숙지.
- 트리는 디렉토리 구조, 탐색 알고리즘, 네트워크 등 다양한 실무에서 활용됨.
8. 다음 학습 방향
- 트리의 순회 방법(전위, 중위, 후위 순회) 자세히 학습.
- 이진 탐색 트리와 균형 트리의 구현 및 응용 이해.
Hello world