[Java/자료구조] TreeMap : 정렬을 지원하는 Map
TreeMap
TreeMap은 HashMap과 마찬가지로 Map 컬렉션 중 하나이다. 같은 Tree 구조로 이루어진 TreeSet과 차이점은 TreeMap이 Map.entry()를 저장한다는 점이다. TreeMap은 이진탐색트리(BinarySearch Tree)의 구조로 되어있어, 데이터를 넣을 때 자동으로 정렬된다.
TreeMap은 일반 Map보다 데이터 추가, 삭제에는 시간이 오래 걸리지만 정렬되어 저장된다는 점 때문에 조회가 빠르다.
기본적으로 Key값을 기준으로 오름차순으로 정렬된다. 그러나 Key값의 데이터타입이 Comparable이 구현되어있지 않은 클래스 이거나, 정렬 방법을 설정하려면 생성자의 매개변수로 Comparator 클래스를 구현하여 넣어주어야 한다.
TreeMap의 구현
레드 - 블랙 트리(Red - Black - Tree)
TreeMap은 이진탐색트리의 문제점을 보완한 균형이진탐색 트리 중 하나인 레드-블랙 트리를 사용한다.
이진탐색트리는 데이터가 한쪽으로 치우쳐져 들어올 경우 매우 비효율적인 성능을 내는데,
레드-블랙 트리는 이 부분을 보완하기 위해 좋은 알고리즘을 사용하여 O(logN)의 시간복잡도를 보장한다.
따라서 레드-블랙 트리를 사용하여 정렬하는 TreeMap의 정렬에 대한 성능은 믿고 사용해도 좋다.
물론 정렬된 데이터에서 값을 사용해야 하는 경우가 아니라면 HashMap이 성능이 더 좋다.
TreeMap 생성자
일반적인 Map과 생성 방법은 똑같다.
기본 정렬 방식을 사용 시 default 생성자를 이용하면 되고,
정렬방식을 지정해 주려면 Comparator을 구현하거나, 람다식으로 나타내주면 된다.
Comparator 구현 방법 ->https://innovation123.tistory.com/108
default 생성자
TreeMap<String, Integer> treeMap = new TreeMap<>();Comparator 클래스 구현
TreeMap<Integer, Integer> treeMap = new TreeMap<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
});람다식 이용
TreeMap<Integer, Integer> treeMap = new TreeMap<>((o1, o2) -> o2-o1);기본의 Map으로 생성
TreeMap의 생성자에 기존의 정렬되지 않은 Map을 넣어주면, 모든 데이터가 정렬되어 treeMap에 저장된다.
Map<String, Integer> map = new HashMap<>();
TreeMap<String, Integer> treeMap = new TreeMap<>(map);EntrySet을 바로 만들어서 생성 Map.of()
TreeMap<String, Integer> treeMap = new TreeMap<>(Map.of("kim", 10, "Lee",20,"Park", 30));중요한 점은 TreeMap에서만 제공하는 메서드를 사용하려면 Map인터페이스로 업캐스팅하여 생성하면 안 된다는 점이다.
TreeMap에서 제공하는 유용한 메서드들을 사용하기 위해 HashMap이 아닌 TreeMap을 사용하는 것이니,
TreeMap으로 생성을 해야 한다는 점을 기억하자.
Methods
아래 메서드들은 TreeMap에서만 사용할 수 있는 메서드이다.
위에서 말했듯이 생성할 때 Map<> map = new TreeMap<>(); 으로 생성하면 이용할 수 없다.
아래와 같이 TreeMap으로 생성해야 한다.
TreeMap<String, Integer> map = new TreeMap<>();
아래에서 제시할 메서드들 이외에도 Map 인터페이스의 모든 메서드를 사용할 수 있다.
firstKey(), lastKey()
- firstKey() : 가장 우선순위가 높은 Key 반환
- lastKey() : 가장 우선순위가 낮은 Key 반환
(정렬 방법에 따라 달라진다.)
String firstKey = map.firstKey();
String lastKey = map.lastKey();firstEntry(), lastEntry()
- firstEntry() : 가장 우선순위가 높은 Entry 반환
- lastEntry() : 가장 우선순위가 낮은 Entry 반환
Map.Entry<String, Integer> firstEntry = map.firstEntry();
Map.Entry<String, Integer> lastEntry = map.lastEntry();pollFirstEntry(), pollLastEntry()
Queue의 poll과 동일하다.
- pollFirstEntry() : 가장 우선순위가 높은 Entry를 삭제하며 반환
- pollLastEntry() : 가장 우선순위가 낮은 Entry를 삭제하며 반환
Map.Entry<String, Integer> pollFirstEntry = map.pollFirstEntry();
Map.Entry<String, Integer> pollLastEntry = map.pollLastEntry();higherEntry(), lowerEntry()
- higherEntry(key) : 지정된 Key보다 큰 첫 번째 Entry를 반환한다.
- lowerEntry(key) : 지정된 Key보다 작은 첫 번째 Entry를 반환한다.
higherKey(), lowerKey()도 똑같이 동작한다.
String higherKey = map.higherKey("key1");
Map.Entry<String, Integer> higherEntry = map.higherEntry("key1");
String lowerKey = map.lowerKey("key1");
Map.Entry<String, Integer> lowerEntry = map.lowerEntry("key1");ceilingKey(), floorKey()
- ceilingKey() : 지정된 Key와 일치하거나, 큰 첫 번째 Key값을 반환한다.
- floorKey() : 지정된 Key와 일치하거나, 작은 첫 번째 Key값을 반환한다.
ceilingEntry(), floorEntry()도 똑같이 동작한다.
String ceilingKey = map.ceilingKey("key1");
Map.Entry<String, Integer> ceilingEntry = map.ceilingEntry("key1");
String floorKey = map.floorKey("key1");
Map.Entry<String, Integer> entry = map.floorEntry("key1");c