TreeMap, HashSet, TreeSet

TreeMap (SortedDict)

TreeMap은 균형잡힌 이진트리 구조로 데이터를 관리해주는 자료구조 이다.

- 각 노드는 (key, value) 쌍 형태로 들어가고, key를 기준으로 노드의 위치를 결정한다

- 따라서 삽입, 삭제, 탐색 등 모든 함수의 시간복잡도가 전부 O(logN)이다.

- TreeMap 자료구조는 built-in function이 없다

- sortedcontainers 라는 외부 라이브러리가 필요

from sortedcontainers import SortedDict

차이점

1. 선언

sd = SortedDict()

2. keys(), items()와 같이 저장된 데이터를 순회할 때, 자동으로 key 기준으로 오름차순 순회 된다.

대체로 "오름차순" dictionary 출력이 필요한 문제에 쓰이는 듯하다

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
apple 2
banana 1
cat 6

HashSet (Set)

set은 HashSet 자료구조로 표현된어있다.(기본 set 집합)

- HashSet은 바로 해싱을 기반으로 데이터들을 관리해주는 자료구조이다.

- 그러므로 삽입, 삭제, 탐색이 전부 O(1)이다.

- HashSet은 빠르지만 구조상 들어온 값의 순서는 보장 X

- set에는 어떤 type도 다 들어올 수 있지만, immutable한 값만 가능하기에, list, dict와 같은 type은 가변적이므로 set 원소에 넣으면 에러 발생

s5 = {3, 5, [1, 5]}                    # error - list는 unhashable type

set 생성, 자주쓰는 함수

1. set()

a = set()

2. 리스트를 set으로 변경 가능

b = [1, 2, 3]

a = set(b)

- set을 이용할때 자주 사용하는 함수

s = set()

1. s.add(E)
2. s.remove(E)
3. E in s

TreeSet (SortedSet)

TreeSet: 균형잡힌 이진트리, sorted 이진트리

삽입, 삭제 탐색 등 모든 함수의 시간 복잡도 O(logN)

• 기본적으로 오름차순으로 정렬됨

from sortedcontainers import SortedSet

s = SortedSet()      # treeset

• 다른 set처럼 s.add, s.remove(E), E in s 는 똑같고, s.bisect_left(E) 이진탐색 함수가 가능함.
  • E보다 같거나 큰 최초의 데이터가 들어있는 index를 반환한다.
  • 없으면 마지막 인덱스를 반환한다

// 이진 탐색으로 해당 E가 들어갈 자리를 준다고 생각하면 편함

s.bisect_right(E)

• 최대값 s[-1], 최소값 s[0] 으로 구한다 -> 원래 [-1]의 경우에도 O(N)이 걸리지만 SortedSet자체는 구조가 이진트리이므로 탐색이 전부 O(logN)이다.