[Java] TreeSet 자료구조와 알고리즘

9north·2024년 9월 1일

알고리즘 문제를 풀 때 가장 많이 사용되는 언어 중 하나는 파이썬이지만, 파이썬으로 풀면 불리한 문제 유형 또한 분명히 존재한다. 바로 TreeSet이다. C++, Java에는 존재하지만 파이썬에는 존재하지 않는 자료구조이기 때문이다. Java를 사용할 경우 TreeSet 의 이점을 활용해 문제를 수월하게 풀 수 있다.

TreeSet이란

TreeSet은 컬렉션의 일종으로, HashSet과 같은 Set의 확장 클래스이다. 사용할 때에는 java.util.TreeSet을 import해야 한다.

TreeSet의 세 가지 특징은 다음과 같다.

요소 중복 비허용
요소 자동 정렬
null의 삽입 비허용

세 특징을 하나씩 살펴보자.

요소 중복 비허용

Set 자료구조가 그러하듯, TreeSet도 요소의 중복을 허용하지 않는다.

import java.util.*;

public class TreeSample {
    public static void main(String[] args) {
        Set<String> treeSet = new TreeSet<>();

        treeSet.add("America");
        treeSet.add("France");
        treeSet.add("Korea");
        treeSet.add("Korea");
        treeSet.add("Japan");
        treeSet.add("The United Kingdom");

		for(String t : treeSet) System.out.println(t);
    }
}

// 실행 결과
/*America
France
Japan
Korea
Mexico
The United Kingdom*/

Korea를 중복으로 입력해도 TreeSet에는 한 번만 입력된다.

요소 자동 정렬

매번 요소의 변경이 있을 때마다, 요소를 자동으로 정렬해 소팅해준다. 삽입할 때에는 add , 삭제할 때에는 remove를 사용한다. TreeSet은 레드 블랙 트리 자료 구조를 사용하고 있기 때문에, 삽입 삭제를 할 때마다 시간복잡도는 O(log n)이다. 따라서 매번 정렬을 갱신할 필요가 있을 때 유리한 자료구조이다. 정렬 규칙은 Comparator를 추가해 변경 가능하다.

import java.util.*;

public class tree {
	public static void main(String[] args) {
		Set<String> treeSet 
        = new TreeSet<>(Comparator.reverseOrder());

		treeSet.add("하");
		treeSet.add("나");
		treeSet.remove("나");
		treeSet.add("가");
		treeSet.add("라");
		treeSet.add("마");

		for (String t : treeSet)
			System.out.println(t);

	}
}
//실행 결과

/*
하
마
라
가
*/

null의 삽입 비허용

HashSet은 null을 삽입해도 되지만, TreeSet은 null의 삽입을 허용하지 않는다. ""와 같은 빈 값의 스트링은 허용한다. HashSet은 내부적으로 HashMap을 사용하는데, HashMap에서 null은 고유한 key값을 갖고 있어 정렬이 가능하다.
이에 비해 TreeSet은 내부에서는 TreeMap을 사용하고 있어, 에러 메시지도 TreeMap에서 NullPointerException이 발생하고 있다. TreeMap의 정렬은 compareTo()나 Comparator를 사용하는데, null에는 그러한 메서드가 존재하지 않기 때문에 오류가 발생하는 것이다.

Exception in thread "main" java.lang.NullPointerException
	at java.util.TreeMap.put(TreeMap.java:563)
	at java.util.TreeSet.add(TreeSet.java:255)
	at d9.tree.main(tree.java:10)

TreeSet의 주요 메서드

메서드	설명
add(Object o)	TreeSet 생성 시 언급된 동일한 정렬 순서에 따라 지정된 요소를 추가. 중복 허용 X
addAll(Collection c)	지정된 Collection의 모든 요소를 세트에 추가. Collection의 요소는 동질적이어야 함. 중복 허용 X
ceiling?(E e)	요소보다 크거나 같은, 해당 집합에서 가장 작은 요소를 반환(없으면 null)
clear()	모든 요소 제거
clone()	얕은 복사본 반환
Comparator comparator()	Comparator를 반환(기본은 null)
contains(Object o)	요소가 TreeSet에 있으면 true, 그렇지 않으면 false
first()	TreeSet의 첫 번째 요소를 반환 (TreeSet이 비었으면 NoSuchElementException)
floor?(E e)	요소보다 작거나 같은, TreeSet에서 가장 큰 요소를 반환(없으면 null)
headSet(Object toElement)	요소보다 작은 TreeSet의 요소 반환
higher?(E e)	요소보다 큰 해당 집합의 최소 요소를 반환(없으면 null)
isEmpty()	요소가 없거나 비어 있는 경우 true, 아니면 false
Iterator iterator()	반복자 반환
last()	TreeSet의 마지막 요소를 반환(TreeSet이 비었으면 NoSuchElementException)
lower?(E e)	요소보다 작은, 이 집합에서 가장 큰 요소를 반환(없으면 null)
pollFirst?()	첫 번째 요소 제거해 반환(없으면 null)
pollLast?()	마지막 요소를 제거해 반환(없으면 null)
remove(Object o)	요소 삭제
size()	요소의 개수 반환
subSet(Object from, Object to)	from 이상, to미만 범위의 요소 반환
tailSet(Object fromElement)	요소보다 크거나 같은 TreeSet의 요소를 반환