TreeSet이란?

• HashSet과 마찬가지로 Set 컬렉션 중 하나
• 이진 검색 트리(binary search tree)라는 자료구조의 형태로 데이터를 저장하는 컬렉션 클래스
  • 이진탐색트리 중에서도 성능을 향상시킨 레드-블랙 트리(Red-Black Tree)로 구현되어 있다.
  • 일반적인 Set보다 데이터 추가, 삭제에는 시간이 오래 걸리지만 정렬되어 저장된다는 점 때문에 조회가 빠르다.
  • 기본적으로 오름차순 정렬을 지원하지만, 생성자의 매개변수로 Comparator 클래스를 구현하여 넣어주면, 정렬 방법도 설정할 수 있다.

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

• 이진탐색트리는 데이터가 한쪽으로 치우쳐져 들어올 경우 매우 비효율적인 성능을 낸다.
• 레드-블랙 트리는 이부분을 보완하기 위해 좋은 알고리즘을 사용하여 O(logN)의 시간복잡도를 보장한다.
  • 부모노드보다 작은 값을 가지는 노드는 왼쪽 자식으로, 큰 값을 가지는 노드는 오른쪽 자식으로 배치하여 데이터의 추가나 삭제 시 트리가 한쪽으로 치우쳐지지 않도록 균형을 맞춘다.

🫧 정렬된 데이터에서 값을 사용해야 하는 경우라면 TreeSet이, 그렇지 않은 경우에는 HashSet의 성능이 좋다.

TreeSet 생성자

• 기본 정렬 방식을 사용 시, default 생성자를 이용한다.
• 정렬 방식을 지정할 경우, Comparator을 구현하거나, 람다식으로 나타낸다.

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; //내림차순 정렬
            }
        });

Comparator 인터페이스

public interface Comparator<T> {
	int compare(T o1, T o2);
}

• 두 개의 객체를 비교하기 위한 인터페이스
• compare() 메서드는 두 매개변수 객체를 비교한다.
  ex) 객체 o1, o2가 있을 때 , compare(o1, o2)
  • return 값에 따라 o1과 o2의 위치가 결정된다.
  • return 1; (양수) : 위치를 변경하지 않음. 즉, o1이 o2보다 앞쪽에 위치하도록 결정한다.
  • return -1; (음수) : 위치를 변경함. 즉, o1이 o2의 뒤에 위치하도록 결정한다.
  • return 0; : return1과 비슷하거나 같음. 위치를 변경하지 않음

람다식 이용

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

기존의 set으로 생성

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

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

TreeSet 메서드

first(), last()

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

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

pollFirst(), pollLast()

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

• Queue의 poll() (첫번째 값을 반환하고 제거) 과 유사하다.
• pollFirst() : 가장 우선순위가 높은 값을 삭제하며 반환
• pollLast() : 가장 우선순위가 낮은 값을 삭제하며 반환

higher(), lower()

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

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

ceiling(), floor()

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

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

---

출처

[JAVA/자료구조] TreeSet : 정렬을 지원하는 Set
[Java] 자바 TreeSet 사용법 & 예제 총정리
[Java/자바] TreeSet 사용법
[JAVA] Comparator / Comparable - 정렬을 위한 클래스(인터페이스)