트리와 그래프
트리는 노드들이 연결된 비선형 자료구조로, 부모-자식 관계를 가진다. 트리의 최상위 노드를 루트(Root)라 부르며, 그 아래 자식 노드들이 구성된다. 트리는 계층적 구조를 가지고 있어, 조직도나 파일시스템 등에 활용된다.
예제코드
class TreeNode {
int value;
TreeNode left;
TreeNode right;
TreeNode(int value) {
this.value = value;
left = null;
right = null;
}
}
그래프는 노드(Node)라 불리는 개체들이 간선(Edge)으로 연결된 구조이다. 그래프는 방향성이 있을 수도 있고(유향 그래프), 없을 수도 있다(무향 그래프). 주로 네트워크 구조를 나타내는 데 사용된다.
예제코드
import java.util.*;
class Graph {
private Map<String, List<String>> adjList = new HashMap<>();
public void addEdge(String v, String w) {
adjList.computeIfAbsent(v, x -> new ArrayList<>()).add(w);
adjList.computeIfAbsent(w, x -> new ArrayList<>()).add(v);
}
}
트리 순회 방법
트리 순회 방법으로는 전위, 중위, 후위 순회가 있다:
전위 순회(Pre-Order Traversal): 루트 노드를 먼저 방문하고, 왼쪽, 오른쪽 서브트리를 순서대로 방문한다.
public void preOrder(TreeNode node) {
if (node != null) {
System.out.print(node.value + " ");
preOrder(node.left);
preOrder(node.right);
}
}
중위 순회(In-Order Traversal): 왼쪽 서브트리, 루트 노드, 오른쪽 서브트리 순으로 방문한다.
public void inOrder(TreeNode node) {
if (node != null) {
inOrder(node.left);
System.out.print(node.value + " ");
inOrder(node.right);
}
}
후위 순회(Post-Order Traversal): 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순으로 방문한다.
public void postOrder(TreeNode node) {
if (node != null) {
postOrder(node.left);
postOrder(node.right);
System.out.print(node.value + " ");
}
}
그래프와 트리의 차이
그래프와 트리는 비선형 자료구조로서 몇 가지 중요한 차이점이 있다:
-
사이클: 트리는 사이클이 없지만, 그래프는 사이클을 가질 수 있다.
-
루트 노드: 트리는 하나의 루트 노드를 가지지만, 그래프에는 루트 노드 개념이 없다.
-
방향성: 트리는 부모에서 자식으로의 단방향 연결을 가지지만, 그래프는 방향성이 있을 수도, 없을 수도 있다.
-
사용 용도: 트리는 계층적인 데이터를 표현하거나 정렬된 데이터를 저장하는 데 사용되며, 그래프는 네트워크 모델링, 경로 탐색 등에 사용된다.
예시
트리와 그래프의 예시는 다음과 같다:
-
트리: 파일 시스템, HTML DOM, 데이터베이스 관리
-
그래프: 소셜 네트워크, 웹 페이지의 하이퍼링크, 지리적 지도
트리 순회 방법은 이진 검색 트리에서 중위 순회를 이용해 오름차순으로 노드를 출력하거나, 컴파일러에서 구문 트리를 후위 순회하여 후위 표기법을 생성하는 데 사용된다.
그래프의 유향성과 무향성은 그래프가 표현하려는 데이터의 관계에 따라 결정된다. 유향 그래프는 방향성이 있는 관계를, 무향 그래프는 방향성이 없는 관계를 표현한다.
트리와 그래프의 구현 방법
트리는 노드와 링크를 이용해 구현되며, 각 노드는 데이터와 자식 노드에 대한 참조를 가진다.
그래프는 인접 리스트나 인접 행렬을 이용해 구현된다.
트리와 그래프에서의 검색 알고리즘도 다르다:
트리에서는 깊이 우선 탐색(DFS)이나 너비 우선 탐색(BFS) 같은 방법을 사용한다.
그래프에서도 DFS와 BFS를 사용할 수 있으나, 사이클이 존재할 수 있으므로 탐색 시 이미 방문한 노드를 체크하는 추가 과정이 필요하다.
트리의 '깊이(Depth)'와 '너비(Width)'는 트리의 구조를 설명하는 데 사용되는 용어이다:
- 깊이(Depth): 루트 노드로부터 특정 노드까지의 경로 길이이다.
- 너비(Width): 가장 많은 노드를 가진 레벨의 노드 수이다.
DFS와 BFS의 차이점
DFS는 주어진 트리나 그래프를 가장 깊게 탐색하는 방법이다.
public void dfs(String start, Set<String> visited) {
visited.add(start);
System.out.print(start + " ");
for (String node : adjList.get(start)) {
if (!visited.contains(node)) {
dfs(node, visited);
}
}
}
BFS는 주어진 트리나 그래프를 가장 넓게 탐색하는 방법이다.
public void bfs(String start) {
Set<String> visited = new HashSet<>();
Queue<String> queue = new LinkedList<>();
queue.add(start);
visited.add(start);
while (!queue.isEmpty()) {
String vertex = queue.poll();
System.out.print(vertex + " ");
for (String node : adjList.get(vertex)) {
if (!visited.contains(node)) {
visited.add(node);
queue.add(node);
}
}
}
}
트리의 깊이와 너비에 따른 효율적인 순회 방법은 순회의 결과가 필요로 하는 순서에 따라 달라진다. DFS와 BFS 중 선택은 트리의 구조와 탐색 목표에 따라 결정된다.
결론?
트리와 그래프는 각각 고유한 특성과 사용 사례를 가지며, 복잡한 문제를 해결하는 데 필수적인 자료구조이다. 이들을 이해하고 올바르게 활용하는 것은 프로그래밍 및 데이터 구조 설계에서 중요한 역량이다. 또한, 트리와 그래프의 탐색 방법은 다양한 알고리즘 문제 해결에 핵심적인 요소이며, 이들의 차이점을 이해하는 것은 효율적인 솔루션 개발에 기여한다.
