SortedDict

Python에서는 TreeMap 자료구조로 만들어져있는 내장함수

TreeMap은 각 노드에 (key, value) 쌍 형태로 들어가 있어, key를 기준으로 노드의 위치가 결정되고 각 key에 대한 value값을 저장하는 형태이다.

따라서 TreeMap에서의 삽입, 삭제, 탐색 등 모든 함수의 시간복잡도는 O(logN)

 

기존 dict과 사용방법이나 함수는 동일하다. 

from sortedcontainers import SortedDict

d = dict()             # hashmap

d["banana"] = 6
d["apple"] = 2
d["cat"] = 1

print("hashmap")
for key, value in d.items():
    print(key, value)

sd = SortedDict()      # treemap 선언 
sd["banana"] = 6
sd["apple"] = 2
sd["cat"] = 1

print("treemap")
for key, value in sd.items():
    print(key, value)

>> 결과
hashmap
banana 6
apple 2
cat 1

treemap # treemap은 key를 기준으로 자동으로 항상 오름차순 정렬을 수행한다.
apple 2
banana 1
cat 6