그래프, 트리, B-tree, 해쉬테이블

그래프란?

- 단순히 노드(node)와 그 노드를 연결하는 간선(edge)을 하나로 모아놓은 자료구조

1. 즉, 연결되어 있는 객체간의 관계를 표현할 수 있는 자료구조이다.

ex) 지도, 지하철 노선도의 최단경로, 전기 회로를 생각하면 쉽다
연결되어있는 객체간의 관계를 표현할 수 있는 자료이다

그래프는 트리와 비슷하게 노드와 엣지로 구성되어 있습니다. 그래프에서는 노드를 버텍스, 엣지를 아크라고 부릅니다

● 그래프의 종류

- 방향 그래프 : 간선에 방향이 있는 그래프

- 무방향 그래프 : 방향이 존재하지 않아 양방향으로 이동이 가능한 그래프

- 완전 그래프 : 각 노드에서 다른 노드와  모두 연결된 그래프

 

● 깊이우선탐색, 너비우선탐색

  1. 깊이우선탐색 : DFS(Depth-First Search) 

  스택을 이용하여 구현

  스택에서 나왔거나, childNode가 없을때 자기자신을 출력하도록 한다.

  1. 데이터를 담을 스택을 만든다. 

  2. 가장 상위에 위치한 노드를 하나씩 차례대로 스택에 넣어준다.

  3.  단, 한 반복에 스택의 top이 하나씩 계속 출력되도록 한다. 

  4. 만약, 출력된 노드에 자식노드가 있다면, 스택에 담아주도록 한다. ==> 3번  

  5. 자식노드가 없다면 그냥 출력만 해준다. 

  

 

  2. 너비우선탐색 : BFS(Broad-First Search)

  큐를 이용하여 구현 

  큐를 dequeque된 노드는 출력을 해주되, childNode의 유무를 확인해준다.

  1. 큐에 상위 노드부터 하나씩 큐에 넣어준다.

  2. dequeque된 노드의 데이터를 출력해주고, 출력된 노드에 자식노드가 있다면 차례대로 큐에 넣어준다. ==>1번

  3. 출력된 노드에 자식노드가 없다면, 출력만 해준다.   

 

 

인접행렬)

 

인접리스트)

---

트리란?

● 트리의 특징

- 계층적인 구조를 가지고 있다

- 노드와 노드를 연결하는 Link들로 구성되어있다

- 노드가 N개인 트리는 항상 N-1개의 Link를 가진다

- 최대 두가지의 자식을 가진 트리를 이진 트리라고 한다

- 노드들은 특정순서로 나열될 수도 있고 그럴 수 없을 수도 있다, 각 노드는 어떤 자료형으로도 표현가능하다

- 부모노드로의 연결이 있을 수도 없을 수도 있다

 

● 트리의 종류

1) 이진트리의 종류 : 이진트리(binary tree), 이진 탐색 트리(binary search tree), 완전 이진 트리(complete binary tree),

   전 이진 트리(full binary tree), 포화 이진 트리(perfect binary tree)

2) 균형이냐 비균형이냐로 나뉠 수 있다

- 비균형 : 편향 이진 트리

3) 균형 트리의 일반적인 유형으로는 레드-블랙 트리와 AVL트리 이렇게 두가지가 있다

 

이진트리(binary tree)

(1) 각 Node가 최대2개의 자식노드를 갖는 트리를 말한다.

(2) 자식을3개 가지면 삼진트리, 10개 가지면 십진트리라고 부른다

 

이진 탐색 트리(B-tree -> binary search tree)

(1) 이진트리와는 다르게 특정조건을 만족해야 한다

(2) 조건 : 모든 왼쪽 자식노드 <= 현재 노드 < 모든 오른쪽 자식노드

(3) (2)사항의 조건은 모든 노드에 대해서 반드시 True여야 한다

 

완전 이진 트리(complete binary tree)

(1) 트리의 모든 높이(또는 깊이)에서 노드가 꽉 차있는 이진트리를 말한다

(2) 마지막 자식노드는 꽉 차있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져야 한다

 

전 이진 트리(full binary tree)
(1) 모든 Node의 자식노드가 없거나 정확히 두개 있는 경우를 말한다

 

포화 이진 트리(perfect binary tree)

(1) 전 이진트리 && 완전 이진트리인 경우를 말한다

(2) 노드의 갯수는 정확히 (2^K)-1 (K는 depth of height의 수)개 이다

 

편향 이진트리

- Binary Search Tree의 효율을 높이기 위해서는 불균형 트리를 균형 트리로
 바꿔주어야 하는 작업을 해주어야 한다
 이 작업을 하는 방법은 다양하게 있는데,
 그 중 AVL 트리, B -트리가 유명하다.

 

 

● 트리구조 순회방법

1. In-order traversal 중위순회

순서 : Left Node -> Root Node -> Right Node

2. Pre-order traversal 전위순회

순서 : Root Node -> Left Node -> Right Node

3. Post-order traversal 후위순회

순서 : Left Node -> Right Node -> Root Node

---

 

B-tree란?

B-트리는 1개의 노드에 2개 이상의 데이터를 지니고 있다.

이는 많은 정보를 더더욱 효율적으로 저장할 수 있으며 노드의 가지의 수와 높이가 기존의 트리구조보다

현저하게 적어질 수 있도록 해준다

● 노드의 가지수가 적어지면 안좋은거 아닌가?

- B-트리는 하나의 노드에 많은 정보를 담고 있다. 이는 간선의 높이를 동일하게 만들어준다.

  기존 트리구조는 데이터를 하나만 담고 있었기에,

  원하는 데이터를 찾기 위해서는 데이터를 찾고 다음 데이터로 이동하는 과정을  계속 거쳐야 했지만

  B-Tree는 하나의 노드안에 여러개의 데이터를 담고 있기 때문에 다음 노드로 이동하는 과정을 많이 줄일 수 있다. 

  따라서 다음노드를 찾는데에는 시간이 걸리겠지만, 노드 내부에서 데이터를 찾는데는 시간이 얼마 걸리지 않기 때문에,

  데이터의 조회 시간을 줄일 수 있다.

 

- 또한, B-Tree는 규칙이 있는데 부모노드에서 뻗어나가는 간선의 갯수가 부모노드 내의 데이터의 갯수 + 1 이 되야한다.

  4개의 데이터를 가진 부모노드는 총 5개의 자식을 가진다는 뜻이다.

  이러한 규칙은 트리구조가 대칭적으로 되도록 도와주고, 이러한 대칭성 또한 데이터에 접근하고 다루는 것을 빠르게 만들어준다.

---

해쉬테이블이란?

해쉬테이블은 Key 에 Value를 저장하는 데이터구조로 매우 빠른 속도로 저장이 가능하다

기본적인 개념은 input값을 받아서 그것을 특정 알고리즘으로 

index값으로 변환한뒤 그것을 저장합니다

hash function으로 변환한 index를 배열의 index로 지정하고, input값을 넣어준다

 

● 특징 

- 찾고자 하는 데이터의 key만 알고 있으면 즉시 위치를 찾는것이 가능하다

- 탐색, 저장, 삭제, 수정 등을 매우 빠른속도로 처리할 수 있다

- 크기가 매우 커질 수 있기 때문에 주의해야한다

 

● 충돌에 대한 처리 2가지

1. separate chaining 

- 장점 : 해시 테이블의 확장이 필요없고, 간단하게 구현이 가능하며, 삭제 작업또한 간단하다

- 단점 : 데이터의 양이 많아지면 그만큼 연결되는 리스트 또한 많아져서 캐시의 효율성이 떨어진다

2.Open Addressing

- 위에것과 달리 한 버킷당 들어갈 수 있는 엔트리가 하나뿐인 해시테이블이다

- 대표적인 방법인 선형탐사(Linear Probing)는 최초 해시값에 해당하는 버킷에 다른 데이터가 저장되어 있으면, 해당 해시값에서 비어있는 버킷이 나올때 까지 옮겨 다음 해시값에 해당하는 버킷에 (삽입, 삭제, 탐색)을 한다.

---