java TreeMap에 대해 알아보자!

(1) 정의

Red-black Tree를 이용하여 구현한 Key 값을 기준으로 정렬되는 Map이다.
정렬 기준은 default로 오름차순이고, 매개변수로 Comparator를 넣으면, 개발자 입맛에 따라 바꿀 수 있다.

TreeMap<Student, Integer> map = new TreeMap<>((o1,o2) -> (return o1.score - o2.score));

Red-black Tree 란?

이진탐색을 보완하여 성능을 개선한 Tree 자료 구조이다. 이진탐색은 일반적으로 O(logN)의 시간복잡도를 가지지만, 데이터가 한쪽으로 치우쳐서, 일자형 Tree가 나올 경우(ex- 계속 작은 값의 데이터만 입력 등) O(n)이라는 시간복잡도가 든다. 이에 비해 Red-black Tree는 부모노드를 기준으로 큰 값은 오른쪽, 작은 값은 외쪽으로 두어, 이상적인 이진트리 모양 형성을 유도한다. 따라서 Red-Black Tree는 삽입, 삭제, 조회 모두에서 O(logN)이라는 시간복잡도를 가진다.

(2) 시간 복잡도

TreeMap은 Red-black Tree로 구현되어서 삽입, 삭제, 조회 모두에서 O(logN)을 보장한다. O(1)인 hashMap보다는 느리지만, 정렬된 map이 필요한 경우에 효율적이다.

(3) 빈출 매소드

#	이름	설명
1	map.firstKey()	정렬 했을 때, 제일 작은 key를 반환
2	map.lastKey()	정렬 했을 때, 제일 큰 key를 반환
3	map.ceilingKey(K key)	매개변수로 넣은 key보다 크거나 같으면서 제일 근접한 값을 반환
4	map.lowerKey(K key)	매개 변수로 넣은 key보다 작거나 같으면서 제일 근접한 값을 반환
5	map.pollFirstEntry()	정렬 했을 때, 제일 작은 key의 EntrySet()을 map에서 삭제 및 반환
6	map.pollLastEntry()	정렬 했을 떄, 제일 큰 key의 EntrySet()을 map에서 삭제 및 반환