[JAVA] 18-2. 이진 트리 컬렉션 종류

1. 트리 컬렉션의 정의

우선 트리(tree)란 각 노드(데이터)가 나무의 뿌리 형태로 하향 구조화 된 알고리즘을 의미하는데요. 이때 각 부모 노드는 최대 두 개의 자식 노드를 가질 수 있는 구조가 바로 이진 트리(binary Tree) 입니다.

이러한 이진 트리의 특성을 활용해 기존의 HashSet과 HashMap 클래스보다 데이터 검색을 용이하게 해낼 수 있도록 설계된 클래스
가 바로 TreeSet과 TreeMap 클래스인 셈이죠.

2. TreeSet이란?

TreeSet 클래스는 앞서 설명한대로 이진 트리 알고리즘을 적용한 Set 컬렉션의 클래스인데요. 각 노드(객체)는 본인을 기준으로 낮은 노드(객체)는 왼쪽에, 높은 노드(객체)는 오른쪽에 정렬
합니다.

특성은 기존의 Set 컬렉션과 마찬가지로 순서가 있고, 중복을 허용하지 않으며, 검색 기능이 강화되었다고 보시면 되겠습니다.

import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        // TreeSet 생성
        TreeSet<Integer> treeSet = new TreeSet<>();

        // 요소 추가
        treeSet.add(1);
        treeSet.add(2);
        treeSet.add(3);
        treeSet.add(4);
        treeSet.add(5);

        // first(): 가장 작은 요소 반환
        System.out.println("First element: " + treeSet.first()); // 출력: 1

        // last(): 가장 큰 요소 반환
        System.out.println("Last element: " + treeSet.last()); // 출력: 5

        // lower(element): 주어진 요소보다 작은 요소 중 가장 큰 요소 반환
        System.out.println("Lower than 2: " + treeSet.lower(2)); // 출력: 1

        // higher(element): 주어진 요소보다 큰 요소 중 가장 작은 요소 반환
        System.out.println("Higher than 2: " + treeSet.higher(2)); // 출력: 5

        // ceiling(element): 3보다 크거나 같은 요소 중 가장 작은 요소 반환
		System.out.println("Ceiling of 3: " + treeSet.ceiling(3)); // 출력: 3

		// floor(element): 3보다 작거나 같은 요소 중 가장 큰 요소 반환
		System.out.println("Floor of 3: " + treeSet.floor(3)); // 출력: 3

		// pollFirst(): 기존의  가장 작은 요소 제거 및 반환
		System.out.println("Poll first element: " + treeSet.pollFirst()); // 출력: 1

		// pollLast(): 기존의 가장 큰 요소 제거 및 반환
		System.out.println("Poll last element: " + treeSet.pollLast()); // 출력: 5

		// headSet(toElement): 3보다 작은 요소들의 부분 집합 반환
		System.out.println("Head set before 3: " + treeSet.headSet(3)); // 출력: [2]

		// tailSet(fromElement): 3보다 크거나 같은 요소들의 부분 집합 반환
		System.out.println("Tail set after 3: " + treeSet.tailSet(3)); // 출력: [3,4]

		// subSet(fromElement, toElement): 2부터 시작해 4 이내의 요소들의 부분 집합 반환 (toElement는 제외)
		System.out.println("Tail set after 3: " + treeSet.subSet(2,4)); // 출력: [2,3]
    }
}

3. TreeMap이란?

TreeMap 클래스 또한 HashMap 클래스에 이진 트리 알고리즘을 적용하여 검색 기능을 강화
한 클래스라고 보시면 되겠는데요.

사용법은 기존의 TreeSet의 기존 메서드들의 이름 뒷부분에 Entry(키와 값 한 쌍), 또는 Key(키만 입력) 키워드를 붙여
주며, 이때 입력되는 매개변수는 키(key)가 됩니다.

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

public class Main {
    public static void main(String[] args) {
        // TreeMap 생성
        TreeMap<Integer, String> treeMap = new TreeMap<>();

        // put(key, value): 요소 추가
        treeMap.put(1, "apple");
        treeMap.put(2, "banana");
        treeMap.put(3, "orange");
        treeMap.put(4, "grape");
        treeMap.put(5, "kiwi");

        // firstKey(): 가장 작은 키 반환
        System.out.println("First key: " + treeMap.firstKey()); // 출력: 1

        // lastKey(): 가장 큰 키 반환
        System.out.println("Last key: " + treeMap.lastKey()); // 출력: 5

        // lowerKey(key): 주어진 키보다 작은 키 중 가장 큰 키 반환
        System.out.println("Lower than 2: " + treeMap.lowerKey(2)); // 출력: 1

        // higherKey(key): 주어진 키보다 큰 키 중 가장 작은 키 반환
        System.out.println("Higher than 2: " + treeMap.higherKey(2)); // 출력: 3

        // ceilingKey(key): 주어진 키와 같거나 큰 키 중 가장 작은 키 반환
        System.out.println("Ceiling of 3: " + treeMap.ceilingKey(3)); // 출력: 3

        // floorKey(key): 주어진 키와 같거나 작은 키 중 가장 큰 키 반환
        System.out.println("Floor of 3: " + treeMap.floorKey(3)); // 출력: 3

        // pollFirstEntry(): 기존의 가장 작은 키와 값 제거 및 반환
        System.out.println("Poll first entry: " + treeMap.pollFirstEntry()); // 출력: 1=apple

        // pollLastEntry(): 기존의 가장 큰 키와 값 제거 및 반환
        System.out.println("Poll last entry: " + treeMap.pollLastEntry()); // 출력: 5=kiwi

        // headMap(toKey): 주어진 키보다 작은 키들의 부분 집합 반환
        System.out.println("Head map before 3: " + treeMap.headMap(3)); // 출력: {2=banana}

        // tailMap(fromKey): 주어진 키보다 크거나 같은 키들의 부분 집합 반환
        System.out.println("Tail map after 3: " + treeMap.tailMap(3)); // 출력: {3=orange, 4=grape}

        // subMap(fromKey, toKey): 주어진 범위에 해당하는 키들의 부분 집합 반환 (toKey는 제외)
        System.out.println("Sub map from 2 to 4: " + treeMap.subMap(2, 4)); // 출력: {2=banana, 3=orange}
    }
}

이러한 TreeMap은 기존의 HashMap의 값 검색 메서드 또한 사용이 가능하기에 이를 활용하여 값만 따로 검색 및 제어하는 것 또한 가능합니다.

String keyToSearch = "banana";
        if (treeMap.containsKey(keyToSearch)) {
            int value = treeMap.get(keyToSearch);
            System.out.println(keyToSearch + "의 값: " + value);
        } else {
            System.out.println(keyToSearch + " 키는 존재하지 않습니다.");
        }

4. TreeSet과 TreeMap의 정렬 방법

앞서 소개해드린 TreeSet과 TreeMap는 자동적으로 정렬을 해주지는 않는데요. 만약 사용자가 해당 클래스가 적용된 객체에 정렬 기능을 추가하고 싶다면 Comparable 인터페이스에 compareTo 메서드 내에서 상속받고 있는 객체의 특성과 속성에 따른 정렬의 기준을 세세히 지정(객체 자체의 정렬법)
해 주거나,

모든 객체에 적용할 수 있는 외부 정렬 기준인 Comparator를 정의
해 각 객체에 지정해주면 됩니다

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

// Comparable을 구현한 클래스
class Person implements Comparable<Person> {
    private String name;
    private int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public int compareTo(Person other) {
        // 나이를 기준으로 오름차순 정렬
        return this.age - other.age;
    }

    @Override
    public String toString() {
        return name + " (" + age + ")";
    }
}

// Comparator를 구현한 클래스
class AgeComparator implements Comparator<Person> {
    @Override
    public int compare(Person p1, Person p2) {
        // 나이를 기준으로 오름차순 정렬
        return p1.getAge() - p2.getAge();
    }
}

public class Main {
    public static void main(String[] args) {
        // Comparable을 사용한 정렬
        List<Person> people = new ArrayList<>();
        people.add(new Person("Alice", 30));
        people.add(new Person("Bob", 20));
        people.add(new Person("Charlie", 25));
       
        // 정렬
        Collections.sort(people);
        System.out.println("Comparable을 사용한 정렬:");
        System.out.println(people);

        // Comparator를 사용한 정렬
        List<Person> people2 = new ArrayList<>();
        people2.add(new Person("Alice", 30));
        people2.add(new Person("Bob", 20));
        people2.add(new Person("Charlie", 25));
      
        // 정렬
        Collections.sort(people2, new AgeComparator());
        System.out.println("Comparator를 사용한 정렬:");
        System.out.println(people2);
    }
}