TreeMap

이미지 출처 : 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;
        });

이렇게 바꾸면 좀 더 심플한 코드가 된다.