트리(Tree)

트리란 ? 

1. 모두가 연결되어 있는 그래프
   -> 어떤 두 점을 골라도 간선을 타고 사이를 이동 가능
2. 사이클이 존재하지 않음
3. 정점 개수 V = 간선 개수 E + 1

위의 조건 중 2개 이상을 만족해야 한다.

알고리즘 문제를 풀게 되면 Rooted Tree가 대부분이다.

Rooted Tree?

1. Node -> 정점
2. Root -> 최상단에 있는 정점
3. Depth -> 상대적 값이다. Root depth == 0 (1부터 시작해도 무관하다.)
4. Parent, Child, Ancestor, Sibling
   - Parent : 현재 위치 노드와 연결되어 있으며 바로 한단계 위의 노드
   - Child : 현재 위치 노드와 연결되어 있으며 바로 한단계 아래의 노드
   - Ancestor : 자신의 루트 노트 사이의 관계
   - Sibling : 같은 부모 노드를 가지는 관계
5. Leaf Node : 단말 노드라 불리며 자식이 없는 노드

문제의 Keyword

• 모든 두 정점 사이에 이들을 잇는 경로 존재 한다는 구문이 있을 때
• 마을과 마을 사이를 직접 있는 N-1개의 길이 있고, 모든 마을은 연결되어 있다.
• 일반적인 그래프가 아니라 트리라고 언급하는 경우
• 위의 예시를 본다면 문제 접근 방식이 트리라는 것을 알 수 있다.