on
[Data Structure] 자료구조 - 2 (그래프, 트리, 해쉬)
[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/해시_함수
from http://mightyotter.tistory.com/33 by ccl(S) rewrite - 2021-12-30 12:27:08