JS - Tree&Graph Search

1. 트리 순회

1. 어떠한 특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것을 트리 순회라고 한다.
2. 방법은 세 가지가 있으며 전위 순회, 중위 순회, 후위 순회 라고 부른다.
3. 전, 중 , 후의 기준은 루트로, 루트를 어디에 두느냐에 따라서 순회 방식이 달라진다.

 

** 전위 순회 **

• 전위는 제일 처음 루트를 방문하고, 루트를 기준으로 왼쪽의 노드들을 전부 둘러본 뒤, 오른쪽 노드로 탐색을 한다.

 

** 중위 순회 **

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

 

** 후위 순회 **

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

-----------------------------------------------------------------------------------

2. 트리의 종류

 

## 밸런스 ( Balance ) ##

1. Balanced : left, right 노드의 갯수가 정확하게 일치해야 할 필요는 없다, unbalanced 처럼 지나치게 한쪽으로 치우치지 않았다면 balanced tree 이다. ( 예시 : Red-Black Tree, AVL Tree )
2. UnBalanced : 한쪽으로 지나치게 치우친 Tree

 

## 완전 이진 트리 ( Complete Binary Tree ) ##

• 마지막 레벨을 제외한 모든 서브트리의 레벨이 같아야 하고, 마지막 레벨은 왼쪽부터 채워져 있어야 한다.

 

## 정 이진 트리 ( Full Binary Tree ) ##

• 자식 노드가 아예 없거나, 최대 둘뿐인 Tree, 자식을 하나만 가진 노드가 없어야 한다.

 

## 포화 이진 트리 ( Perfect Binary Tree ) ##

• 자식이 아예 없거나 2 개씩만 갖는 '정 이진 트리'와 달리, '포화 이진 트리'는 완벽한 피라미드 형태로, 빈공간 없이 모든 노드가 2 개의 자식을 갖고 있는 트리이다.

Q. 포화 이진 트리의 레벨의 갯수가 n 이라면, 해당 트리의 노드의 갯수는 ?
A. 2^n - 1 로 계산할 수 있다.

-----------------------------------------------------------------------------------

3. 그래프의 탐색

1. 그래프의 탐색은 하나의 정점을 시작으로 그래프의 모든 정점들을 한 번씩 방문( 탐색 )하는 것을 목적으로 삼는다
2. 그래프의 데이터는 배열처럼 정렬이 되어 있지 않아 원하는 자료를 찾을 때까지 하나씩 모두 방문하여 찾기 때문이다
3. 그래프의 탐색 방법에는 여러가지가 있는데 그 중 가장 대표적인 두 가지 방법이 DFS 와 BFS 이다. 이 둘은 어떤 순서로 탐색을 하느냐만 다를 뿐, 모든 자료를 하나씩 확인한다는 점은 같다.

-----------------------------------------------------------------------------------

4. BFS ( Breadth First Search )

1. 너비를 우선적으로 탐색하는 방법으로, 너비 우선 탐색이라고 한다.
2. 주로 두 정점 사이의 최단 경로를 찾고 싶을 때 사용한다.
3. 만약, 경로를 하나씩 전부 방문하는 방식으로 하게 된다면, 최악의 경우에 모든 경로를 다 살펴보게 될지도 모른다
4. 가장 가까운 정점부터 탐색을하고, 더는 탐색할 정점이 없을 때는, 그 다음 떨어져 있는 정점을 순회한다.

 

** BFS 의 장단점 **

## 장점 ##

1. 최적의 해답을 찾음을 보장한다.

## 단점 ##

1. 최소 실행시간보다는 오래 걸린다는 것이 거의 확실하다.
2. 최악의 경우, 실행에 가장 긴 시간이 걸릴 수 있다.

-----------------------------------------------------------------------------------

5. DFS ( Depth First Search )

1. 깊이를 우선적으로 탐색하는 방법을, 깊이 우선 탐색이라고 한다.
2. 하나의 경로를 끝까지 탐색한 후, 원하는 도착점이 아니라면 다음 경로로 넘어가 탐색한다.
3. 하나의 경로를 끝까지 들어가서 확인하고 다음으로 넘어가기 때문에, 운이 좋다면 단 몇 번만에 경로를 찾을 수 있다.
4. 한 정점에서 시작해서 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색하고 싶을 때 사용한다.
5. BFS 보다 탐색 시간은 조금 늦을지라도 모든 노드를 완전히 탐색할 수 있다.

 

** DFS 의 장단점 **

## 장점 ##

1. 최선의 경우, 가장 빠른 알고리즘이다. '운 좋게' 항상 해답에 도달하는 올바른 경로를 선택한다면, 깊이 우선 탐색이 최소 실행시간의 해답을 찾는다.

## 단점 ##

1. 찾은 해답이 최적이 아닐 가능성이 있다.
2. 최악의 경우, 가능한 모든 경로를 탐험하고서야 해답을 찾으므로, 해답에 도달하는데 가장 오랜 시간이 걸린다.

-----------------------------------------------------------------------------------

6. BFS vs DFS

 

# BFS : 그래프가 큰 경우와 최단거리 문제일때 사용하는 것이 좋다.

# DFS : 그래프의 규모가 작고, depth 가 얕은 경우, 이동한 정점의 값을 가지고 계속 연산을 하는 경우( 재귀적으로 호출되는 경우 )에 사용하는 것이 좋다.