자료구조 - 세트 (Set)

1. 세트란?

세트(Set)이란 집합을 정의하는 자료구조로 동일한 자료형을 모아놓은 것이다. 집합의 모든 원소(Key)는 유일해 중복이 허용되지 않는다. 삽입, 삭제, 탐색의 세 가지 연산을 지원한다. 구현 방식에 따라 해시 셋, 트리 셋 등이 존재한다.

 

2. 해시 세트

- 해시 세트(Hash Set)이란 해싱을 이용해 데이터를 저장하는 방법

- 모든 연산이 O(1)에 수행되기 때문에 가장 빠르다.

- Key값을 나열했을 때 순서를 예측할 수 없다.

 

3. 트리 세트

- 트리 세트(Tree Set)이란 일반적으로 균형 이진 검색 트리(Balanced Binary Search Tree) 중 레드 블랙 트리(Red-black Tree)로 구현되어 있다.

- 모든 연산이 O(logN)에 수행된다.

- key 값을 나열했을 때 정렬된 순서로 불러오며 정렬 방식을 지정할 수 있다.