트리

부모-자식 관계를 가지는 특수한 형태의 그래프

트리의 조건

1. 모두가 연결되어 있는 그래프

   • 어떤 두 점을 골라도 간선을 타고 이동 가능
   • 문제에서 keyword가 되는 조건 ex) 모든 두 정점 사이에 이들을 잇는 경로가 존재하며…
     

2. 사이클이 존재하지 않음

   • 대놓고 키워드로 줌

3. 정점 = 간선 + 1 (V = E + 1)

   ex) 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며…

트리 관련 용어

• Node
• Root
• Depth
• Parent, Child, Ancestor, Sibling
• Leaf Node

트리는 무조건 인접 리스트에 저장 (인접 행렬 X)

• 공간 복잡도 (V=10만, E=9.9…)
  • 인접 행렬
    • O(V^2) → 100억
  • 인접 리스트
    • O(E) → 9만9천…

트리에서 탐색

• DFS > BFS