[Coding Test] Collection(9)

1. TreeMap

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

레드-블랙 트리(Red-Black Tree)

TreeMap은 이진탐색트리의 문제점을 보완한 레드-블랙 트리(Red-Black Tree)로 이루어져 있다. 일반적인 이진 탐색 트리는 트리의 높이만큼 시간이 필요하다. 값이 전체 트리에 잘 분산되어 있다면 효율성에 있어 크게 문제가 없으나 데이터가 들어올 때 값이 한쪽으로 편향되게 들어올 경우 한쪽 방면으로 크게 치우쳐진 트리가 되어 굉장히 비효율적인 퍼포먼스를 낸다. 이 문제를 보완하기 위해 레드 블랙 트리가 등장하였다. 레드 블랙 트리는 부모 노드보다 작은 값을 가지는 노드는 왼쪽 자식으로, 큰 값을 가지는 노드는 오른쪽 자식으로 배치하여 데이터의 추가나 삭제 시 트리가 한쪽으로 치우쳐지지 않도록 균형을 맞추어준다.

2. TreeMap 사용법

TreeMap 선언

TreeMap<Integer,String> map1 = new TreeMap<Integer,String>();//TreeMap생성
TreeMap<Integer,String> map2 = new TreeMap<>();//new에서 타입 파라미터 생략가능
TreeMap<Integer,String> map3 = new TreeMap<>(map1);//map1의 모든 값을 가진 TreeMap생성
TreeMap<Integer,String> map6 = new TreeMap<Integer,String>(){{//초기값 설정
    put(1,"a");
}};

TreeMap을 생성하기 위해서는 키로 저장할 객체타입과 값으로 저장할 객체 타입을 타입 파라미터로 주고
기본 생성자를 호출하면 된다. 생성하는 명령어는 HashMap과 크게 다르지 않으나 선언 시 크기를 
지정해줄 수는 없다.

TreeMap 값 추가

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

TreeMap은 구조만 HashMap과 다를뿐이지 기본적으로 Map인터페이스를 같이 상속받고 있으므로 기본적인
메소드의 사용법 자체는 HashMap과 동일하다. TreeMap에 값을 추가하려면 put(key, value)
메소드를 사용하면 된다. TreeMap의 타입 파라미터와 같은 타입의 key와 value값을 넣어야 정상적으로
값이 input 되며 만약 입력되는 키 값이 TreeMap 내부에 존재한다면 기존의 값은 새로 입력되는 값으로
대치된다.

TreeMap 값 삭제

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

TreeMap에 값을 제거하려면 remove(key) 메소드를 사용하면 된다. 
오직 키값으로만 TreeMap의 요소를 삭제할 수 있다. 모든 값을 제거하려면 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을 그냥 print하게 되면 {}로 묶어 Map의 전체 key값, value가 출력된다. 
특정 key값의 value를 가져오고 싶다면 get(key)를 사용하면 된다. 그리고 TreeMap은 HashMap과는
달리 Tree구조로 이루어져 있기에 항상 정렬이 되어있어 최솟값, 최댓값을 바로 가져오는 다양한
메소드를 지원한다. firstEntry는 최소 Entry값, firstKey는 최소 Key값, lastEntry는 최대
Entry값, lastKey는 최대 Key값을 리턴한다.

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]:수박

TreeMap의 전체요소를 출력하려면 HashMap과 마찬가지로 entrySet()이나 keySet()메소드를 활용하여
Map의 객체를 반환받은 후 출력하면 된다. entrySet()은 key와 value 모두가 필요할 경우 사용하며
keySet()은 key 값만 필요할 경우 사용하는데 key값만 받아서 get(key)를 활용하여 value도 출력할
수도 있기에 어떤 메소드를 선택하든지 간에 큰 상관이 없어 대부분 코드가 간단한 keySet을 활용하던데
key값을 이용해서 value를 찾는 과정에서 시간이 많이 소모되므로 많은 양의 데이터를 가져와야 한다면
entrySet()이 좋다.(약 20%~200% 성능 저하가 있음)

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]:수박

TreeMap의 전체출력 시 반복문을 사용하지 않고 Iterator를 사용하여도 된다. 
iterator로 Map안의 전체 요소를 출력하는 방법은 위와 같다.