카테고리 없음
자료구조 Set and Map (Hash 기반 vs Tree 기반) (NeetCode 21번 알고리즘 : BST Sets and Maps )
코테챌린져
2024. 7. 10. 16:58
자료구조 Set
자료구조에서의 set는 단순히 , 고유한 요소들의 모음을 나타내는 class이다.
Tree 기반 set와 해시 기반 Set가 존재한다.
특징
1. 중복된 요소가 없음.
2. 순서가 없음.
3. 변경 가능 (추가, 제거 가능)
해시 기반 Set
대부분 set는 해시 테이블 기반으로 만들어지며, insert, add 등이 O(1)의 시간 복잡도를 가진다.
Initialize
thisset = set()
# thisset = {}를 하면 dict로 인식하기 때문에 초기화는 set()로 해준다.
thisset = {1,2,3}
# set 초기화
Add and Remove
thisset.add(4)
thisset.remove(3)
Set Operations
# 합집합
union_set = set1 | set2
print(union_set) # 출력: {1, 2, 3, 4, 5}
# 교집합
intersection_set = set1 & set2
print(intersection_set) # 출력: {3}
# 차집합
difference_set = set1 - set2
print(difference_set) # 출력: {1, 2}
Other Methods
- len(set): set의 요소 개수를 반환
- in: 요소가 set에 있는지 확인
- clear(): 모든 요소를 제거
- copy(): set의 복사본을 반환
my_set = {1, 2, 3, 4}
# 요소 개수
print(len(my_set)) # 출력: 4
# 요소 존재 여부 확인
print(2 in my_set) # 출력: True
print(5 in my_set) # 출력: False
# 모든 요소 제거
my_set.clear()
print(my_set) # 출력: set()
# 복사본 생성
my_set = {1, 2, 3}
my_set_copy = my_set.copy()
print(my_set_copy) # 출력: {1, 2, 3}
BST Set
BST Set는 자료구조 set의 한 종류로써 고유한 요소들의 모임이지만, 위에서 언급한 해시 기반 해쉬와는 다르게 BST로 구현을 하게 된다면 값들이 정렬 되게 만든다. 즉, 해시 테이블 기반의 set은 요소들의 순서를 보장하지 않지만, 트리 기반의 set은 항상 요소들이 정렬된 상태를 유지한다.
Tree로 구현시 장점
- 정렬된 데이터 유지: 트리 기반의 set은 요소들이 항상 정렬된 상태를 유지한다. 이는 데이터가 정렬된 상태로 필요할 때 유용하다.
- 범위 쿼리: 트리 기반 set은 특정 범위 내의 요소들을 효율적으로 찾을 수 있다. 예를 들어, 최소값, 최대값 또는 특정 범위 내의 모든 값을 찾는 작업이 효율적이다.
- 순서 기반 작업: 정렬된 데이터가 필요하거나, 순서 기반의 작업을 자주 수행해야 하는 경우 트리 기반의 set이 더 유리하다.
Tree로 구현시 단점
- 성능: 평균적으로 해시 테이블 기반의 set이 요소 추가, 삭제, 검색에서 더 빠르다 (O(1) vs. O(log n)).
- 구현 복잡성: 트리 구조는 구현이 더 복잡하며, 이를 제대로 구현하기 위해 추가적인 노력이 필요하다.
어차피 Set를 사용하는거는 해쉬테이블의 장점을 살릴 때 많이 사용함으로 BST Set를 사용은 많이 안 할 것 같다.
구현
1. sortedcontainers 라이브러리에서 sortedSet 사용.
pip install sortedcontainersfrom sortedcontainers import SortedSet
# SortedSet 생성
tree_set = SortedSet()
# 요소 추가
tree_set.add(4)
tree_set.add(1)
tree_set.add(3)
tree_set.add(2)
print(tree_set) # 출력: SortedSet([1, 2, 3, 4])
# 요소 제거
tree_set.remove(3)
print(tree_set) # 출력: SortedSet([1, 2, 4])
# 요소 존재 여부 확인
print(2 in tree_set) # 출력: True
print(5 in tree_set) # 출력: False
# 요소 순회
for elem in tree_set:
print(elem)
# 출력:
# 1
# 2
# 4
print(tree_set)
# 출력:
#SortedSet([1,2,4])
2. 직접 구현
class TreeNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
class TreeSet:
def __init__(self):
self.root = None
def add(self, key):
if not self.root:
self.root = TreeNode(key)
else:
self._add(self.root, key)
def _add(self, node, key):
if key < node.key:
if node.left:
self._add(node.left, key)
else:
node.left = TreeNode(key)
elif key > node.key:
if node.right:
self._add(node.right, key)
else:
node.right = TreeNode(key)
def remove(self, key):
self.root = self._remove(self.root, key)
def _remove(self, node, key):
if not node:
return None
if key < node.key:
node.left = self._remove(node.left, key)
elif key > node.key:
node.right = self._remove(node.right, key)
else:
if not node.left:
return node.right
if not node.right:
return node.left
temp_val = self._min_value_node(node.right)
node.key = temp_val.key
node.right = self._remove(node.right, temp_val.key)
return node
def _min_value_node(self, node):
current = node
while current.left:
current = current.left
return current
def contains(self, key):
return self._contains(self.root, key)
def _contains(self, node, key):
if not node:
return False
if key < node.key:
return self._contains(node.left, key)
elif key > node.key:
return self._contains(node.right, key)
else:
return True
def in_order_traversal(self):
elements = []
self._in_order_traversal(self.root, elements)
return elements
def _in_order_traversal(self, node, elements):
if node:
self._in_order_traversal(node.left, elements)
elements.append(node.key)
self._in_order_traversal(node.right, elements)
# 사용 예제
tree_set = TreeSet()
tree_set.add(4)
tree_set.add(1)
tree_set.add(3)
tree_set.add(2)
print(tree_set.in_order_traversal()) # 출력: [1, 2, 3, 4]
tree_set.remove(3)
print(tree_set.in_order_traversal()) # 출력: [1, 2, 4]
print(tree_set.contains(2)) # 출력: True
print(tree_set.contains(5)) # 출력: False
자료구조 Map
자료구조에서 map은 키-값 쌍을 저장하고, 키를 사용하여 값을 효율적으로 검색할 수 있는 데이터 구조이다.
특징
- 키-값 쌍 저장: map은 각 요소가 키와 값으로 구성된 데이터를 저장한다.
- 고유한 키: 각 키는 고유해야 하며, 이를 통해 값을 검색할 수 있다.
- 효율적인 검색: 키를 사용하여 값을 빠르게 검색할 수 있다. O(1) (해시 테이블 기반), O(logn) (트리기반)
- 삽입, 삭제, 검색 연산: 일반적으로 O(1) (해시 테이블 기반) 또는 O(log n) (트리 기반) 시간 복잡도를 가진다.
해시 기반 Map
파이썬의 경우 dict 자료구조를 사용하면 된다. 끝.
BST Map
Map의 한 종류로써 해시 테이블 기반이 아닌 트리로 구현된 map이다. 해시 기반과는 다르게 key값으로 정렬된다. 파이썬에서의 dict는 해시 테이블 기반이므로 트리 기반 해시 테이블은 sortedDict를 사용하거나 직접 구현해야 한다.
구현
1. sortedcontainers 라이브러리에서 sortedDict 사용.
pip install sortedcontainers
from sortedcontainers import SortedDict
# SortedDict 생성
sorted_dict = SortedDict()
# 요소 추가
sorted_dict['c'] = 3
sorted_dict['a'] = 1
sorted_dict['b'] = 2
# SortedDict는 자동으로 키를 정렬된 상태로 유지
print(sorted_dict) # 출력: SortedDict({'a': 1, 'b': 2, 'c': 3})
# 요소 접근
print(sorted_dict['a']) # 출력: 1
# 요소 삭제
del sorted_dict['b']
print(sorted_dict) # 출력: SortedDict({'a': 1, 'c': 3})
# 요소 존재 여부 확인
print('c' in sorted_dict) # 출력: True
print('b' in sorted_dict) # 출력: False
# 키와 값 순회
for key, value in sorted_dict.items():
print(key, value)
# 출력:
# a 1
# c 3
2. 직접구현
class TreeNode:
def __init__(self, key, value):
self.key = key
self.value = value
self.left = None
self.right = None
self.height = 1
class AVLTreeMap:
def __init__(self):
self.root = None
def insert(self, key, value):
if not self.root:
self.root = TreeNode(key, value)
else:
self.root = self._insert(self.root, key, value)
def _insert(self, node, key, value):
if not node:
return TreeNode(key, value)
if key < node.key:
node.left = self._insert(node.left, key, value)
elif key > node.key:
node.right = self._insert(node.right, key, value)
else:
node.value = value
return node
node.height = 1 + max(self._get_height(node.left), self._get_height(node.right))
balance = self._get_balance(node)
if balance > 1 and key < node.left.key:
return self._right_rotate(node)
if balance < -1 and key > node.right.key:
return self._left_rotate(node)
if balance > 1 and key > node.left.key:
node.left = self._left_rotate(node.left)
return self._right_rotate(node)
if balance < -1 and key < node.right.key:
node.right = self._right_rotate(node.right)
return self._left_rotate(node)
return node
def _left_rotate(self, z):
y = z.right
T2 = y.left
y.left = z
z.right = T2
z.height = 1 + max(self._get_height(z.left), self._get_height(z.right))
y.height = 1 + max(self._get_height(y.left), self._get_height(y.right))
return y
def _right_rotate(self, z):
y = z.left
T3 = y.right
y.right = z
z.left = T3
z.height = 1 + max(self._get_height(z.left), self._get_height(z.right))
y.height = 1 + max(self._get_height(y.left), self._get_height(y.right))
return y
def _get_height(self, node):
if not node:
return 0
return node.height
def _get_balance(self, node):
if not node:
return 0
return self._get_height(node.left) - self._get_height(node.right)
def get(self, key):
return self._get(self.root, key)
def _get(self, node, key):
if not node:
return None
if key < node.key:
return self._get(node.left, key)
elif key > node.key:
return self._get(node.right, key)
else:
return node.value
def delete(self, key):
self.root = self._delete(self.root, key)
def _delete(self, node, key):
if not node:
return node
if key < node.key:
node.left = self._delete(node.left, key)
elif key > node.key:
node.right = self._delete(node.right, key)
else:
if not node.left:
return node.right
elif not node.right:
return node.left
temp = self._get_min_value_node(node.right)
node.key = temp.key
node.value = temp.value
node.right = self._delete(node.right, temp.key)
if not node:
return node
node.height = 1 + max(self._get_height(node.left), self._get_height(node.right))
balance = self._get_balance(node)
if balance > 1 and self._get_balance(node.left) >= 0:
return self._right_rotate(node)
if balance > 1 and self._get_balance(node.left) < 0:
node.left = self._left_rotate(node.left)
return self._right_rotate(node)
if balance < -1 and self._get_balance(node.right) <= 0:
return self._left_rotate(node)
if balance < -1 and self._get_balance(node.right) > 0:
node.right = self._right_rotate(node.right)
return self._left_rotate(node)
return node
def _get_min_value_node(self, node):
if node is None or node.left is None:
return node
return self._get_min_value_node(node.left)
# 사용 예제
avl_map = AVLTreeMap()
avl_map.insert("apple", 10)
avl_map.insert("banana", 20)
avl_map.insert("cherry", 30)
print(avl_map.get("apple")) # 출력: 10
print(avl_map.get("banana")) # 출력: 20
print(avl_map.get("grape")) # 출력: None
avl_map.delete("banana")
print(avl_map.get("banana")) # 출력: None
p.s. 파이썬에서의 Map 함수
파이썬에서의 map 함수는 자료구조 map과는 전혀 상관없는 함수이다. 파이썬의 map 함수는 함수형 프로그래밍 도구 중 하나로, 주어진 함수와 하나 이상의 이터러블(예: 리스트)을 인수로 받아, 이터러블의 각 요소에 함수를 적용하여 새로운 이터러블을 생성한다.
import sys
this_list = list(map(int, sys.stdin.readline().rstrip().split(' ')))this_list = [1,2,3]
print(list(map(lambda x: x+ 1,this_list)))