오늘은 비슷한듯 비슷하지 않은 2 + 1개의 데이터 구조를 공부할 예정이다.

Graph

Graph 란 Node 와 Node들을 잇는 Edge으로 구성되어 있는 데이터 구조이다.

Property

Node : Node
Edge : Node 와 Node 를 잇는 선

method

adjacent(a, b) : a 와 b 를 잇는 Edge 가 있는지 확인
remove_node(a) : a Node 를 삭제한다.
get_node_value(a) : a Node 의 value 를 확인
set_node_value(a, b) : a Node 의 value 를 b로 설정

ex) 네비게이션

Tree

모양은 Grahp 와 비슷하지만, 위에서 아래로 단방향성을 가지고 있다.

property

root : 트리의 inital Node
parent : 현재 노드의 부모 노드 ( 2, 3번 Node 의 parent 는 1번 Node 이다.)
Subtree : (2 - 4,5 - 8,9,10,11), (4 - 8,9) ... 등등
depth : root 와 해당 Node 잇는 Edge 의 갯수 (6의 경우 1 - 3 - 6 --> depth : 2)

Binary Search Tree

• 현재 Node 보다 값이 크면 오른쪽, 작으면 왼쪽으로 배치한다.
• 한 Node 당 최대 2개의 child 을 갖는다.

라는 규칙을 갖는 Tree 이다.

Method

insert_node(x) : Node 를 BST 규칙 에 의해 적절한 위치에 배치시킨다.'
remove_node(x) : x값을 가지고 있는 Node 를 찾아 삭제한후 해당 Node 의 child을 적절한 위치에 배치시킨다.
contain(x) : x 값을 가지고 있는 Node 를 찾는다.

DFS

Recursion 을 이용한다.

장점

• 저장공간의 수요가 적다.
• target 이 깊숙한곳에 있다면 비교적 빠르게 searching 할수 있다.

단점

• 해가없는 경로에서는 무한경로에 빠지는 경우가 있다.
  depth 설정하여 설정한 depth까지 만 탐색하는 방법이 있다.
• 얻은 경로가 최적의 경로가 아닐수도 있다.
  여러개의 경로가 있을수 있지만 한개의 경로를 찾게되면 함수가 끝이난다.

BFS

for loop 과 queue 을 이용한다.

장점

• 여러개의 경로가 있을경우 최단 경로를 찾을수 있다.
• 여러개의 경로가 있을경우, 어느한 경로가 무한경로에 빠지는경우에도 답을 찾아 낼 수 있다.

단점

• child의 갯수가 많을경우, 저장공간이 많이 필요하다.
• 답이 깊숙히 있을경우 탐색에 오랜시간이 걸린다.

백 트래킹

풀이시간단축 을 위해 일정한 규칙(가능성)에 만족하지 않으면 그 하위 child은 배제 한 채 다른 Node 를 탐색하는 방법이다.