[JAVA/자료구조] TreeSet : 정렬을 지원하는 Set

TreeSet

TreeSet은 HashSet과 마찬가지로 Set 컬렉션 중 하나이다.

그러나 TreeSet 이진탐색트리(BinarySearch Tree)의 구조로 되어있어, 데이터를 넣을 때 자동으로 정렬된다.

따라서 TreeSet은 일반적인 Set보다 데이터 추가, 삭제에는 시간이 오래 걸리지만 정렬되어 저장된다는 점 때문에 조회가 빠르다.

기본적으로 오름차순 정렬을 지원하지만, 생성자의 매개변수로 Comparator 클래스를 구현하여 넣어주면, 정렬 방법도 설정할 수 있다.

---

TreeSet의 구현

레드 - 블랙 트리(Red - Black - Tree)

TreeSet은 이진탐색트리의 문제점을 보완한 균형이진탐색 트리 중 하나인 레드-블랙 트리를 사용한다.

이진탐색트리는 데이터가 한쪽으로 치우쳐져 들어올 경우 매우 비효율적인 성능을 내는데,

레드-블랙 트리는 이부분을 보완하기 위해 좋은 알고리즘을 사용하여 O(logN)의 시간복잡도를 보장한다. 

따라서 레드-블랙 트리를 사용하여 정렬하는 TreeSet의 정렬에 대한 성능은 믿고 사용해도 좋다.

물론 정렬된 데이터에서 값을 사용해야 하는 경우가 아니라면 HashSet이 성능이 더 좋다.

---

TreeSet 생성자

HashSet과 생성 방법은 똑같다.

기본 정렬 방식을 사용 시 default 생성자를 이용하면 되고,

정렬방식을 지정해주려면 Comparator을 구현하거나, 람다식으로 나타내주면 된다.

Comparator 구현 방법 ->https://innovation123.tistory.com/108

---

default 생성자

TreeSet<Integer> treeSet = new TreeSet<>();

Comparator 클래스 구현

TreeSet<Integer> treeSet = new TreeSet<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1; //내림차순 정렬
            }
        });

람다식 이용

TreeSet<Integer> treeSet = new TreeSet<>((o1, o2) ->o2-o1);

기존의  set으로 생성

TreeSet의 생성자에 기존의 정렬되지 않은 set을 넣어주면, 모든 데이터가 정렬되어 treeSet에 저장된다.

Set<Integer> hashSet = new HashSet<>();

TreeSet<Integer> treeSet = new TreeSet<>(hashSet);

 배열로 생성

TreeSet<Integer> treeSet = new TreeSet<Integer>(Arrays.asList(1,2,3));

---

Methods

아래 메서드들은 TreeSet에서만 사용할 수 있는 메서드이다.

따라서 생성할 때 Set set = new TreeSet<>(); 으로 생성하면 이용할 수 없다.

아래와 같이 TreeSet으로 생성해야 한다.

TreeSet<Integer> treeSet = new TreeSet<>();

---

first(), last()

• first() : 가장 우선순위가 높은 값 반환
• last() : 가장 우선순위가 낮은 값 반환

(정렬 방법에 따라 달라진다.)

//[1, 3, 4, 5, 7, 11]
int first = treeSet.first(); // 1
int last = treeSet.last(); // 11

---

pollFirst(), pollLast()

Queue의 poll()과 비슷하다.

• pollFirst() : 가장 우선순위가 높은 값을 삭제하며 반환
• pollLast() : 가장 우선순위가 낮은 값을 삭제하며 반환

int first = treeSet.pollFirst();
int last = treeSet.pollLast();

---

higher(), lower()

• higher(n) : n보다 큰 첫번째 값 반환
• lower(n) : n보다 작은 첫번째 값 반환

//[1, 3, 4, 5, 7, 11]
int higher = treeSet.higher(6); //5
int lower = treeSet.lower(6); //7

---

 ceiling(), floor()

• ceiling(n) : n과 일치하거나, 큰 첫번째 값 반환
• floor(n) : n과 일치하거나, 작은 첫번째 값 반환

//[1, 3, 4, 5, 7, 11]
int ceiling = treeSet.ceiling(5); //5
int floor = treeSet.floor(6); //7