이미지 출처 : https://adrianmejia.com/data-structures-for-beginners-trees-binary-search-tree-tutorial/
트리구조.
TreeMap
이미지 출처 : https://www.java8net.com/2020/02/treemap-in-java.html
TreeMap은 이름에서 알다시피 이진검색트리 형태에 key와 value 쌍으로 이루어진 데이터를 저장한다.
- 검색과 정렬에 적합한 컬렉션 클래스다.
범위 검색은 TreeMap이 성능이 좋지만, 그게 아니라면 검색 부분에서는 HashMap 성능이 더 좋다.
TreeMap의 메서드
| method | 설명 |
|---|---|
| TreeMap(Comparator c) | 지정한 Comparator를 기준으로 정렬하는 객체 생성 |
| TreeMap(Map m) | 주어진 Map에 저장된 요소를 포함하는 객체 생성 |
| TreeMap(SortedMap m) | 주어진 SortedMap에 저장된 모든 요소를 포함하는 객체 생성 |
| Map.Entry ceilingEntry(Object key) | 지정한 key와 일치하거나, 큰 것 중 제일 작은 Map.Entry(key-value) 반환. 없으면 null. |
| Object ceilingKey(Object key) | 지정한 key와 일치하거나 큰 것중 제일 작은 key를 반환. 없으면 null |
| void clear() | 모든 객체 삭제 |
| Object clone() | 현재 객체를 복제해서 반환 |
| Comparator comparator() | TreeMap의 정렬기준이 되는 Comparator를 반환. Comparator가 지정되지 않았다면 null |
| boolean containsKey(Object key | TreeMap에 지정한 key가 포함되어 있는지 확인 |
| boolean containsValue(Object value) | 지정한 value를 포함하는지 확인 |
| NavigableSet descendingKeySet() | 저장된 키를 역순으로 정렬해서 NavigableSet으로 반환 |
| Set entrySEt() | 엔트리(key+value)를 (Set타입)반환 |
| Map.entry firstEntry() | 첫 번째(가장 작은) key-value를 반환 |
| Object firstKey() | 첫 번째(가장 작은) key를 반환 |
| Map.Entry floorEntry(Object key) | 지정한 key와 일치하거나 작은 것 중에 제일 큰 key의 key-value를 반환. |
| Object floorKey(Object key) | 지정한 key와 일치하거나 작은 것 중, 제일 큰 키를 반환. |
| Object get(Object key) | 지정한 key의 value를 반환 |
| SortedMap headMap(Object toKey) | TreeMap에 저장된 첫 번째 요소부터 지정한 범위에 속한 모든 요소가 담긴 SortedMap을 반환. (toKey 포함) |
| NavigableMap headMap(Object toKey, boolean inclusive) | TreeMap에 저장된 첫 번째 요소부터 지정한 범위toKey에 속한 모든 요소가 담긴 SortedMap을 반환. inclusive가 true면 toKey도 포함 |
| Map.Entry highherEntry(Object key | 지정한 key보다 큰 키 중에서, 제일 작은 key-value를 반환. |
| Object higherKey(Object key) | 지정한 key보다 큰 키 중에서 제일 작은 key-value를 반환 |
| boolean isEmpty() | 객체가 비었는지 확인 |
| Set keySet() | 객체에 저장된 모든 key를 포함하는 Set반환 |
| Map.Entry lastEntry() | 객체에 저장된 마지막 key(가장 큰 키)-value 반환 |
| Object lastKey() | TreeMap에 저장된 마지막 키(가장 큰 키)를 반환 |
| Map.Entry lowerEntry(Object key) | 지정한 key보다 작은 key중에서 제일 큰 key-value를 반환 |
| Object lowerKey(Object key) | 지정한 key보다 작은 key중에서 제일 큰 key-value를 반환 |
| NavigableSet navigableKeySet() | 모든 key가 담긴 NavigableSet을 반환 |
| Map.Entry().pollFirstEntry() | 객체에서 제일 작은 key를 제거하면서 반환 |
| Map.Entry().pollLastEntry() | 객체에서 제일 큰 key를 제거하면서 반환 |
| Object put(Object key, Object value) | 지정한 key, value를 저장 |
| void putAll(Map map) | 지정한 Map에 포함된 모든 요소를 저장 |
| Object remove(Object key) | 지정한 key로 저장된 객체key-value를 제거 |
| Object replace(Object k,Object v) | 기존의 key(k)의 value를 새로운 value(v)로 변경 |
| boolean replace(Object key, Object oldValue, Object newValue) | 기존의 key의 value를 새로운 newValue로 변경. 단, 기존의 value와 oldValue가 일치해야 함. |
| int size() | 저장된 객체의 수 반환 |
| NavigableMap subMap(Object fromKey, boolean fromInclusive, Object toKey, boolean toInclusive) | 지정한 두 개의 키 사이에 있는 모든 요소가 담긴 NavagableMap반환. fromInclusive, toInclusive가 true면 범위에 포함. |
| SortedMap subMap(Object fromKey, Object toKey) | 지정한 키 사이에 있는 모든 요소가 담긴 SortedMap반환. (toKey 미포함) |
| SortedMap tailMap(Object fromKey) | 지정한 키부터 마지막 요소까지 반환 |
| NavigableMap(Object fromKey, boolean inclusive) | 지정한 키부터 마지막 요소까지 반환. inclusive가 true면 fromKey 포함. |
| Collection values() | 저장된 모든 객체를 Collecton타입으로 반환 |
package com.javaex.ch11;
import java.util.*;
public class TreeMapEx1 {
public static void main(String[] args) {
String[] data = {"A", "K", "A", "K", "D","K","A","K","K","K","K","Z","D"};
TreeMap map = new TreeMap();
for (int i = 0; i < data.length; i ++) {
if(map.containsKey(data[i])) {
Integer value = (Integer)map.get(data[i]);
map.put(data[i],value+1);
} else {
map.put(data[i], 1);
}
}
Iterator iterator = map.entrySet().iterator();
System.out.println("==기본정렬==");
while (iterator.hasNext()) {
Map.Entry entry = (Map.Entry)iterator.next();
int value = ((Integer)entry.getValue()).intValue();
System.out.println(entry.getKey() + " : " + printBar('#', value) + " " + value);
}
System.out.println();
//map -> ArrayList -> Collections.sort() 정렬
Set set = map.entrySet();
List list = new ArrayList(set);
//static void sort(List list, Comparator c)
Collections.sort(list, new Comparator() { //익명클래스
@Override
public int compare(Object o1, Object o2){
if(o1 instanceof Map.Entry && o2 instanceof Map.Entry) {
Map.Entry entry1 = (Map.Entry) o1;
Map.Entry entry2 = (Map.Entry) o2;
int value1 =((Integer)entry1.getValue()).intValue();
int value2 =((Integer)entry2.getValue()).intValue();
return value2 - value1;
}
return -1;
}
});
iterator = list.iterator();
System.out.println("==값의 크기가 큰 순서로 정렬==");
while(iterator.hasNext()){
Map.Entry entry = (Map.Entry)iterator.next();
int value = ((Integer)entry.getValue()).intValue();
System.out.println(entry.getKey() + " : " + printBar('#',value) + " " + value);
}
} //main()
public static String printBar(char ch, int value) {
char[] bar = new char[value];
for(int i = 0; i < bar.length; i ++) {
bar[i] = ch;
}
return new String(bar);
}
}
위 예제는 HashMap을 이용한 예제를 TreeMap으로 변경한 것이다. String클래스에 정의된 기본 정렬과, Comparator를 구현한 정렬을 비교한 것이다.
참고로 익명클래스를 이용해 구현한 부분은 람다를 이용해 조금 더 간단히 쓸 수 있다.
Collections.sort(list, (Object o1, Object o2) -> { //람다
if(o1 instanceof Map.Entry && o2 instanceof Map.Entry) {
Map.Entry entry1 = (Map.Entry) o1;
Map.Entry entry2 = (Map.Entry) o2;
int value1 =((Integer)entry1.getValue()).intValue();
int value2 =((Integer)entry2.getValue()).intValue();
return value2 - value1;
}
return -1;
});이렇게 바꾸면 좀 더 심플한 코드가 된다.
