트리(Tree)

트리(Tree) : 트리는 Nodes와 Branches로 이루어져 있다.

- 노드와 링크로 구성된 자료구조 (그래프의 일종, Cycle 없음)

- 계층적 구조를 나타낼 때 사용

    - 폴더 구조(디렉토리, 서브 디렉토리)

    - 조직도, 가계도, ...

 

Tree 예시

 

트리의 구성 요소

- 노드(Node) : 트리 구조의 자료 값을 담고 있는 단위

- 에지(Edge) : 노드 간의 연결선 (=link, branch)

- 루트 노드(Root) : 부모가 없는 노드, 가장 위의 노드

- 잎새 노드(Leaf) : 자식이 없는 노드 (=단말)

- 내부 노드(Internal) : 잎새 노드를 제외한 모든 노드

- 부모(Parent) : 연결된 두 노드 중 상위의 노드

- 자식(Child) : 연결된 두 노드 중 하위의 노드

- 형제(Sibling) : 같은 부모를 가지는 노드

- 깊이(Depth) : 루트에서 어떤 노드까지의 간선의 수

- 레벨(Level) : 트리의 특정 깊이를 가지는 노드 집합

- 높이(Height) : 트리에서 가장 큰 레벨 값

- 크리(Size) : 자신을 포함한 자식 노드의 개수

- 차수(Degree) : 각 노드가 지닌 가지의 수

- 트리의 차수 : 트리의 최대 차수

 

 

트리의 특징

- 하나의 노드에서 다른 노드로 이동하는 경로는 유일

- 노드가 N개인 트리의 Edge의 수는 N-1개

- Acyclic (Cycle이 존재하지 않음)

- 모든 노드는 서로 연결되어 있음

- 하나의 Edge를 끊으면 2개의 Sub-Tree로 분리됨

 

 

 

 

 

 

References

- Chapter 6. Introduction to Trees, Data Structures: A Pseudocode Approach with C, Second Edition, Richard F. Gilberg Behrouz A. Forouzan.