[JAVA] TreeMap 사용법

✨ TreeMap 이란 무엇인가요?

1. TreeMap은 이진트리를 기반으로 한 Map 컬렉션입니다. 
2. 같은 Tree구조로 이루어진 TreeSet과의 차이점은 TreeSet은 그냥 값만 저장한다면 TreeMap은 키와 값이 저장된 Map, Etnry를 저장한다는 점입니다. 
3. TreeMap에 객체를 저장하면 자동으로 정렬되는데, 키는 저장과 동시에 자동 오름차순으로 정렬되고 숫자 타입일 경우에는 값으로, 문자열 타입일 경우에는 유니코드로 정렬합니다. 
4. 정렬 순서는 기본적으로 부모 키값과 비교해서 키 값이 낮은 것은 왼쪽 자식 노드에 키값이 높은 것은 오른쪽 자식 노드에 Map.Etnry 객체를 저장합니다. 
5. TreeMap은 일반적으로 Map으로써의 성능이 HashMap보다 떨어집니다. 
6. TreeMap은 데이터를 저장할 때 즉시 정렬하기에 추가나 삭제가 HashMap보다 오래 걸립니다. 
7. 하지만 정렬된 상태로 Map을 유지해야 하거나 정렬된 데이터를 조회해야 하는 범위 검색이 필요한 경우 TreeMap을 사용하는 것이 효율성면에서 좋습니다.

Red Black Trees

출처 : 링크

 

TreeMap은 이진탐색트리의 문제점을 보완한 레드-블랙 트리(Red-Black Tree)로 이루어져 있습니다.

 

일반적인 이진 탐색 트리는 트리의 높이만큼 시간이 필요합니다.

 

값이 전체 트리에 잘 분산되어 있다면 효율성에 있어 크게 문제가 없으나

 

데이터가 들어올 때 값이 한쪽으로 편향되게 들어올 경우 한쪽 방면으로 크게 치우쳐진 트리가 되어 굉장히 비효율적인 퍼포먼스를 냅니다.

 

이 문제를 보완하기 위해 레드 블랙 트리가 등장하였습니다.

 

레드 블랙 트리는 부모 노드보다 작은 값을 가지는 노드는 왼쪽 자식으로,

 

큰 값을 가지는 노드는 오른쪽 자식으로 배치하여

 

데이터의 추가나 삭제 시 트리가 한쪽으로 치우쳐지지 않도록 균형을 맞추어줍니다.

---

✨ TreeMap 사용법

∙ TreeMap 선언

/* TreeMap생성 */
TreeMap<Integer,String> map1 = new TreeMap<Integer,String>();

/* new에서 타입 파라미터 생략가능 */
TreeMap<Integer,String> map2 = new TreeMap<>();

/* map1의 모든 값을 가진 TreeMap생성 */
TreeMap<Integer,String> map3 = new TreeMap<>(map1);

/* 초기값 설정 */
TreeMap<Integer,String> map6 = new TreeMap<Integer,String>(){{
    put(1,"a");
}};

 

∙ TreeMap 값 추가

/* TreeMap생성 */
TreeMap<Integer,String> map = new TreeMap<Integer,String>();
map.put(1, "사과");//값 추가
map.put(2, "복숭아");
map.put(3, "수박");

 

∙ TreeMap 값 삭제

/* 초기값 설정 */
TreeMap<Integer, String> map = new TreeMap<Integer,String>(){{
    put(1, "사과");//값 추가
    put(2, "복숭아");
    put(3, "수박");
}};
/* key값 1 제거 */
map.remove(1); 

/* 모든 값 제거 */
map.clear();

 

∙ TreeMap 단일 값 출력

TreeMap<Integer,String> map = new TreeMap<Integer,String>(){{//초기값 설정
    put(1, "사과");//값 추가
    put(2, "복숭아");
    put(3, "수박");
}};
		
System.out.println(map); //전체 출력 : {1=사과, 2=복숭아, 3=수박}
System.out.println(map.get(1));//key값 1의 value얻기 : 사과
System.out.println(map.firstEntry());//최소 Entry 출력 : 1=사과
System.out.println(map.firstKey());//최소 Key 출력 : 1
System.out.println(map.lastEntry());//최대 Entry 출력: 3=수박
System.out.println(map.lastKey());//최대 Key 출력 : 3

 

∙ TreeMap 전체 값 출력

TreeMap<Integer,String> map = new TreeMap<Integer,String>(){{//초기값 설정
    put(1, "사과");//값 추가
    put(2, "복숭아");
    put(3, "수박");
}};

//entrySet() 활용
for (Entry<Integer, String> entry : map.entrySet()) {
    System.out.println("[Key]:" + entry.getKey() + " [Value]:" + entry.getValue());
}
//[Key]:1 [Value]:사과
//[Key]:2 [Value]:복숭아
//[Key]:3 [Value]:수박

//KeySet() 활용
for(Integer i : map.keySet()){ //저장된 key값 확인
    System.out.println("[Key]:" + i + " [Value]:" + map.get(i));
}
//[Key]:1 [Value]:사과
//[Key]:2 [Value]:복숭아
//[Key]:3 [Value]:수박

 

∙ Iterator

iterate : (계산, 컴퓨터 처리 절차를) 반복하다
iterator : 반복자

TreeMap의 전체출력 시 반복문을 사용하지 않고 Iterator를 사용할수 있습니다.

TreeMap<Integer,String> map = new TreeMap<Integer,String>(){{//초기값 설정
    put(1, "사과");//값 추가
    put(2, "복숭아");
    put(3, "수박");
}};
		
//entrySet().iterator()
Iterator<Entry<Integer, String>> entries = map.entrySet().iterator();
while(entries.hasNext()){
    Map.Entry<Integer, String> entry = entries.next();
    System.out.println("[Key]:" + entry.getKey() + " [Value]:" +  entry.getValue());
}
//[Key]:1 [Value]:사과
//[Key]:2 [Value]:복숭아
//[Key]:3 [Value]:수박
		
//keySet().iterator()
Iterator<Integer> keys = map.keySet().iterator();
while(keys.hasNext()){
    int key = keys.next();
    System.out.println("[Key]:" + key + " [Value]:" +  map.get(key));
}
//[Key]:1 [Value]:사과
//[Key]:2 [Value]:복숭아
//[Key]:3 [Value]:수박

 

출처 : 링크