CS 백엔드/자료구조
[자료구조] 그래프(Graph) 와 트리(Tree)
츄르릅
2023. 2. 17. 01:56
위 그림을 보면 트리는 그래프에 종속되어 있는 것을 알 수 있다.
즉, 그래프는 트리의 기능을 구사할 수 있다는 말이 된다.
1. 그래프 (Graph)
그래프란 무엇일까?
노드(하나의 점)와 간선으로 이루어진 자료구조이다.
위 말을 쉽게 풀어보면, 노드와 노드 간을 연결하는 간선으로 구성된 자료구조라는 말로 볼 수 있다.
이러한 그래프에는 어떤 특징이 있을까?
- 그래프는 순환 또는 비순환 구조를 가질 수 있다.
- 방향을 가질 수도 있고 가지지 않을 수도 있다.
- 부모와 자식 관계가 없고 모든 노드가 평등하다.
- 무방향과 양방향이 가능하다.
2. 트리 (Tree)
트리란 무엇일까?
트리는 그래프 중 하나로 그래프 구조의 특징처럼 노드와 간선으로 이루어진 자료구조이다.
하지만 트리는, 두 개의 노드 사이에 반드시 1개의 경로만을 가지며 순환의 특징을 가지지 않는 방향 그래프이다.
또한, 부모와 자식 관계가 성립되기 때문에 계층적인 구조를 가지고 있다.
트리의 특징은 무엇일까?
- 부모 - 자식 관계가 존재해 레벨이 존재한다. (Root - Parent - Child Node)
- 방향성은 존재하지만 비순환 구조를 가진다.
- 트리의 순회는 전위 순회, 중위 순회, 후위 순회 3가지가 존재한다.
[참고]