7. 사전 ADT (Dictionary ADT)

사전 ADT는 탐색 가능한 형태의 (키, 원소) 쌍 항목들의 모음을 모델링한다.

사전 내의 원소 탐색에는 키가 사용되고, 탐색한 원소가 존재하지 않는 경우 NoSuchKey 에러가 발생한다.

사전 ADT의 함수

int size();
bool isEmpty();
elem findElement(key);
void insertItem(key, value);
elem removeElem(key);

사전 구현에 따른 탐색기법

구현 형태	구현 종류	예	주요 탐색 기법
리스트	무순사전	기록 데이터	선형 탐색
	순서사전	일람표	이진 탐색
트리	탐색트리	이진탐색트리, AVL 트리, 스플레이 트리	트리 탐색
해시테이블			해싱

무순사전

사전 항목들을 임의의 순서대로 사전에 저장한 경우이다.

• insertItem은 맨 앞 혹은 맨 뒤에서 임의로 실행하면 되므로 $O(1)$ 시간이 소요된다.
• findElement 및 removeElement는 최악의 경우(항목이 존재하지 않는 경우) 주어진 키를 찾기위해 리스트 전체를 순회해야 하므로 $O(n)$이 소요된다.

무순사전은 소규모 사전이나, 입력은 빈번하지만 탐색과 삭제가 드문 로그 파일의 저장 등에 유용하다.

무순사전의 탐색은 단순히 리스트 전체를 순회하며 원소를 탐색하는 선형 탐색을 사용한다.

순서사전

사전 항목들을 키를 기준으로 배열하여 저장한다.

• findElement는 이진탐색을 활용하면, $O(\log n)$시간이 소요된다.
• insertItem은 최악의 경우, 공간 확보를 위해 $n$개의 항목을 이동해야 하므로 $O(n)$시간이 소요된다.
• removeItem도 같은 이유로 $O(n)$시간이 소요된다.

순서사전은 소규모 사전이나 탐색은 빈번하지만 삽입이나 삭제는 드문 사전에 유용하다.

이진 탐색

순서사전의 탐색에는 이진 탐색이 사용된다. 이진 탐색은 진행에서 재귀가 발생할 때마다 탐색해야할 원소의 수가 반감되므로 재귀는 최대 $\log (n)$회 실행된다.

def binarySearch(k, l, r):
    if l>r:
        raise Exception('NoSuchKey')
    mid = (l+r)/2
    if k=key(A[mid]):
        return elem(A[mid])
    elif k<key(A[mid]):
        return binarySearch(k, l, mid-1)
    else:
        return binarySearch(k, mid+1, r)