7. 트리

트리는 그래프의 special case

N개의 정점에 대해 N-1개의 간선이 주어짐.

child, parent, sibling, depth, leaf, root 등 트리의 terminology가 있음.

 

트리의 특징이라고 하면

사이클이 존재하지 않는다.

N개의 정점에 대해 N-1개의 간선이 있다는 것으로 활용 가능함.

한 노드에서 다른 노드로 가는 최소 경로가 하나로 정해진다.

연결 그래프이다.

 

구현의 경우 인접 리스트 또는 인접 행렬로 한다.

A와 B 간선 존재 여부

	인접행렬	인접리스트
A와 B를 잇는 간선 존재 여부 확인	O(1)	O(min(deg(A), deg(B))
A와 연결된 모든 정점 확인	O(|V|)	O(deg(A))
공간 복잡도	O(|V^2|)	O(|E|)

탐색 방법

 - 2진 트리일 경우 전위, 중위, 후위 순회 등이 있을 수 있다.

 - 그래프의 special case이므로 bfs or dfs로 해결 가능하다

  - 인접리스트를 쓴다면 O(V+E) DFS가 매우 쉽게 구현 가능하다.

재귀에 대한 이해가 있다면 트리는 재귀구조라 쉽게 구현할 수 있다.