[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