Tree, BST

 

트리구조

 

트리구조는 이름에서도 직관적으로 알 수 있듯이, 나무와 닮은 구조를 가지고 있습니다.

하나의 뿌리로부터 가지가 뻗어나가는 형태를 지니고 있습니다.

 

 

트리 구조의 시작점을 root라고 합니다. 위에 그림에서는 2가 root입니다.

그리고 아래 뻗어나가는 가지들이 자식 노드입니다. 그럼 위에 있는 노드는 부모노드겠지요.

root만 부모도느인 것은 아닙니다. 자식들이 있으면 부모노드가 됩니다.

 

같은 부모에 붙어있는 자식노드는 형제노드라고 합니다. 2가 부모인 형제노드는 9, 12 ,8 , 99, 10입니다.

 

자식이 더이상 없는 노드는 leaf 노드라고 합니다.

 

트리 전체의 높이를 height라고 하고 한 층은 depth라고 합니다. 위의 그림에서 height는 3이 됩니다.

 

트리노드의 특징은?

• 부모 자식의 흐름은 상-하
• slef lopp 불가, loop 순회 불가
• 순회 방법은 전위, 중위, 후위 순회로 이어짐.
• 계층모델

 

그래프의 탐색 방법 DFS, BFS

 

• DFS (Depth First Search) : 깊이 우선 탐색, 최대한 깊게, stack으로 구현.
• BFS (Breadhth First Search) : 너비 우선 탐색, 최대한 넓게, queue로 구현.

 

DFS는 스택을 이용해서 갈 수 있는 만큼 최대한 깊이 가고, 더이상 갈 곳이 없다면 이전 정점으로 돌아갑니다. 모든 노드를 돌아보고 싶을 때 사용합니다.

 

BFS는 큐를 이용해서 지금 위치에서 갈 수 있는 것들을 모두 큐에 넣는 방식합니다. 하나의 정점으로 시작해서, 그 정점과 맞닿아 있는 가지들을 우선적으로 본 후, 그 다음줄에 가지들, 그 다음줄에 있는 가지들을 순차적으로 봅니다. 두 노드 사이에 최단경로 혹은 임의의 경로를 찾고 싶을때 사용합니다.

 

전위 순회, 중위 순회, 후위 순회

DFS의 기법을 따르는 전위, 중위, 후위 탐색입니다. root가 어디에 위치하느냐 따라서 용어가 다릅니다. root를 맨처음에 방문하는게 전위 순회, 중간에 방문하는것이 중위 순회, 마지막에 방문하는 것이 후위 순회 탐색입니다.

 

순회는 왼쪽->오른쪽으로 가는데

 

전위는 root -> 왼쪽노드 -> 오른쪽 노드로 순회

중위는 왼쪽노드 -> root -> 오른쪽 노드로 순회

후위는 왼쪽노드 -> 오른쪽 노드 -> root로 순회

 

이렇게 루트가 어디있느냐에 따라서 전, 중, 후위로 나뉩니다.