[자료구조] Set과 Map 근데 이제 해시와 트리를 곁들인

해시맵(Hash Map)은 많이 들어본 개념이다 하지만 해시를 이용한 셋(Set)과 트리를 이용한 셋(set)과 맵(Map)은 뭘까?

셋(Set)

중복되지 않는 원소들의 집합으로, 특정 원소의 존재 여부를 빠르게 확인할 수 있다.

---

맵(Map)

키-값(Key-Value) 쌍으로 데이터를 저장하는 자료구조로, 각 키는 유일하며 키를 통해 값에 빠르게 접근할 수 있다.

---

트리를 이용한 Set과 Map

트리를 이용한 Set과 Map은 이진 탐색 트리(Binary Search Tree, BST), 특히 균형 이진 탐색 트리(예: 레드-블랙 트리)를 사용하여 구현된다.

특징

• 정렬된 데이터: 원소들이 자동으로 정렬된 상태로 저장된다.
• 탐색, 삽입, 삭제의 시간 복잡도: 평균 및 최악의 경우 모두 O(log n)이다다.
• 순회가 용이: 중위 순회를 통해 오름차순 또는 내림차순으로 데이터를 쉽게 순회할 수 있습니다.

장점과 단점

장점:

• 데이터가 항상 정렬된 상태로 유지되므로, 범위 검색이나 순차 접근이 필요할 때 유리하다.
• 최악의 경우에도 성능이 보장된다다.

단점:

• 해시 테이블에 비해 상수 시간이 더 많이 소요될 수 있다.

---

해시 기반 Set과 Map

해시 기반의 Set과 Map은 해시 테이블을 기반으로 구현되고 해시 함수를 사용하여 키를 해시 버킷에 매핑한다.

특징

• 비정렬 데이터: 원소들이 특정 순서 없이 저장된다.
• 탐색, 삽입, 삭제의 평균 시간 복잡도: O(1)
• 최악의 경우 시간 복잡도: O(n) (해시 충돌 시)

장점과 단점

장점:

• 평균적으로 매우 빠른 탐색, 삽입, 삭제 성능을 보인다.

단점:

• 데이터가 정렬되지 않으므로, 정렬된 상태로 데이터를 처리해야 할 때는 부적합하다.
• 해시 함수의 품질에 따라 성능이 크게 좌우될 수 있다.
• 최악의 경우 성능이 저하될 수 있다.

---

트리 기반과 해시 기반 자료구조 비교

특징	트리 기반	해시 기반
구현 방식	균형 이진 탐색 트리 (레드-블랙 트리)	해시 테이블
데이터 정렬	정렬됨	정렬되지 않음
탐색 시간 복잡도	O(log n)	평균 O(1), 최악 O(n)
순회 순서	정렬된 순서로 순회 가능	임의의 순서로 순회
메모리 사용	상대적으로 적음	상대적으로 많음
사용 사례	정렬된 데이터, 범위 검색	빠른 삽입/삭제/탐색, 순서가 중요하지 않을 때

사용 사례

• 트리 기반:
  • 데이터가 항상 정렬된 상태로 유지되어야 할 때
  • 범위 검색이나 순차적 접근이 자주 필요할 때
  • 최악의 경우에도 일정한 성능을 보장받아야 할 때
• 해시 기반:
  • 빠른 삽입, 삭제, 탐색이 필요할 때
  • 데이터의 순서가 중요하지 않을 때
  • 해시 함수가 잘 설계되어 있어 충돌이 적을 때

---

언제 어떤 자료구조를 선택할까?

• 트리 기반 자료구조를 선택할 때:
  • 데이터 정렬: 데이터가 항상 정렬된 상태로 유지되어야 할 때.
  • 범위 검색: 특정 범위 내의 원소를 효율적으로 검색해야 할 때.
  • 반복자 안정성: 삽입이나 삭제 시에도 반복자의 유효성이 중요할 때.
• 해시 기반 자료구조를 선택할 때:
  • 성능 최적화: 빠른 삽입, 삭제, 탐색이 필요할 때.
  • 순서 무관: 데이터의 순서가 중요하지 않을 때.
  • 해시 함수 품질: 해시 함수가 잘 설계되어 있어 충돌이 적을 때.