신창수 교수님의 유튜브 강의를 보고 캡쳐하여 작성하였다.
트리(=최소 연결 트리)
- 트리는 노드로 이루어진 자료 구조 (비선형 자료구조)
- 계층 모델 이다.
- 하나의 루트 노드를 갖음
- 트리에는 사이클 존재 X
- 그래프의 한 종류 (acyclic 특징, DAG(Directed Acyclic Graph)의 한 종류이다.)
- 루트에서 어떤 노드로 가는 경로는 유일
트리의 구조
- 루트 노드(root node): 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다.
- 단말 노드(leaf node): 자식이 없는 노드(=잎 노드)
- 간선(edge): 노드 사이를 연결하는 선 (=link, branch)
- 노드의 레벨(level): 트리의 특정 깊이를 갖는 노드의 집합
- 노드의 깊이(depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 할 간선 수
- 트리의 높이(height): 루트 노드에서 가장 깊숙히 있는 노드의 깊이(depth)
- 트리의 표현법은 3가지
Reference
https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html
공부방