6.20 Dev.Feedback (Tree 순회)

트리순회

특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것을 트리 순회라고 한다.

트리 구조에서 노드를 순차적으로 조회할 때는 항상 왼쪽부터 시작하여 오른쪽으로 향하게 된다.

1에서 10까지의 정수로 구성된 트리에서 3이라는 숫자를 찾기 위해 모든 노드를 방문하는 경우거 트리 순회의 한 예시이다.

트리 구조는 계층적 구조라는 특별한 특징을 가지고 있는데, 모든 노드를 순회하는 방법엔 크게 세 가지가 있다.

트리를 순회할 수 있는 세 가지 방법은 전위 순회, 중위 순회, 후위 순회이다.

 

전위 순회

 

루트에서 시작해 왼쪽의 노드들을 순차적으로 둘러본 뒤, 왼쪽의 노드 탐색이 끝나면 오른쪽 노드를 탐색한다.

상위 레벨을 먼저 탐색을했다면, 그 상위 레벨을 거치지 않고 바로 우측에 탐색하지 않은 노드로 넘어간다.

 

중위 순회

 

루트를 가운데에 두고 순회한다.

루트부터 시작하지 않고, 제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여, 루트를 기준으로 왼쪽에 있는 노드의 순회가 끝나면 루트를 거쳐 오른쪽에 있는 노드로 이동하여 마저 탐색한다.

 

후위 순회

루트를 가장 마지막에 순회하는 방식. 제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여, 루트를 거치지 않고 오른쪽으로 이동해 순회한 뒤, 제일 마지막에 루트를 방문한다.

BFS / DFS

BFS(Breadth-First Search)

일반적으로, 최단경로를 찾을 때 사용된다.

상위 레벨의 좌측 노드를 먼저 확인하고(Root에 가까운 정점), 결과에 맞지 않으면 하위 레벨의 좌측 노드들을 차례로 탐색한다. 만일 원하는 결과를 얻으면 탐색을 멈추고 빠져나온다.

하지만, 결과를 얻지 못하면 모든 Node를 탐색해야하는 상황이 발생할 수도 있다.

 

 

한국에서 미국으로 가는 최단 경로를 확인할 때 BFS를 쓰면, 위의 이미지와 같은 방식으로 찾게 된다.

 

DFS(Depth-First Search)

일반적으로 (최단 경로를 포함한) 목적지에 도착하는 경로를 찾을 때 사용된다.

DFS는 루트와 연결된 상위 노드의 Leaf노드까지 들어가 탐색을 한다. 깊이 우선 탐색으로 한 정점에서 시작해서 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색할 때 사용한다. BFS보다 탐색 시간은 조금 오래 걸릴지라도 모든 노드를 완전히 탐색할 수 있다는 장점이 있다. 만약, BFS로 탐색을 하게 된다면 제일 첫 번째 경로가 미국행이라도, 다른 모든 경로를 살펴보아야 한다.

 

BFS와 DFS의 장단점은 명확하다. 그렇기에 상황에 따라 선택을 하는 것이 좋다.

 

예를 들면, 그래프가 굉장히 크고 구해야 하는 정보를 빠르게 구해야 한다면, BFS로

반대로 그래프의 규모가 작고, depth가 얕다면, DFS로 확인을 하는 것이 좋다.