트리

컴퓨터 과학에서 트리란 사이클이 없는 그래프를 말한다.

트리를 구성하는 요소에는 크게 두 가지가 있다.

첫 번째는 Node이고, 두 번째는 edge이다.

동그라미하고 선이라고 보면 참 편하다.

트리의 종류에는 또 크게 두 가지가 있는데, directed와 undirected 그래프가 있다.

이는 방향성이 있는 그래프와 방향성이 없는 그래프를 뜻한다.

방향성이 있다는 것은, 편도라는 것이고 방향성이 없다는 것은 왕복이라는 것이다.

생각해보면 참 편한 자료구조이다.

구현에는 두 가지 방식이 있는데 배열로 무식하게 때려박는 방식과 벡터를 사용하는 방식이 있다.

배열로 무식하게 때려박는 방식

 int tree[N][N]
 tree[1][2] = 1;

해당 코드의 둘째 줄은 1번 노드에서 2번 노드로 가는 편도 길이 존재한다는 것을 의미한다.

벡터로 스마트하게 박는 방식 이 방식은 공간을 아낄 수 있다. 위의 배열 방식은 무조건 (자료 사이즈)*N^2 바이트의 공간을 요구한다.

 vector<int> tree[N];
 tree[1].push_back(2);

해당 코드의 둘째 줄 또한 마찬가지로 1에서 2로 가는 편도 길이 존재한다는 것을 의미한다.