[Java] TreeMap

 

1. TreeMap이란?

- 이진 탐색 트리(binary search tree)의 일종인 'Red-Black Tree'를 기반으로 하는 ‘key = entry’ 형식의 Map 컬렉션이다.

---

Red-Black Tree

- 일반적인 Tree 형태의 자료구조에서는 Tree의 높이가 클수록 데이터의 탐색시간이 길어진다. 또한, 데이터가 한쪽으로만 입력되어 치우진 구조가 된다면 전체 효율이 매우 떨어질 수 있다. 이를 보완하여 고안된 것이 Red-Black Tree이다. Red Black Tree의 주요 특징은 Root를 기준으로 작은 값은 왼쪽 서브 노드에, 더 큰 값을 오른쪽 서브 노드에 배치한다는 것이다. 복잡한 자료구조이긴 하나, 실사용에서 효율적이기 때문에 최악의 상황에서도 우수한 실행 시간을 담보할 수 있다는 장점을 가지고 있다. TreeMap은 Red-Black Tree 구조에 기반해있다.

출처 :  https://upload.wikimedia.org/wikipedia/commons/6/66/Red-black_tree_example.svg

 

---

- SortedMap의 구현체로, 내부적으로 SortedMap 인터페이스를 상속하고 있다.

- HashMap과의 가장 큰 차이점은 Map 객체에 있는 데이터가 자동으로 정렬된다는 점이다.

- 기본 정렬 작업을 포함하고 있어서, HashMap보다는 성능이 상대적으로 떨어진다.

- 숫자, 문자 모두 오름차순으로 자동 정렬된다.

 

TreeMap 관련 메소들을 알아보기 위해, Junit 테스트 클래스를 하나 만들었다.

우선 ‘key(Integer):value(String)' 형태의 TreeMap 객체를 만든 후, 무작위로 7개의 Entry를 삽입했다.

단, 삽입되는 Entry의 Key 순서는 전혀 상관하지 않지 않았다.

import java.util.TreeMap;

import org.junit.jupiter.api.Test;
import org.junit.jupiter.api.TestInstance;
import org.junit.jupiter.api.TestInstance.Lifecycle;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import org.springframework.boot.test.context.SpringBootTest;

@SpringBootTest
@TestInstance(Lifecycle.PER_METHOD)
class TreeMapTest {
	
private static final Logger log = LoggerFactory.getLogger(TreeMapTest.class);

	
@Test
public void treeMapIsSortableTest() {
	
	TreeMap<Integer, String> tmap = new TreeMap<>();
	
	tmap.put(5, "test5");
	tmap.put(1, "test1");
	tmap.put(2, "test2");
	tmap.put(3, "test3");
	tmap.put(4, "test4");
	tmap.put(6, "test6");
	tmap.put(9, "test9");

    log.info("tmap : {}", tmap);
	
   }
}

 

테스트 케이스를 돌려 로그를 찍어본 결과, key의 오름차순으로 출력됨을 확인할 수 있었다.

tmap : {1=test1, 2=test2, 3=test3, 4=test4, 5=test5, 6=test6, 9=test9}

 

 

2. TreeMap의 선언

- 일반적인 객체 선언 방식뿐만 아니라 이미 생성되어 있는 TreeMap 객체를 인자로 받아서도 생성할 수 있다.

TreeMap<String, Integer> tmap = new TreeMap<>();
TreeMap<String, Integer> tmp2 = new TreeMap<>(tmap);

 

- Entry의 key를 어떤 기준으로 비교할지를 정해주는 'Compator' 인터페이스 객체를 별도로 정의했다면, 그것을 인자로 사용할 수도 있다.

Comparator<Integer> comp = new Comparator<Integer>() {
		
      @Override
		public int compare(Integer o1, Integer o2) {
			return o2-o1;
		}
	};

TreeMap<String, Integer> tmap = new TreeMap<>(comp);

 

 

3. 관련 메소드

① keySet() - return Set<?>

→ TreeMap 객체에 있는 key들을 집합체(Set)로 리턴한다.

log.info("tmap.keySet() : {}", tmap.keySet());  
// tmap.keySet() : [1, 2, 3, 4, 5, 6, 9]

 

 

② values() - return Collection<V>

→ TreeMap 객체에 있는 value들을 Collection 객체로 리턴한다.

log.info("tmap.values() : {}", tmap.values());  
// tmap.values() : [test1, test2, test3, test4, test5, test6, test9]

 

 

③ lowerEntry(key) - return Map.Entry<K,V>

lowerKey(key) - return K

→ (lowerEntry) 인자로 받은 key보다 작은 값을 key로 가지고 있는 Entry들 중, 가장 높은 값의 key를 가지고 있는 Entry를 리턴한다. 만약 값이 없으면 null을 return 한다.

→ (lowerKey) 상기 Entry의 key만 리턴한다.

log.info("tmap.lowerEntry(4) : {}", tmap.lowerEntry(4));
// tmap.lowerEntry(4) : 3=test3

 

 

④ floorEntry(key) - return Map.Entry<K,V>

floorKey(key) - return K

→ (floorEntry) 인자로 받은 key와 같거나 작은 값을 key로 가지고 있는 Entry들 중, 가장 높은 값의 key를 가지고 있는 Entry를 리턴한다. 만약 값이 없으면 null을 return 한다.

→ (floorKey) 상기 Entry의 key만 리턴한다.

log.info("tmap.floorEntry(4) : {}", tmap.floorEntry(4));
// tmap.floorEntry(4) : 4=test4
log.info("tmap.floorKey(4) : {}", tmap.floorKey(4));
// tmap.floorKey(4) : 4

 

 

⑤ ceilingEntry(key) - return Map.Entry<K,V>

ceilingKey(key) - return K

→ (ceilingEntry) 인자로 받은 key와 같거나 작은 값을 key로 가지고 있는 Entry들 중, 가장 높은 값의 key를 가지고 있는 Entry를 리턴한다. 만약 값이 없으면 null을 return 한다.

→ (ceilingKey) 상기 Entry의 key만 리턴한다.

log.info("tmap.ceilingEntry(4) : {}", tmap.ceilingEntry(4));
// tmap.ceilingEntry(4) : 4=test4
log.info("tmap.ceilingKey(4) : {}", tmap.ceilingKey(4));
// tmap.ceilingEntry(4) : 4

 

 

⑥ firstEntry() - return Map.Entry<K,V>

firstKey() - return K

→ (firstEntry) TreeMap 객체에 들어있는 첫 번째 Entry를 리턴한다.

→ (firstKey) 상기 Entry의 key만 리턴한다.

log.info("tmap.firstEntry() : {}", tmap.firstEntry());
// tmap.firstEntry() : 1=test1
log.info("tmap.firstKey() : {}", tmap.firstKey());
// tmap.firstKey() : 1

 

 

⑦ lastEntry() - return Map.Entry<K,V>

→ (lastEntry) TreeMap 객체에 들어있는 가장 마지막 Entry를 리턴한다.

→ (lastKey) 상기 Entry의 key만 리턴한다.

log.info("tmap.lastEntry() : {}", tmap.lastEntry());
// tmap.lastEntry() : 9=test9
log.info("tmap.lastKey() : {}", tmap.lastKey());
// tmap.lastKey() : 9

 

⑧ descendingMap() - return NavigableMap<K,V>

→ TreeMap 객체에 들어있는 Entry들을 내림차순으로 정렬하여 Map(NavigableMap) 객체로 리턴한다.

log.info("tmap.descendingMap() : {}", tmap.descendingMap());
// tmap.descendingMap() : {9=test9, 6=test6, 5=test5, 4=test4, 3=test3, 2=test2, 1=test1}

 

⑨ descendingKeySet() - return NavigableSet<K>

→ TreeMap 객체에 들어있는 Entry들의 key를 내림차순으로 정렬하여 Set(NavigableSet) 객체로 리턴한다.

log.info("tmap.descendingKeySet() : {}", tmap.descendingKeySet());
// tmap.descendingKeySet() : [9, 6, 5, 4, 3, 2, 1]

 

 

지금까지 자바의 TreeMap 인터페이스에 대해 알아보았다.

 

감사합니다 : )