트리(Tree)
정점(Node)과 선분(Branch)으로 구성된 비선형 계층적 자료 구조
사이클이 없는 그래프의 한 형태
- 부모-자식 관계로 연결된 계층 구조를 나타냄
- 노드(Node) : 데이터를 저장하는 기본 단위
- 링크(Link) : 노드 간의 연결 관계
- 하나의 루트(Root) 노드 존재
- 모든 노드는 서로 연결되어 있으며, 사이클이 없음
- 계층적 구조를 가짐
트리 관련 주요 용어
트리
- 노드(Node)
- 트리의 기본 구성 요소
- 데이터 + 연결 정보를 포함
- 루트 노드(Root Node)
- 디그리(Degree, 차수)
- 한 노드에서 뻗어나오는 가지(자식 노드)의 수
- A=3, C=1
- 단말 노드(Terminal Node, Leaf Node)
- 자식이 없는 노드
- Degree = 0
- K, L, F, G, M, I, J
- 비단말 노드(Non-Terminal Node)
- 자식이 하나 이상 있는 노드
- Degree ≥ 1
- A, B, C, D, E, H
- 조상 노드(Ancestors Node)
- 특정 노드에서 루트까지의 경로 상에 있는 모든 노드
- L의 조상 노드는 E, B, A
- 부모 노드(Parent Node)
- 바로 상위 레벨에 있는 노드
- H, I, J의 부모 노드는 D
- 자식 노드(Son Node)
- 특정 노드의 하위 레벨에 있는 노드들
- B의 자식 노드는 E, F
- 형제 노드(Sibling)
- 같은 부모를 공유하는 노드들
- H의 형제 노드는 I, J
- 레벨(Level)
- 루트의 레벨을 1로 하며, 아래로 갈수록 +1씩 증가
- 깊이(Depth, Height)
- 트리 내에서 노드가 가질 수 있는 가장 큰 레벨 값
- 현재 트리 깊이는 4
- 숲(Forest)
- 트리의 디그리
- 모든 노드의 차수 중 가장 큰 값
- 노드 A나 D가 세 개의 디그리를 가지므로 위 트리의 디그리는 3
