Tree

그래프의 특수한 형태

• cycle이 없고, 1개의 루트 노드가 있다.
• 루트 노드를 제외한 노드는 1개의 부모 노드를 갖는다.
• 트리의 부분(subtree) 역시 트리의 모든 특징을 따른다.

트리에서 임의의 두 노드를 이어주는 경로는 유일하다.

🔰구성 요소

구성 요소	설명
노드	데이터의 index와 value를 표현하는 요소
엣지	노드와 노드의 연결 관계를 나타내는 선
루트 노드	트리에서 가장 상위에 존재하는 노드
부모 노드	두 노드 사이의 관계에서 상위 노드에 해당하는 노드
자식 노드	두 노드 사이의 관계에서 하위 노드에 해당하는 노드
리프 노드	트리에서 가장 하위에 존재하는 노드(자식 노드가 없음)
서브 트리	전체 트리에 속한 작은 트리

🍎 코딩 테스트에서 트리
1. 그래프로 푸는 트리: 인접 리스트로 표현 -> DFS, BFS 적용
2. 트리만을 위한 문제: 이진트리 / 세그먼트 트리(인덱스 트리) / LCA(최소 공통 조상)
    인접 리스트로 표현하지 않음. 1차원 배열로 트리를 표현