검색기능을 강화시킨 컬렉션(TreeSet, TreeMap)

TreeSet클래스

TreeSet 클래스는 데이터가 정렬된 상태로 저장되는 이진 검색 트리(binary search tree)의 형태로 요소를 저장합니다.

이진 검색 트리

트리는 자료 사이의 계층 구조를 나타내는 자료 구조 입니다.

이진 검색 트리는 데이터를 추가하거나 제거하는 등의 기본 동작 시간이 매우 빠릅니다.

좌, 우 child 노드를 참조하기 위한 두 개의 변수로 구성되어 있습니다.

간단한 검색 트리 예제

💡 23, 10, 48, 15, 7, 22, 56

트리생성

)

위와 같이 트리가 자동으로 정렬되면서 생성이 되고, 이를 중위(Inorder) 순회를 하면 오름차순된 결과값을 얻을 수 있습니다. (Left - Root - Right)

👉 7 → 10 → 15 → 22 →23 →48 → 56

public static void main(String[]args) {
        TreeSet<Integer> ts = new TreeSet<>();
        ts.add(23);
        ts.add(10);
        ts.add(48);
        ts.add(15);
        ts.add(7);
        ts.add(22);
        ts.add(56);
        // Enhanced for 문
        for(int e : ts) System.out.println(e + " ");

        // remove()메소드로 요소의 제거
        ts.remove(40);

        // iterator() 메소드를 이용한 요소의 출력
        Iterator<Integer> iter = ts.iterator();
        while(iter.hasNext()) System.out.print(iter.next() + " ");

        // size() 메소드를 이용한 요소의 총 개수
        System.out.println("이진 검색 트리의 크기 : " + ts.size());

        // subSet() 메소드를 이용한 부분 집합의 출력
        System.out.println(ts.subSet(10, 20));
    }

주요 메소드

기능	메소드	설명
특정 객체 검색	Object first()	정렬된 순서에서 첫 번째 객체 반환
	Object last()	정렬된 순서에서 마지막 객체 반환
	Object lower(Object o)	지정된 객체보다 작은 값을 가진 객체 중 제일 가까운 객체 반환, 없으면 null
	Object higher(Object o)	지정된 객체보다 큰 값을 가진 객체 중 제일 가까운 값의 객체 반환, 없으면 null
정렬	NaviableSet descendingSet()	TreeSet 에 저장된 요소들을 역순으로 정렬해서 반환
범위 검색	SortedSet headSet(Object toElement)	지정된 객체보다 작은 값의 객체 반환
	SortedSet tailSet(Object toElement)	지정된 객체보다 큰 값의 객체들을 반환
	SortedSet subSet(Object frontElement, Object toElement)	범위 검색(frontElement ~ to Element사이)의 결과 반환

TreeSet 예제

• int 배열에 5명의 성적을 입력 받아 저장
• TreeSet에 성적을 추가하여 합격점수와 불합격 점수 출력( 합격 기준은 60점)

public static void main(String[]args) {
	Integer[] score = {78, 45, 60, 54, 92};
  TreeSet<Integer> treeSet = new TreeSet<>(Arrays.asList(score));

    System.out.println("60점 이하 : " + treeSet.headSet(60));
    System.out.println("60점 이상 : " + treeSet.tailSet(60));

    // 주어진 점수 보다 바로 아래 점수
    System.out.println("60점 이하 : " + treeSet.lower(60));
    // 주어진 점수 보다 바로 위의 점수
    System.out.println("60점 이상 : " + treeSet.higher(60));
}

TreeMap

Map 인터페이스를 구현한 클래스 중 key 값으로 자료를 정렬하려면 TreeMap을 사용 할 수 있습니다.

TreeMap은 TreeSet과 마찬가지로 이진 검색 트리로 구현 되어 있습니다.

Key 값으로 정렬하므로 key 값에 해당하는 클래스에 Comparable과 Comparator를 구현 해야 합니다.

• 이진 트리 기반의 Map 컬렉션 입니다.
• TreeSet과 차이점은 키와 값이 저장된 Map.Entry를 저장 합니다.
• 기본적으로 부모키값과 비교해 낮은것은 왼쪽에 높은 것으로 오른쪽에 저장 합니다.

• Map 인터페이스 타입 변수에 대입해도 되지만 TreeMap 클래스 타입으로 대입하는 이유는 특정 객체를 찾거나 범위 검색과 관련된 메소드를 사용하기 위함 입니다.

TreeMap<String, Integer> treeMap = new TreeMap<String, Integer>();

리턴 타입	메소드	설명
Map.Entry<K, V>	firstEntry()	제일 낮은 Map.Entry를 리턴
Map.Entry<K, V>	lastEntry()	제일 높은 Map.Entry를 리턴
Map.Entry<K, V>	lowerEntry(K key)	주어진 키보다 바로 아래 Map.Entry를 리턴
Map.Entry<K, V>	higherEntry(K key)	주어진 키보다 바로 위의 Map.Entry를 리턴
Map.Entry<K, V>	floorEntry(K key)	주어진 키와 동등한 키가 있으면 해당 Map.Entry를 리턴, 없다면 주어진 키 바로 아래의 Map.Entry 리턴
Map.Entry<K, V>	ceillingEntry(K key)	주어진 키와 동등한 키가 있으면 해당 Map.Entry를 리턴, 없다면 주어진 키 바로 위의 Map.Entry 리턴
Map.Entry<K, V>	pollFirstEntry()	제일 낮은 Map.Entry를 꺼내오고 컬렉션 제거
Map.Entry<K, V>	pollLast()	제일 높은 Map.Entry를 꺼내오고 컬렉션 제거

public static void main(String[] args) {
    TreeMap<Integer, String> score = new TreeMap<>();
    score.put(87, "나희도");
    score.put(88, "고유림");
    score.put(75, "백이진");
    score.put(65, "구자경");
    score.put(98, "우영우");

    Map.Entry<Integer, String> entry = null;

    entry = score.firstEntry();
    System.out.println("가장 낮은 점수 : " + entry.getKey() + "-" + entry.getValue());

    entry = score.lastEntry();
    System.out.println("가장 높은 점수 : " + entry.getKey() + "-" + entry.getValue());

    entry = score.lowerEntry(95);
    System.out.println("95점 아래 점수 : " + entry.getKey() + "-" + entry.getValue());

    entry = score.higherEntry(95);
    System.out.println("95점 위의 점수 : " + entry.getKey() + "-" + entry.getValue());

    entry = score.floorEntry(95);
    System.out.println("95점 이거나 바로 아래 점수 : " + entry.getKey() + "-" + entry.getValue());

    entry = score.ceilingEntry(95);
    System.out.println("95점 이거나 바로 위의 점수 : " + entry.getKey() + "-" + entry.getValue());

    while(!score.isEmpty()) {
        entry = score.pollFirstEntry();
        System.out.println(entry.getKey() + "-" + entry.getValue() + "남은 객체 수 : " + score.size());
    }
}

내림 차순으로 출력하기

리턴 타입	메소드	설명
NavigableSet	descendingKeySet()	내림차순으로 정렬된 키의 NavigableSet리턴
NavigableMap<K, V>	descendingMap()	내림차순으로 정렬된 Map.Entry의 NavigableMap을 리턴

NavigableMap<Integer, String> descendingMap = score.descendingMap();
Set<Map.Entry<Integer, String>> descendingEntrySet = descendingMap.entrySet();
for(Map.Entry<Integer, String> entry : descendingEntrySet) {
    System.out.print(entry.getKey() + "-" + entry.getValue() + " ");
}
System.out.println();

• Map에 값을 전체 출력하기 위해서는 entrySet(), keySet() 메소드를 사용하면 되는데 entrySet() 메서드는 key와 value의 값이 모두 필요한 경우 사용하고, keySet() 메서드는 key의 값만 필요한 경우 사용합니다.

오름 차순 출력

for(Map.Entry<Integer, String> entry : score.entrySet()) {
    System.out.print(entry.getKey() + "-" + entry.getValue() + " ");
}