트리 맵(Tree Map)

Ouroboros·2023년 11월 11일

Tree Map 맵 자료구조 트리 트리맵

자료구조

목록 보기

13/13

자바는 배열이 크기가 고정되어 있고 삽입 삭제가 오래걸린다는 단점을 보완하기 위해 1)동적배열 개념인 Collection Framework를 제공한다.
대표적인 종류가 List, Set, Map이다.

[LIST,MAP,SET 설명 더보기]

0. Map

Key 값과 Value 값을 관리해주는 컬렉션이다.
Key값은 데이터 중복을 허용하지 않지만, Value 값은 데이터 중복을 허용한다.

Map<String, String> map = new HashMap<String, String>();

map.put("key1", "value1");
map.put("key2", "value2");

System.out.println(map.get("key1"));

"key1"이라는 Key 값과 "value1"이라는 Value 값을 갖는 Entry가 HashMap 내부에 put() 메소드를 통해 저장된다. 해당 값을 가져올 때에는 get() 메소드를 활용해서 Key 값인 "key1"라는 문자열만 넘겨주면 Value 값을 얻어올 수 있는 형태의 컬렉션이다.

MAP 종류와 비교

	종류	순서	데이터 중복
Map	HashMap	x	Key: x / Value: o
	LinkedHashMap	o	Key: x / Value: o
	TreeMap	x 입력순서는 유지하지 않으나, 입력된 key의 데이터에 따라 정렬되어 저장	Key: x / Value: o

Tree Map

Tree Map 이란?

Tree Map은 내부에 레드-블랙 트리(Red-Black Tree)의 자료구조를 이용한다.
Tree set 과 다른 점은 Tree set은 값만 저장한다면,
Tree Map은 키와 값이 저장된 Map, Entry를 저장한다.
TreeMap에 객체를 저장하면 자동으로 정렬되며, 설정하지 않는다면 key는 저장되면서 자동으로 오름차순으로 정렬된다.
하지만 Key 값으로 사용할 클래스에 Comparator 인터페이스를 구현하면 사용자가 정렬된 순서를 조정할 수 있다.
기본적으로 부모 키값과 비교해서 키 값이 낮은 것은 왼쪽 자식 노드에 키 값이 높은 것은 오른쪽 자식 노드에 저장 한다.

Tree Map 장단점

Tree Map은 저장할 때 정렬하기 때문에 추가나 삭제할 때 Hash Map보다 시간이 걸린다.
정렬된 데이터를 조회해야 할 때 TreeMap이 더 효율적 이다.

Tree Map 코드

1) TreeMap 선언

import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

  
TreeMap<String, String> map = new TreeMap<String, String>(); // String, String 타입 설정

Java에서 TreeMap을 선언 하려면 java.util.TreeMap을 import 한 뒤,
HashMap map = new HashMap<>(); 과 같은 형식으로 선언 한다.
key, value 모두 String이면, String, String으로 설정해준다.

2) TreeMap 값 추가

TreeMap<String, String> map = new TreeMap<String, String>(); // String, String 타입 설정

map.put("1", "Java"); 
map.put("2", "Oracle"); 
map.put("3", "SQL"); 
map.put("4", "Spring"); 

System.out.print(map); // {1=Java, 2=Oracle, 3=SQL, 4=Spring}

HashMap<'타입','타입'> 에 맞춰서(예시에서는 String, String) key, value 값에 값을 넣는다.
Map은 모두 put(key, value) 메소드를 사용해 값을 추가한다.

3) TreeMap 값 삭제

TreeMap<String, String> map = new TreeMap<String, String>(); // String, String 타입 설정

map.put("1", "Java"); 
map.put("2", "Oracle"); 
map.put("3", "SQL"); 
map.put("4", "Spring"); 

map.remove("3);

System.out.print(map); // {1=Java, 2=Oracle, 4=Spring}

remove(key) 메소드를 사용해서 key를 삭제한다.
만약 clear() 메소드를 사용하면 HashMap의 모든 키 값을 삭제된다.

4) TreeMap 출력

TreeMap<String, String> map = new TreeMap<String, String>(); // String, String 타입 설정

map.put("1", "Java"); 
map.put("2", "Oracle"); 
map.put("3", "SQL"); 
map.put("4", "Spring"); 

System.out.print(map); // 전체 출력 : {1=Java, 2=Oracle, 3=SQL, 4=Spring}
System.out.println(map.get(1));// -> Java
System.out.println(map.firstEntry());// -> 1=Java
System.out.println(map.firstKey());//-> 1
System.out.println(map.lastEntry());//->4=Spring
System.out.println(map.lastKey());//->4

TreeMap은 HashMap과는 달리 Tree구조로 이루어져 있기에 항상 정렬이 되어 있다.
따라서 최솟값, 최댓값을 바로 가져오는 다양한 메소드를 지원한다.
firseEntry는 최소 Entry값(예시: 1=Java), fisrtKey는 최소 key값(1), lastEntry는 최대 Entry값(4=Spring), lastKey는 최대 key값(4)을 리턴한다.

5) TreeMap 전체 출력

TreeMap<String, String> map = new TreeMap<String, String>(); // HashMap 선언 

map.put("1", "Java"); 
map.put("2", "Oracle"); 
map.put("3", "SQL"); 
map.put("4", "Spring"); 

for(Map.Entry<String, String> e : map.entrySet()) {
	System.out.println("Key : " + e.getKey() + ", Value : " + e.getValue());
}