자료구조
Search Algorithm
Tree traversal
특정 목적을 위해 트리의 모든 노드를 방문하는 것을 트리 순회라고 한다.
트리 구조는 계층적 구조라는 특별한 특징을 가져, 모든 노드를 순회하는 방법으로는 크게 3가지가 있다.
우선, 이진트리를 순회하는 방법으로는 전위 순회, 중위 순회, 후위 순회가 있다.
루트와 왼쪽의 서브 트리, 오른쪽 서브 트리 중 루트를 언제 방문하느냐에 따라 구분된다.
여기서 루트를 방문하는 작업은 V, 왼쪽 서브 트리 방문은 L, 오른쪽 서브 트리 방문은 R이다.
이 순회 방식과는 논외로, 트리 구조에서 노드를 순차적으로 조회할 때 순서는 항상 왼쪽 → 오른쪽이다.
1. 전위 순회
루트 노드 → 왼쪽 서브 트리 → 오른쪽 서브 트리 순으로 방문한다.
2. 중위 순회
왼쪽 서브 트리 → 루트 노드 → 오른쪽 서브 트리 순으로 방문한다.
3. 후위 순회
왼쪽 서브 트리 → 오른쪽 서브 트리 → 루트 노드 순으로 방문한다.
BFS / DFS
그래프 탐색은 하나의 정점에서 시작해 모든 정점들을 방문(탐색)하는 것이 목적이다.
그래프의 데이터는 배열처럼 정렬되어 있지 않아, 원하는 자료를 찾기 위해선 하나씩 방문하여 찾아야 한다.
BFS
BFS(Breadth-First Search, 너비 우선 탐색)는 너비를 우선적으로 탐색하는 방법이다.
가까운 정점부터 탐색하고, 더 이상 탐색할 정점이 없을 때 떨어져 있는 다음 정점을 순서대로 방문한다.
주로 최단 경로를 찾을 때 사용한다.
DFS
DFS(Depth-First Search, 깊이 우선 탐색)는 하나의 경로를 끝까지 탐색한 후, 도착지점이 아니면 다음 경로로 넘어가 탐색한다.
한 정점에서 시작해 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색할 때 사용한다.
BFS보다 탐색 시간은 오래 걸리지만, 모든 노드를 완전히 탐색할 수 있다.
BFS vs DFS
참고자료
[Java] 트리 Tree 2 - 이진 트리의 순회(전위, 중위, 후위, 반복, 레벨) / 구현
[알고리즘] 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS)
[Java] DFS, BFS 정리
BFS는 낯설어서
이미지 출처
