트리(Tree) 개념 정리

트리 (Tree) 란 ?

노드들과 노드들을 연결하는 간선, 사이클이 없는 하나의 연결 그래프이다.

노드 Node : 트리를 구성하는 기본 요소
간선 Edge : 노드와 노드 간의 연결선
루트 노드 Root Node : 트리 구조에서 부모가 없는 최상위 노드
부모 노드 Parent Node : 자식 노드를 가진 노드
자식 노드 Child Node : 부모 노드의 하위 노드
형제 노드 Sibling Node : 같은 부모를 가지는 노드
외부 노드 External Node, 단말 노드 Terminal Node, 리프 노드 Leaf Node : 자식 노드가 없는 노드
내부 노드 Internal Node, 비 단말 노드 Non-Terminal Node, 가지 노드 Branch Node : 자식 노드 하나 이상 가진 노드
깊이 Depth : 루트에서 어떤 노드까지의 간선 수
높이 Height : 어떤 노드에서 리프 노드까지 가장 긴 경로의 간선 수
차수 Degree : 노드의 자식 수
크기 Size : 자신을 포함한 자손의 노드 수
Level : 루트에서 어떤 노드까지의 간선 수
Path : 한 노드에서 다른 한 노드에 이르는 길 사이에 놓여있는 노드들의 순서
Path Length : 해당 경로에 있는 총노드의 수
Width : 레벨에 있는 노드 수
Breadth : 리프 노드의 수
Distance : 두 노드 사이의 최단 경로에 있는 간선의 수
Order : 부모 노드가 가질 수 있는 최대 자식의 주

Tree는 그래프의 종류로, 계층 모델입니다.
DAG의 한 종류입니다. DAG란? Directed Acyclic Graphs의 약어로 방향성이 있는 비순환 그래프를 말합니다. DAG는 사이클이 없습니다. 즉, Tree는 사이클이 없다.
간선은 항상 정점의 개수 - 1 만큼 가집니다.
두 개의 정점 사이는 1개의 경로만 가집니다.
부모-자식의 관계를 가지므로 흐름은 top-bottom 또는 bottom-top으로 이루어집니다.