개념
정렬된 맵(Ordered Map)은 맵의 엔트리들을 전체 순서(total order)에 따라 정렬하고, 정렬된 순서에 따라 키와 값을 검색한다. 맵의 엔트리들이 정렬되어 있으면, 맵의 ADT의 추가적인 함수들을 효율적으로 구현할 수 있다.
추상 데이터 타입(ADT)
- firstEntry(): 가장 작은 키값을 가진 엔트리의 iterator을 반환한다. 만약 맵이 비었으면 end를 반환한다.
- lastEntry(): 가장 큰 키값을 가진 엔트리의 iterator의 반환한다. 만약 맵이 비었으면 end를 반환한다.
- ceilingEntry(k): k보다 크거나 같은 값을 가지는 키 중 최소값의 iterator을 반환한다. 만약 그러한 값이 없다면, end를 반환한다.
- floorEntry(k): k보다 작거나 같은 값을 가지는 키 중 최대값의 iterator을 반환한다. 만약 그러한 값이 없다면, end를 반환한다.
- lowerEntry(k): k보다 큰 값을 가지는 키 중 최소값의 iterator을 반환한다. 만약 그러한 값이 없다면, end를 반환한다.
- higherEntry(k): k보다 작은 값을 가지는 키 중 최대값의 iterator을 반환한다. 만약 그러한 값이 없다면, end를 반환한다.
구현
정렬된 맵은 위 ADT를 구현해야 하므로 비정렬 리스트나 해시 테이블을 사용할 수 없다. 따라서 스킵 리스트나 이진 탐색 트리 등으로 구현 해야한다.
이진 검색(Binary Search)
이진 검색은 정렬된 원소를 갖는 리스트 등에서 $O(\log{n})$의 실행시간으로 탐색을 하는 방법이다. algorithm의 binary_search 함수를 이용해 검색할 수 있다.
스킵 리스트(Skip List)
스킵 리스트(Skip List)는 정렬된 맵 ADT를 효율적으로 구현하는 자료구조이다. 스킵 리스트는 엔트리를 랜덤하게 배치하여 검색과 수정을 평균 $O(\log{n})$ 시간에 수행한다. 이 때의 평균 시간 복잡도는 입력되는 키들의 확률 분포에 종속되지 않는다. 대신, 삽입의 구현에 있어 새 엔트리의 위치를 결정하는 데 도움을 주는 랜덤-넘버 생성자의 사용에 종속된다.
반응형
댓글