Tree traversal

특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것을 트리 순회라고 한다.
1에서 10까지의 정수로 구성된 트리에서 3아라는 숫자를 찾기 위해 모든 노드를 방문하는 경우는 트리에서 3이라는 숫자를 찾기 위해 모든 노드를 방문하는 경우는 트리 순회의 한 예시이다. 트리 구조는 계층적 구조라는 특별한 특징을 가자기 때문에, 모든 노드를 순회하는 방법엔 크게 세 가지가 있다.

전위 순회

중위 순회

후위 순회

Question

• 이진트리와 BST 이외에 어떠한 트리가 있을까?

• 균형 이진 탐색 트리란 무엇인가?

• Heap이란 무엇 인가?

BFS / DFS

그래프의 탐색은 하나의 정점에서 시작하여 그래프의 모든 정점들을 한 번씩 탐색하는 것이 목적이다. 그래프의 데이터는 배열처럼 정렬 되어 있지 않다. 그래서 원하는 자료를 찾으려면 하나씩 모두 탐색하여 찾아야한다.

정점 탐색 방법에도 여러가지가 있다. 대표적인 두 가지 방법이 BFS, DFS 이다.
이 둘은 데이터를 탐색하는 순서만 다를뿐, 모든 자료를 하나씩 확인해본다는 점은 같다.

BFS / DFS의 특징을 알 수 있는 예시

한국에서 미국으로 가는 비행기를 예약하려고한다. 직항편과 경유편이 있는데, 만약 경유를 하게 되면, 해당 항공사가 필요로 하는 공항에 잠시 머물러야한다.
경유를 하는 시간은 비행편마다 다르고, 경유지도 다르다. 이렇게 다양한 비행기편 중에 최단 경로를 알아내려면 어떻게 해야할까?

BFS

한국을 기준으로 미국까지 가는 방법을 가까운 정점부터 탐색한다. 그리고 더는 탐색할 정점이 없을 때 , 그 다음 떨어져 있는 정점을 순서대로 탐색한다. 직항편이라면, 한국과 미국사이에 어떠한 경유지도 없기 때문에 가장 가까운 정점에 미국이 있다.
만약 경유지가 있다면, 직항보다 거리가 멀다.

• 너비를 우선적으로 탐색하는 방법을 BFS (Breadth-First Search) 너비 우선 탐색 이라고 한다.
• 주로 두 정점 사이의 최단 경로를 찾을 때 사용한다.

• 만약 경로를 하나씩 모두 방문 한다면, 최악의 경우에는 모든 경로를 다 살펴 보아야한다.

그렇다면 , 한국에서 출발하는 항공기의 모든 경로중에 미국에 도착하는 여정을 알아내고 싶을 때에는 어떻게 해야할까?

DFS (Depth- First Search)

비행기 티켓이 없다면 어떤 비행기가 미국으로 가는 것인지 알 도리가 없다. 이때 비행기를 타고 여러 나라를 방문하면서, 마지막으로 미국에 도착하는 경로를 찾아야한다.
DFS는 하나의 경로를 끝까지 탐색한 후 미국 도착이 아니라면 다음 경로로 넘어가 탐색한다. 하나의 노선을 끝까지 들어가서 확인하고 다음으로 넘어가기 때문에, 운이 좋다면 단 몇 번만의 시도로 경로를 찾을 수 있다. 또한 미국으로 가는 길이 아님을 미리 체크 할 수 있다면, 바로 다음 탐색으로 넘어갈 수 있다.

• 깊이를 우선적으로 탐색하는 방법을 DFS ( Depth- First Search)라고 한다.

• 한 정점에서 시작해서 다음 경로로 넘어가기전에 해당 경로를 완벽하게 탐색할 때 사용한다.

• BFS보다 시간은 조금 더 걸리더라도, 모든 노드를 완전히 탐색할 수 있다는 장점이있다.

• 만약 BFS로 탐색을 하게 된다면, 제일 첫번째 경로가 미국행이더라도, 다른 모든 경로를 살펴보아야한다.

DFS와 BFS는 모든 정점을 한 번만 방문 한다는 공통점을 가지고 있지만, 사용할 때의 장단점은 분명하기 때문에 해당 상황에 맞는 탐색 기법을 사용해야 한다.

Question

• DFS와 BFS의 장단점은 또 무엇이 있을까?

• 그래프가 굉장히 크다면, 어떤 탐색 기법을 고려해야 할까?

• 반대로, 규모가 작고 depth가 얕다면 어떤 탐색 기법을 고려해야할까?

추가적으로 공부해볼 것

• Linked-list
• Hash Table