TreeMap<K, V>

Java의 TreeMap은 Map 인터페이스, NavigableMap 인터페이스와 AbstractMap 클래스를 구현한다

특징

• Key 값 기준으로 자연적인 순서(오름차순)로 정렬한다
  • Comparator를 도입하여 정렬 기준을 재정의할 수 있다
• Red-Black 트리 (자가 균형 이진 탐색 트리의 종류)로 구현되어 있다
  • 즉, 데이터의 추가, 삭제, 조회의 시간 복잡도가 O(log N)으로 우수하다

메서드

1. 생성자

TreeMap<Integer, Integer> treeMap = new TreeMap<>();

정렬 기준을 재정의하고 싶은 경우 () 안에 Comparator를 도입하면 된다

2. 데이터 추가

treeMap.put(key, value);

3. 데이터 삭제

key 기준 제거

treeMap.remove(key);

최소 key 값의 entry 제거: Map.Entry<K, V>를 리턴한다

treeMap.pollFirstEntry();

최대 key 값의 entry 제거: Map.Entry<K, V>를 리턴한다

treeMap.pollLastEntry();

4. 데이터 조회

특정 key가 있는지 여부 조회

treeMap.containsKey(key); // boolean 값 리턴

특정 key의 value 조회

treeMap.get(key);

특정 value가 있는지 여부 조회

treeMap.containsValue(value); 
// 1개 이상의 key가 해당 value를 가지면 true

5. 최솟값, 최댓값 조회

최소/최대 키만 조회

treeMap.firstKey(); // 기본적으로 오름차순 정렬이라 최소값 리턴
treeMap.lastKey(); // 최대값 리턴

최소/최대 키 값의 entry 조회

treeMap.firstEntry(); 
treeMap.lastEntry();

6. 부분 조회

treeMap.subMap(startKey, endKey);

startKey부터 endKey 전까지의 범위에 포함되는 key들의 map을 리턴한다

7. 내림차순 전체 조회

전체 맵의 내림차순

NavigableMap<Integer, Integer> reversedTreeMap = treeMap.descendingMap();

key 값들의 내림차순

NavigableSet<Integer> reversedKeySet = treeMap.descendingKeySet();

8. 이외 유용한 메서드

• Map.Entry<K, V> ceilingEntry(K key) : 인수 키 이상인 키 값 중 최소 값의 entry를 리턴한다. 만족하는 entry가 없을 경우 null을 리턴한다

• Map.Entry<K, V> higherEntry(K key) : 인수 키 초과인 키 값 중 최소 값의 entry를 리턴한다. 만족하는 entry가 없을 경우 null 리턴한다

• SortedMap<K, V> headMap(K toKey): 인수 키 값보다 작은 키의 key-value 집합을 맵으로 리턴한다. boolean inclusive 인수를 추가할 수 있다

활용 문제 백준#7662

골드4인 문제지만 TreeMap을 사용하면 아주 간단하게 풀 수 있다.

문제 이해

3가지 연산이 가능하다

1. 데이터의 삽입
2. 현재 데이터 집합의 최솟값 제거
3. 현재 데이터 집합의 최댓값 제거

해결 방안

최솟값과 최댓값를 효율적으로 제거하기 위해서 우선순위큐를 2개 두고, 현재 제거되지 않은 데이터에 대한 맵을 유지하는 방식으로도 이 문제를 풀 수 있지만, TreeMap을 활용하면 더 간단하게 풀 수 있다.

최솟값은 .firstKey(), 최댓값은 .lastKey()를 활용해서 조회하고, 해당 키의 value 값이 0이면 맵에서 제거하면 된다. 어떤 값이 실제로는 제거되어야 하는데 아직 집합에 남아있는 잔실수를 방지할 수 있다.

초반에 설명했듯이 데이터의 추가, 삭제, 조회 연산 등이 O(log N)으로 효율적이기 때문에 시간 초과 또한 걸리지 않는다

풀이 코드

이중 우선순위 큐 #7662 풀이 코드

---

출처:
https://www.geeksforgeeks.org/treemap-in-java/
https://docs.oracle.com/javase/8/docs/api/java/util/TreeMap.html