07Dec2019 TIL

Today I learned :

• DataStructure (Graph / Tree / Binary Search Tree / Hash Table)

---

Data Structure 자료 구조

: 처리할 데이터의 모음 / 형태 / 관계

=> 처리할 일에 맞는 자료 구조를 선택하는 것이 관건!

\

Graph Data Structure 그래프형 자료 구조 :

각 노드의 연결성을 보여주는 데이터 자료 형태. 

e.g.) 지하철 노선도, 페이스북 인맥도, 네트워크 망, 가계도 등.

 

• Vertex (Node) :  각각의 데이터
• Edge :  각각의 노드를 연결하는 선 (방향과 가중치를 둘 수 있다)
• Adjacency : 노드 간 인접성. e.g.) 1은 55와 3과 인접한다.
• Path : 경로. 1에서 76까지 가는 최단의 경로

NODE와 NODE를 연결해주는 EDGE로 구성되어 있다.

. addVertex() : 노드를 생성하고 값을 부여한다 -> 다른 노드와 연결해준다.

. addEdge() : 노드와 노드 사이 연결성을 부여한다.

. display() : 전체 데이터를 보여준다.

---

Tree Data Structure 트리형 자료구조

그래프 형 자료구조의 일종으로, 데이터의 계층이 표현.

순환형 그래프 자료구조(cyclic data-structure)는 허용하지 않는다 (상하 관계가 무시되기 때문)

e.g.) DOM도 트리형 자료구조를 택한다.

출처 : https://www.tutorialspoint.com/data_structures_algorithms/tree_data_structure.htm

---

Binary Search Tree Data Structure 이진 탐색 트리

특정 값을 찾기 위해 중간 값을 기준으로 트리를 만들어 찾아 나가는 탐색 형태

한 노드는 반드시 두 개의 자식 노드를 가진다. (왼쪽 노드 < 오른쪽 노드 순서로 기입된다)

e.g.) 술병 뚜껑 up and down 게임 생각하면 조금 비슷하다.

출처  : https://www.tutorialspoint.com/data_structures_algorithms/binary_search_tree.htm

. retrieve () 특정 데이터 탐색

전체 데이터를 크기에 따라 작은 것 - 큰 순으로 일렬로 세운다 -> 중간 값을 root 값으로 지정한다 ->

root 값을 경계로 작은 그룹의 중간 값을 왼쪽 자식 노드로 값을 부여한다. &&

큰 그롭의 중간 값을 오른쪽 자식 노드 값으로 부여한다. -> 원하는 값을 찾을 때 까지 과정 반복 || 찾지 못함.

 

. insert() 특정 데이터 삽입 : 반드시 leaf Node에서만 삽입 할 수 있다 (데이터의 관계성을 깨뜨릴 수 있어서)

루트 데이터와 삽입 데이터 크기 비교 -> 크기가 작다면 왼쪽 자식 노트로 내려가 비교 ->

왼쪽 자식 노트보다 작다면 또 내려가 -> 최종 leaf Node 로 내려감 -> 노드 생성 후 삽입 데이터 값 지정->

부모 노드에 해당 삽입 데이터 자식노드로 추가해줌.

 

. delete() 특정 데이터 삭제 : 트리구조의 계층을 파괴 하지 않는 방향으로 진행...

---

Hash Table Data Structure 해시 테이블 자료 구조

데이터 공간을 미리 확보하고, 그 공간의 각각의 인덱스에 데이터를 저장하는 형태

e.g.) 사회 과학 대학교 사무실 사물함 배정 (학과이름 - 학번배정 - 사물함 배정)

 

출처 : https://subscription.packtpub.com/book/application_development/9781788833738/4/ch04lvl1sec28/hash-tables

Hash Table 자료 구조는 key - Hash Function - Buckets - Value로 구성되어 있음을 알 수 있다.

• Key : 고유한 값. 원하는 형태, 길이 가능 (i.e. 사회과학대학 monkey)
• Hash function : 고유한 key를 일정한 길이와 형태로 변환해주는 함수 (i.e. 단과대학생이름 -> 학번으로 치환)
• Hash : Hash_function(key)를 통과한 key 의 새로운 형태 (i.e. 20201234)
• Value : key에 대응하는 값 (i.e. 사회과학대학 monkey 의 각종 짐들)
• Buckets : Hash - Value 페어를 저장하는 공간. 빈공간 허용함 (i.e. 사물함). 

출처 : https://www.tutorialspoint.com/data_structures_algorithms/hash_data_structure.htm

장점으로는, 1) 한정된 공간을 효율적으로 사용과 2) 상대적으로 적은 메모리를 사용한다

 

그러나, 고유한 key 값을 유한한 Hash 값으로 바꾸면서 Hash 가 충돌하는 현상을 피하기 어렵다.

똑같이 학생회비 냈는데, 사물함 누구는 혼자 쓰고, 누구는 같이 쓰라는 걸 생각해보라.

 

단점으로는,

1) 데이터 크기와 관계 없이 공간을 선점하기 때문에 효율이 높지 않다.

2) 순서가 중요한 데이터 저장형으로 어울리지 않는다.