트리

---

트리란?

트리는 노드와 에지로 연결된 그래프의 특수한 형태이다.

트리의 특징

• 순환 구조를 지니고 있지 않고, 1개의 루트 노드가 존재한다.
• 루트 노드를 제외한 노드는 단 1개의 부모 노드를 갖는다.
• 트리의 부분 트리 역시 트리의 모든 특징을 따른다.

트리의 구성요소

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

코딩테스트에서 tree 문제 유형

1. 그래프로 푸는 tree -> DFS, BFS 등
2. tree만을 위한 문제 -> 세그먼트 트리(index 트리), LCA(최소공통조상) 등