C++로 쉽게 풀어쓴 자료구조/ 탐색
탐색이란?
컴퓨터 프로그램에서 탐색은 하나 이상의 필드(field)로 구성되는 레코드(record)의 집합에서 원하는 레코드를 찾아내는 작업이다. 보통 이러한 레코드들의 집합을 테이블(table)이라 부른다. 레코드들은 서로 중복되지 않고 고유한 값을 가지는 키를 가지는데, 이것을 탐색키(search key)라 부른다.
맵이란?
맵은 탐색을 위한 자료구조이다. 맵(map) 또는 사전(dictionary)은 자료를 저장하고 키를 이용해 원하는 자료를 빠르게 찾을 수 있도록 하는 자료구조를 말한다. 맵은 키를 가진 레코드(keyed record) 또는 엔트리(entry)라 불리는 키-값 쌍(key, value)을 테이블에 저장한다. 이때 각 키는 유일하고 맵에 저장되는 키와 값은 어떠한 자료형도 가능하다.
키를 가진 레코드의 추상 자료형은 다음과 같다.
- 객체
- 키(key)와 값(value)을 가진 요소 (key, value)의 집합
- 연산
- create(key, value): 주어진 key와 value를 각각 키와 값으로 갖는 레코드를 생성한다.
- getKey(): 레코드의 키를 반환한다.
- getValue(): 레코드의 값을 반환한다.
- update(value): 레코드의 값을 value로 변경한다.
맵의 추상 자료형은 다음과 같다.
- 객체
- 유일한 키를 가진 엔트리(키를 가진 레코드)의 집합
- 연산
- create(): 공백 상태의 맵을 생성한다.
- search(key): 테이블에서 주어진 탐색키 key를 가진 레코드를 찾아 반환한다.
- insert(entry): 테이블에서 주어진 entry를 삽입한다.
- delete(key): 테이블에서 주어진 탐색키 key를 가진 레코드를 찾아 삭제한다.
- count(): 테이블의 모든 레코드 수를 반환한다.
맵을 구현하는 가장 간단한 방법은 배열일 것이다. 그러나 맵의 탐색 성능을 향상하고자 한다면 이진 탐색 트리와 같은 보다 효율적인 자료구조를 사용해야 한다.