✨ TreeMap이란?
TreeMap은 HashMap과 마찬가지로 Map 컬렉션 중 하나이다.
Red-Black-Tree 기반으로 구현된 NavigableMap의 하나로, Key를 기준으로 정렬된 상태를 유지한다는 특징이 있다.
- Key를 기준으로 오름차순 정렬되며,
Comparator을 사용해 정렬 기준을 설정할 수도 있다. - 내부적으로 이진 균형 트리 구조이기에, 시간 복잡도로 탐색, 삽입, 삭제가 가능하다.
- 하지만, 정렬이 진행되기 때문에 일반 Map보다 데이터 추가, 삭제는 시간이 걸리지만, 조회는 빠르다.
- Key 값의 데이터타입이 Comparable이 구현되어 있지 않은 클래스거나, 정렬 방법을 설정하려면, 생성자의 매개변수로
Comparator클래스 구현을 해줘야 한다. lowerKey(), HigherKey(), ceilingEntry(), floorEntry같이 NavigableMap 기능을 지원하여, 특정 값과 가장 가까운 Key를 찾을 수 있다.
✨ TreeMap 사용 예시
- 정렬된 상태로 데이터 저장
- 범위 검색 (SubMap, HeadMap, TailMap 이용)
- 최소, 최대 값 찾기 (firstEntry(), lastEntry())
- 가장 가까운 값 찾기 (ceilingEntry(), floorEntry())
- 빈도수 계산 및 순위 정렬
✨ 정렬 저장 및 최소, 최대
만약 아래의 데이터가 TreeMap에 들어있다고 하자.
{30, "30대"}, {50, "50대"}, {20, "20대"}, {40, "40대"}, {60, "60대 이상"}
이대로 Map을 출력해보면
System.out.println("TreeMap : " + treeMap);{20=20대, 30=30대, 40=40대, 50=50대, 60=60대 이상}으로 알아서 정렬되어 출력된다.
System.out.println("작은 키: " + treeMap.firstKey());
System.out.println("큰 키: " + treeMap.lastKey());위의 firstKey와 lastKey를 출력해보면, 10, 60이 각각 출력된다.
✨ 다른 Methods
우선순위
Map.Entry<Integer, String> firstEntry = treeMap.firstEntry();
Map.Entry<Integer, String> lastEntry = treeMap.lastEntry();firstKey, lastKey와 유사하며,
해당 값들 출력 시 20=20대, 60=60대 이상 이 출력된다.
삭제하며 반환
Map.Entry<Integer, String> pollFirstEntry = treeMap.pollFirstEntry();
Map.Entry<Integer, String> pollLastEntry = treeMap.pollLastEntry();각각 첫 번째, 마지막 키를 삭제하고 그 다음을 출력하는 메소드이다.
위의 예시 기준으로 출력 시,
30=30대, 50=50대 가 출력된다.
지정키보다 작거나 큰 키
// 지정 Key보다 큰 값 중 가장 작은 값
System.out.println(treeMap.higherKey(30)); // 40 출력
Map.Entry<Integer, String> higherEntry = treeMap.higerEntry(30); // 출력하면 40=40대 반환
// 지정 Key보다 작은 값 중 가장 큰 값
System.out.println(treeMap.lowerKey(30)); // 20 출력
Map.Entry<Integer, String> lowerEntry = treeMap.lowerEntry(30); // 출력하면 20=20대 반환만약 각각에 해당하는 값이 없다면 null을 갖게 된다.
지정키와 일치하거나 큰/작은 값
// 지정키와 일치하거나 큰 첫 번째 값
System.out.println(treeMap.ceilingKey(30)); // 30 출력
Map.Entry<Integer, String> ceilingEntry = treeMap.ceilingEntry (30); // 출력하면 30=30대 반환
// 지정키와 일치하거나 작은 첫 번재 값
System.out.println(treeMap.floorKey(10)); // null 출력
Map.Entry<Integer, String> floorEntry = treeMap.floorEntry(30); // 출력하면 null 반환
System.out.println(treeMap.floorKey(70)); // 60 출력
Map.Entry<Integer, String> floorEntry = treeMap.floorEntry(30); // 출력하면 60=60대 이상 반환✨ Comparator 구현
TreeMap<Integer, String> ascMap = new TreeMap<>((a, b) -> a - b);
TreeMap<Integer, String> descMap = new TreeMap<>((a, b) -> b - a);위의 두 맵에 {1, "One"}, {2, "Two"}, {3, "Three"}를 넣었다고 하자.
그러면 ascMap에서 a-b로 쓴건 오름차순을 의미하고, 이는 1, 2, 3 순으로 값을 저장한다.
descMap에서 b-a는 내림차순이며, 3, 2, 1 순으로 값을 저장한다.
만약, 람다식이 아닌 Comparator를 직접 구현하게 되면!
Comparator<Integer> comparator = new Comparator<Integer>() {
@Override
public int compare(Integer a, Integer b) {
return b-a;
}
}
TreeMap<Integer, String> descMap = new TreeMap<>(comparator);이렇게 작성할 수도 있다!
comparator의 compare 메소드 안에 내림차순, 오름차순 기준에 맞춰 작성해주면 된다.
🤔 그냥 Comparator에 내장된 메소드를 바로 사용하고 싶다면!
오름차순 (자연 순서)
TreeMap<Integer, String> map = new TreeMap<>(Comparator.naturalOrder());내림차순 (역순 정렬)
TreeMap<Integer, String> map = new TreeMap<>(Comparator.reverseOrder());문자열 길이 비교
{1, "일"}, {2, "일일"}, {3, "일일일"}
이와 같이 <Integer, String> 형태고, value 값의 길이로 구분하고 싶다면!
- 오름차순
TreeMap<Integer, String> map = new TreeMap<>(
Comparator.comparingInt(entry -> entry.getValue().length())
);- 내림차순 (두 가지 가능)
TreeMap<Integer, String> map = new TreeMap<>(
Comparator.comparingInt((entry1, entry2) -> Integer.compare(entry2.getValue().length(), entry1.getValue().length()))
);TreeMap<Integer, String> map = new TreeMap<>(
Comparator.comparingInt(entry -> entry.getValue().length().reversed())
);
{"일", "한글자"}, {"일일", "두글자"}, {"일일일", "세글자"}
이와 같이 <String, String> 형태고, key 값의 길이로 구분하고 싶다면!
- 오름차순
TreeMap<Integer, String> map = new TreeMap<>(
Comparator.comparingInt(String::length)
);- 내림차순
TreeMap<Integer, String> map = new TreeMap<>(
Comparator.comparingInt(String::length).reversed()
);결국 key를 비교하냐, value를 비교하냐 기준으로 봐주면 된다!
