[Java] 컬렉션 프레임워크 ④

[ 검색 기능을 강화시킨 컬렉션 ]

컬렉션 프레임워크는 검색 기능을 강화시킨 TreeSet과 TreeMap을 제공하고 있다.

TreeSet은 Set 컬렉션이고, TreeMap은 Map 컬렉션이다. 이 컬렉션들은 이진 트리(binary tree)를 이용해서 계층적 구조(Tree 구조)를 가지면서 객체를 저장한다.

1. 이진 트리 구조

이진 트리(binary tree)는 여러 개의 노드가 트리 형태로 연결된 구조로, 루트 노드라고 불리는 하나의 노드에서부터 시작해서 각 노드에 최대 2개의 노드를 연결할 수 있는 구조를 가지고 있다.

• 위아래로 연결된 두 노드를 부모-자식관계에 있다고 하며 위의 노드를 부모 노드, 아래의 노드를 자식 노드라고 한다.
• 하나의 부모 노드는 최대 두 개의 자식 노드와 연결될 수 있다.
• 이진 트리는 부모 노드의 값보다 작은 노드는 왼쪽에 위치시키고, 부모 노드의 값보다 큰 노드는 오른쪽에 위치시킨다.

✅ 이진 트리 값 저장 과정

첫 번째로 저장되는 값은 루트 노드가 되고, 두 번째 값은 루트 노트부터 시작해서 값의 크기를 비교하면서 트리를 따라 내려간다. 작은 값은 왼쪽에, 큰 값은 오른쪽에 저장한다. 숫자가 아닌 문자를 저장할 경우에는 문자의 유니코드 값으로 비교한다. 이렇게 트리를 구성하면, 왼쪽 마지막 노드가 제일 작은 값이 되고 오른쪽 마지막 노드가 가장 큰 값이 된다.

왼쪽 마지막 노드에서부터 오른쪽 마지막 노드까지 왼쪽 노드 → 부모 노드 → 오른쪽 노드 순으로 값을 읽으면 오름차순으로 정렬된 값을 얻을 수 있고, 반대로 오른쪽 마지막 노드에서부터 왼쪽 마지막 노드까지 오른쪽 노드 → 부모 노드 → 왼쪽 노드 순으로 값을 읽으면 내림차순으로 정렬된 값을 얻을 수 있다.

이진 트리가 범위 검색을 쉽게할 수 있는 이유는 값들이 정렬되어 있어 그룹핑이 쉽기 때문이다.

2. TreeSet

TreeSet은 이진 트리를 기반으로 한 Set 컬렉션이다.

• 하나의 노드는 노드값인 value의 왼쪽과 오른쪽 자식 노드를 참조하기 위한 두 개의 변수로 구성된다.
• TreeSet에 객체를 저장하면 자동으로 정렬되는데 부모값과 비교해서 낮은 것은 왼쪽 자식 노드에, 높은 것은 오른쪽 자식 노드에 저장한다.
• TreeSet 클래스는 NavigableSet 인터페이스를 기존의 이진 검색 트리의 성능을 향상시킨 레드-블랙 트리(Red-Black tree)로 구현한다.
• TreeSet 클래스는 Set 인터페이스를 구현하므로, 요소를 순서에 상관없이 저장하고 중복된 값은 저장하지 않는다.

✅ TreeSet 생성 방법

TreeSet을 생성하기 위해서는 저장할 객체 타입을 파라미터로 표기하고 기본 생성자를 호출하면 된다.

TreeSet<E> treeSet = new TreeSet<E>();

• String 객체를 저장하는 TreeSet은 다음과 같이 생성할 수 있다.

TreeSet<String> treeSet = new TreeSet<String>();

✅ TreeSet 검색 관련 메소드

Set 인터페이스 타입 변수에 대입해도 되지만 TreeSet 클래스 타입으로 대입한 이유는 객체를 찾거나 범위 검색과 관련된 메소드를 사용하기 위해서이다. 다음은 TreeSet이 가지고 있는 검색 관련 메소드들이다.

✅ 예제 | 특정 객체 찾기

import java.util.TreeSet;

public class TreeSetExample {
    public static void main(String[] args) {
        TreeSet<Integer> scores = new TreeSet<Integer>();
        scores.add(87);
        scores.add(98);
        scores.add(75);
        scores.add(95);
        scores.add(80);

        Integer score = null;

        score = scores.first();
        System.out.println("가장 낮은 점수: " + score);

        score = scores.last();
        System.out.println("가장 높은 점수: " + score + "\n");

        score = scores.lower(95);
        System.out.println("95점 아래 점수: " + score);

        score = scores.higher(95);
        System.out.println("95점 위의 점수: " + score + "\n");

        score = scores.floor(95);
        System.out.println("95점 이거나 바로 아래 점수: " + score);

        score = scores.ceiling(95);
        System.out.println("95점 이거나 바로 위의 점수: " + score + "\n");

        while (!scores.isEmpty()) {
            score = scores.pollFirst();
            System.out.println(score + " (남은 객체 수: " + scores.size() + ")");
        }
    }
}

• 실행 결과

가장 낮은 점수: 75
가장 높은 점수: 98

95점 아래 점수: 87
95점 위의 점수: 98

95점 이거나 바로 아래 점수: 95
95점 이거나 바로 위의 점수: 95

75 (남은 객체 수: 4)
80 (남은 객체 수: 3)
87 (남은 객체 수: 2)
95 (남은 객체 수: 1)
98 (남은 객체 수: 0)

✅ TreeSet 정렬 관련 메소드

• descendingIterator() 메소드는 내림차순으로 정렬된 Iterator 객체를 리턴한다.
• descendingSet() 메소드는 내림차순으로 정렬된 NavigableSet 객체를 리턴한다.
  • NavigableSet은 TreeSet과 마찬가지로 first(), last(), lower(), higher(), floor(), ceiling() 메소드를 제공하고, 정렬 순서를 바꾸는 descendingSet() 메소드도 제공한다.
• 오름차순으로 정렬하고 싶다면 다음과 같이 descendingSet() 메소드를 두 번 호출하면 된다.

NavigableSet<E> descendingSet = treeSet.descendingSet();
NavigableSet<E> ascendingSet = descendingSet.descendingSet();

✅ TreeSet 범위 검색 관련 메소드

세 가지 메소드 중에서 subSet() 메소드의 사용 방법을 자세히 살펴보도록 하자. subSet() 메소드는 네 개의 매개 변수가 있는데, 시작 객체와 끝 객체, 그리고 이 객체들을 포함할지 여부의 boolean 값을 받는다.

NavigableSet<E> set = treeSet.subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)

• E fromElement: 시작 객체
• boolean fromInclusive: 시작 객체의 포함 여부
• E toElement: 끝 객체
• boolean toInclusive: 끝 객체의 포함 여부

---

[ 참고자료 ]

이것이 자바다 책
http://tcpschool.com/java/java_collectionFramework_set