자바(Java) - 컬렉션 프레임워크(4) 검색 기능을 강화 시킨 컬렉션(TreeSet, TreeMap)

TreeSet<E> 클래스

• 데이터가 정렬된 상태로 저장되는 이진 검색 트리(binary search tree)의 형태로 요소를 저장

이진 검색 트리

• 트리는 자료사이의 계증 구조를 나타내는 자료 구조 입니다.
• 데이터를 추가하거나 제거하는 등의 기본 동작 시간이 매우 빠릅니다.
• 자식노드는 0,1,2개만 가질 수 있습니다.

간단한 검색 트리 예제

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

트리 생성

루트(root)-23 를 기준으로 root 보다 작으면 왼쪽, 크면 오른쪽으로 배치됩니다.

10은 23보다 작으므로 왼쪽, 48은 10보다 크므로 오른쪽

15는 23보다 작으므로 왼쪽, 10보다 크므로 오른쪽

7은 23보다 작으므로 왼쪽, 10보다 작으므로 왼쪽

48은 23보다 크므로 오른쪽

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

7 -> 10 -> 15 -> 22 -> 48 -> 56

🐶기본 예제1

import java.util.Iterator;
import java.util.TreeSet;

public class Main {
    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);
        for(Integer e : ts) System.out.print(e + " ");
        ts.remove(48); // 매개변수로 전달한 요소를 제거
        System.out.println();
        
        // iterator() 로 순회 : 반복자 (향상된 for문이 나오기 이전에 표준으로 사용하던 방식
        Iterator<Integer> iterator = ts.iterator();
        while(iterator.hasNext()) {
            System.out.print(iterator.next() + " ");
        }
        
        // 요소의 갯수
        System.out.println("크기 : " + ts.size());
    }
}

🐶기본 예제2

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

        System.out.println("60점 미만 : " + ts.headSet(60));
        System.out.println("60점 이상 : " + ts.tailSet(60));
        // 주어진 점수 바로 아래의 점수 출력
        System.out.println("60점 바로 아래 점수 : " + ts.lower(60));
        // 주어진 점수 바로 위의 점수 출력
        System.out.println("60점 바로 위 점수 : " + ts.higher(60));
    }
}

TreeMap

• Map 인터페이스를 구현한 클래스 중 키 값으로 자료를 정렬하려면 TreeMap을 사용하면 됩니다.
• TreeMap도 TreeSet과 마찬가지로 이진 검색 트리(값이 추가 될 때 자동정렬)로 구현 되어 있습니다.
• TreeMap은 키 값으로 정렬하므로 키 값에 해당하는 Comparable과 Comparator를 구현해야 합니다.
• TreeSet과의 차이점은 키와 값이 저장된 Map.Entry를 저장합니다.

import java.util.Map;
import java.util.TreeMap;

public class Main {
    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());
    }
}