[Dictionary]34. Dictionaries

목차

1. Dictionary ADT

2. List-based Dictionary

3. Search Table

 

1. Dictionary ADT

 Dictionary는 후에 배울 Binary Search Tree, AVL Tree, ADT 등등 탐색할 수 있는 ADT라고 생각하면 됩니다.

 

1) 특징

- 입력되는 데이터가 하나의 key로 간주된다

- data의 순서는 명시되어 있지 않음

(필요에 의하다면 추가 가능)

- 중복되는 key를 지닐 수 있다

 

2) 기능

- find(k): key k에 해당하는 위치를 반환

- put(k, o): 해당 위치에 새로운 값 입력

- erase(k): key k에 해당하는 값 제거

- size(), empty()

 

2. List-based Dictionary

 Dictionary를 구현하는 방법은 수도 없이 많으며, 그중에서 list를 기반으로 구현할 수 있습니다. 이는 unsorted sequence로, put에 O(1)의 시간이 소모되며 find, erase에 O(n)의 시간이 소요됩니다.

 

3. Search Table

 Search Table은 sorted sequence로 값을 저장하는 Dictionary로서, 배열을 기반으로 합니다.

 

1) 특징

- 배열 기반의 sorted sequence이다

- Binary Search algorism을 활용하여, 찾는데 필요한 시간을 줄일 수 있다

 

2) 기능

- find: binary search를 활용, O(logn)의 시간이 소요된다

- put: O(n)의 시간이 소모된다

- erase: O(n)의 시간이 소모된다

- 따라서, find를 주로 사용할 경우 Search Table을 사용하는 데 이점이 있다.

 

3) Binary Search

 

 Binary Search는 Search Table에서 find()기능에서 활용되는 알고리즘입니다. 마치 업다운 게임과 같이, 전체 배열의 중간을 우선 확인하고, 찾고자하는 key값 k와 크기 비교후 해당 방향으로 이동하는 방법입니다. 마치 heap에서의 탐색과 비슷한 방법으로, O(logn)의 시간이 소요됩니다.