[Data Structure] 자료구조 - 2 (그래프, 트리, 해쉬)

그래프 (Graph)

- *정점(Vertices)와 *간선(Edge)로 구성됨

- 무방향(Undirected)과 방향(Directed) 그래프 2가지의 형태가 존재함

- 방향 그래프의 경우 다음 노드를 탐색할 때 지정한 경로밖에 갈 수 없음

- 필요에 따라 노드의 추가, 삭제가 용이함

 

* 정점(Vertices) : 노드(Node)라고도 하며, 탐색이 가능한 각 지점들을 의미함 (아래 사진의 A, B, C, D)

* 간선(Edge) : 각 정점에 연결된 경로를 의미함 (아래 사진의 AB, AD ... DB)

※ 방향그래프의 경우 정점 D에서 시작 했을 때 다음 탐색 경로는 정점 B이다.

 

방향성과 무방향성 그래프

 

트리 (Tree)

- 계층적 자료구조 형태

- 필요에 따라 노드의 추가, 삭제가 용이함

- 각 용어 정리

  * 루트(Root) : 최상위 노드

  * 깊이(Depth) : 루트를 기준으로 다른 노드로의 접근하기 위한 거리

  * 부모(Parent) : 자신과 연결된 노드 중 상위 노드

  * 자식(Child) : 자신과 연결된 노드 중 하위 노드

  * 형제(Sibling) : 같은 부모를 가지면서 같은 깊이를 가진 노드

  * 리프(Leaf) : 자식이 없는 노드

 

깊이가 2인 트리 구조

 

Windows 탐색기에서 볼 수 있는 트리(Tree) 구조

 

 

해쉬 (Hash)

- 키(Key)에 대한 결과값(Value)을 반환하는 자료구조

- *연관배열 구조(Associative array)를 이용함

 

*연관배열 구조(Associative array) : 키(Key) 1개와 값(Value) 1개가 1:1로 연관된 자료구조, 연관배열 구조는 다음 명령을 지원함

  - 키(key)와 값(value)이 주어졌을 때, 연관 배열에 그 두 값(key & value)을 저장하는 명령
  - 키(key)가 주어졌을 때, 연관되는 값(value)을 얻는 명령
  - 키(key)와 새로운 값(value)이 주어졌을 때, 원래 키에 연관된 값(value)을 새로운 값(value)으로 교체하는 명령
  - 키(key)가 주어졌을 때, 그 키(key)에 연관된 값(value)을 제거하는 명령

  ※ 위의 명령은 해쉬 테이블(Hash Table)에서도 동일하게 적용이 된다.

해쉬 테이블 (Hash Table)

- 키(Key), 해쉬함수(Hash Function), 해쉬(Hash), 값(value), 저장소(Bucket, Slot)로 구성됨

 * 키(key) : 고유한 값이며, 해쉬 함수의 input이 된다. 다양한 길이의 값이 될 수 있음
 * 해쉬함수(Hash Function) : 입력 받은 키(key)를 일정한 길이를 가지는 해시(hash)로 변경하여 저장소를 효율적으로 운영할 수 있도록 도와준다. 다만, 서로 다른 키(key)가 같은 해시(hash)가 되는 경우를 해시 충돌(Hash Collision)이라고 하는데, 해시 충돌을 일으키는 확률을 최대한 줄이는 함수를 만드는 것이 중요하다.
 * 해쉬(Hash) : 해시 함수(Hash Function)의 결과물이며, 저장소(bucket, slot)에서 값(value)과 매칭되어 저장된다.
 * 값(Value) : 저장소(bucket, slot)에 최종적으로 저장되는 값으로 키와 매칭되어 저장, 삭제, 검색, 접근이 가능해야 한다.

 

해쉬 알고리즘

[3] 해시 함수 - 위키백과

 

# Reference

[1] Data Structure 개발자라면 꼭 알아야 할 7가지 자료구조.

  URL : https://velog.io/@jha0402/Data-structure-개발자라면-꼭-알아야-할-7가지-자료구조

[2] [자료구조] Hash의 개념 및 설명.

  URL : https://go-coding.tistory.com/30

[3] 해시 함수 - 위키백과

  URL : https://ko.wikipedia.org/wiki/해시_함수