트리셋&트리맵 (TreeSet & TreeMap)

JayJi·2026년 4월 12일

목록 보기

18/30

문제	난이도	핵심
7785번 — 회사에 있는 사람	실버 V	정렬된 집합
1302번 — 베스트셀러	실버 IV	빈도 + 정렬
2357번 — 최솟값과 최댓값	골드 I	범위 내 최솟값/최댓값
1927번 — 이중 우선순위 큐	골드 IV	최솟값/최댓값 동시 삭제
5397번 — 키로거	실버 II	순서 유지 탐색

1. 개념

TreeSet과 TreeMap은 레드-블랙 트리(Red-Black Tree) 기반의 자료구조로, BST의 균형을 항상 유지한다.

HashSet/HashMap의 O(1) 대신 O(log N)이지만, 항상 정렬된 상태를 유지한다.

TreeSet  = 정렬된 집합  → 중복 없음, 오름차순 유지
TreeMap  = 정렬된 맵    → 키 기준 오름차순 유지

HashSet/HashMap과 달리 순서가 보장되고, 범위 탐색이 가능하다는 것이 핵심이다.

2. HashSet/HashMap vs TreeSet/TreeMap

	Hash 계열	Tree 계열
내부 구조	해시 테이블	레드-블랙 트리
탐색/삽입/삭제	평균 O(1)	O(log N)
정렬 순서	❌	✅ 오름차순
범위 탐색	❌	✅
null 허용	✅	❌

정렬이나 범위 탐색이 필요하면 Tree 계열, 단순 빠른 조회면 Hash 계열을 써라.

3. 핵심 포인트 2가지

범위 탐색 메서드를 활용하라

TreeSet/TreeMap은 BST 구조 덕분에 특정 값의 이전/이후 원소를 O(log N)에 찾을 수 있다.

// TreeSet 범위 탐색
set.first()          // 최솟값
set.last()           // 최댓값
set.floor(x)         // x 이하인 가장 큰 값
set.ceiling(x)       // x 이상인 가장 작은 값
set.lower(x)         // x 미만인 가장 큰 값
set.higher(x)        // x 초과인 가장 작은 값
set.subSet(a, b)     // a 이상 b 미만 범위

이중 우선순위 큐가 필요하면 TreeMap을 써라

최솟값과 최댓값을 동시에 삭제해야 하는 문제에서,
PriorityQueue 두 개를 쓰면 삭제 동기화가 복잡해진다.
TreeMap을 쓰면 firstKey() / lastKey()로 O(log N)에 깔끔하게 처리할 수 있다.

4. 코드

TreeSet 기본 연산

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

set.add(5);
set.add(1);
set.add(3);
// 내부 상태: [1, 3, 5] (자동 정렬)

set.first();          // → 1 (최솟값)
set.last();           // → 5 (최댓값)
set.floor(4);         // → 3 (4 이하 최댓값)
set.ceiling(4);       // → 5 (4 이상 최솟값)
set.lower(3);         // → 1 (3 미만 최댓값)
set.higher(3);        // → 5 (3 초과 최솟값)

set.contains(3);      // → true
set.remove(3);        // 삭제
set.size();           // → 2

// 내림차순 순회
for (int val : set.descendingSet()) {
    System.out.println(val);
}

TreeMap 기본 연산

TreeMap<Integer, String> map = new TreeMap<>();

map.put(5, "five");
map.put(1, "one");
map.put(3, "three");
// 키 기준 자동 정렬: {1=one, 3=three, 5=five}

map.firstKey();       // → 1 (최솟값 키)
map.lastKey();        // → 5 (최댓값 키)
map.floorKey(4);      // → 3 (4 이하 최대 키)
map.ceilingKey(4);    // → 5 (4 이상 최소 키)

map.get(3);           // → "three"
map.remove(1);        // 삭제

// 순회 (키 오름차순)
for (Map.Entry<Integer, String> entry : map.entrySet()) {
    System.out.println(entry.getKey() + " : " + entry.getValue());
}

이중 우선순위 큐 패턴 (7662번)

// 최솟값과 최댓값을 모두 O(log N)에 삭제
TreeMap<Integer, Integer> map = new TreeMap<>();  // 값 → 개수

// 삽입
map.put(val, map.getOrDefault(val, 0) + 1);

// 최솟값 삭제
int minKey = map.firstKey();
if (map.get(minKey) == 1) map.remove(minKey);
else map.put(minKey, map.get(minKey) - 1);

// 최댓값 삭제
int maxKey = map.lastKey();
if (map.get(maxKey) == 1) map.remove(maxKey);
else map.put(maxKey, map.get(maxKey) - 1);

커스텀 정렬 TreeSet

// 내림차순 TreeSet
TreeSet<Integer> descSet = new TreeSet<>(Collections.reverseOrder());

// 길이 오름차순, 같으면 사전순 TreeSet
TreeSet<String> strSet = new TreeSet<>((a, b) -> {
    if (a.length() != b.length()) return a.length() - b.length();
    return a.compareTo(b);
});

5. 시간복잡도

연산	시간복잡도
add / put	O(log N)
remove	O(log N)
contains / get	O(log N)
first / last	O(log N)
floor / ceiling / lower / higher	O(log N)

모든 연산이 O(log N)으로 균일하다. 레드-블랙 트리가 균형을 항상 유지하기 때문이다.

6. 주의사항

floor, ceiling 등은 해당하는 값이 없으면 null을 반환한다. int로 바로 받으면 NullPointerException이 발생하므로 null 체크를 먼저 하라.
TreeSet은 중복을 허용하지 않는다. 중복이 있는 데이터를 관리하려면 TreeMap<값, 개수> 형태로 카운트를 따로 관리하라.
커스텀 Comparator 사용 시 일관성을 지켜야 한다. compare(a, b) == 0이면 TreeSet은 같은 원소로 판단해 삽입하지 않는다. 의도치 않은 중복 제거가 생길 수 있다.
null을 원소로 넣을 수 없다. TreeSet/TreeMap은 원소 비교가 필요하기 때문에 null 삽입 시 NullPointerException이 발생한다.