자료구조) 딕셔너리 ADT

딕셔너리 ADT

• ADT
  • 탐색 가능한 형태의 { key, value } 쌍 데이터 상목들의 집단을 모델링한 것이다.
  • 주요 작업
    1. searching
       ** key 탐색을 통해 원하는 데이터를 찾는 것
    2. inserting
    3. deleting
  • 종류
    1. unordered
    2. ordered
  • key 순서를 기준으로

딕셔너리 ADT 메소드

• int size() : 사전의 항목 수 반환
• bool isEmpty()
• element findElement(key)
• insertItem(key, element)
• element removeElement(key)

 

탐색

• 데이터 집단으로부터 지정된 key를 가진 element를 추출하는 것
• 유일키 사전 : 한 개의 키에 대해 하나의 element만 존재
• 중복키 사전 : 한 개의 키에 여러 개의 element가 존재

• 리스트
  • unordered: 선형탐색
  • ordered: 이진 탐색
• 트리
  • 탐색 트리 (bst, avl, splay)
• 해시 테이블

unordered dictionary ADT

• 삽입 O(1)
• 탐색, 삭제 O(n)
• 소규모의 사전 또는 삽입은 빈번하지만 탐색이나 삭제가 드문 형태에 유리
• findElement - 선형 탐색

 

 

ordered dictionary ADT

• 탐색 O(lon n) using 이진 탐색
• 이진 O(n) → 공간 확보
• 삭제 O(n)
• 탐색

• 이진 탐색 - 재귀 버전 : 재귀할 떄마다 후보 항목의 수가 절반으로 줄어든다.

---

References

• 성균관대학교 안용학 교수님의 2020-2 <데이터사이언스와 컴퓨팅 (알고리즘)> 수업을 들으며 공부한 내용입니다.