Java에서 알고리즘 풀이 시 자주 사용하는 Collection들 - TreeSet

들어가며

• 해당 시리즈는 Java에서 알고리즘 풀이 시 자주 사용하는 Collection들 - LinkedList에서 이어진다.
• 이번에는 데이터가 정렬된 상태를 유지하게 하는 자료구조인 Associative Containers에 대하여 알아본다.

2023.01.15 - [Algorithm/Before Check] - Java에서 알고리즘 풀이 시 자주 사용하는 Collection들 - (2)

Java에서 알고리즘 풀이 시 자주 사용하는 Collection들 - (2)

 

 

Associative Containers

• 해당 분류에 포함된 자료구조들은 데이터를 정렬된 상태로 유지하는 특징을 가진다. Red-Black Tree 자료구조를 기반으로 하여 만들어진다
• 해당 자료구조의 데이터 삽입/삭제/접근 연산이 O(logn)에 수행되는 강력한 특성을 가지고 있으나 메모리의 사용이 많기 때문에 메모리 제한이 작은 경우에 사용에 주의해야한다.
• Java에서 Associative Containers로 분류되는 Collection들은 TreeSet, TreeMap이 있다.

 

 

TreeSet

• TreeSet을 알아보기에 앞서 Set이 무엇을 의미하는지에 대하여 정확히 할 필요가 있다.
• Set은 집합 구조로, 순서를 유지하지 않으며 데이터의 중복을 허용하지 않는 자료구조이다.
• TreeSet은 Java에 존재하는 Set인터페이스를 구현한 구현체들 중 하나로 다른 Set으로는 HashSet등이 있다. TreeSet은 위에서 설명한 Red-Black Tree에 기반한 이진 검색 트리(BST)를 이용하여 데이터를 저장한다.
• Associative Containers에 분류되어있는 만큼 자체적으로 데이터가 정렬되고 유지되며 정렬, 검색, 범위검색에 매우 좋은 성능을 보인다.
• TreeSet의 연산은 다음과 같다.

메서드	메서드 타입	설명
TreeSet()	constructor	TreeSet객체를 생성한다.
TreeSet(Collection c)	constructor	컬랙션의 모든 요소를 포함하는 TreeSet객체를 생성한다.
TreeSet(Comparator comp)	constructor	지정된 비교방법을 사용하는 TreeSet객체를 생성한다.
add(E e)	boolean	요소를 TreeSet에 삽입한다.
add(Collection c)	boolean	컬랙션의 모든 요소를 TreeSet에 삽입한다.
ceiling(E e)	E	지정된 객체와 동일한 객체를 반환하고 그 객체가 없다면 객체보다 큰 값을 가진 객체중 가장 가까운 객체 반환
comparator()	Comparator<>	TreeSet이 사용하고 있는 Comparator를 반환한다.
contains(E e)	boolean	요소가 TreeSet에 존재하는지 검사한다.
contains(Collection c)	boolean	컬랙션의 모든 요소가 TreeSet에 존재하는지 검사한다.
descendingSet()	NavigableSet<E>	TreeSet의 모든 요소를 역순으로 정렬하여 반환한다.
first()	E	TreeSet의 첫 번째 요소를 반환한다.
floor()	E	지정된 객체와 동일한 객체를 반환하고 그 객체가 없다면 객체보다 작은 값을 가진 객체중 가장 가까운 객체 반환
headSet(E toElement)	SortedSet<E>	지정된 객체보다 작은 값을 반환한다.
headSet(E toElement, boolean inclusive)	SortedSet<E>	지정된 객체보다 작은 값을 반환한다. inclusive가 true라면 지정된 객체도 포함한다.
higher(E e)	E	지정된 객체보다 큰 값을 가진 객체 중 가장 가까운 객체를 반환한다. 없을 시 null을 반환한다.
last()	E	TreeSet의 마지막 요소를 반환한다.
lower(E e)	E	지정된 객체보다 작은 값을 가진 객체 중 가장 가까운 객체를반환한다. 없을 시 null을 반환한다.
pollFirst()	E	TreeSet의 첫 번째 요소를 제거하고 그 요소를 반환한다.
pollLast()	E	TreeSet의 마지막 요소를 제거하고 그 요소를 반환한다.
remove(E e)	boolean	지정된 객체를 TreeSet에서 삭제한다.
retainAll(Collection c)	boolean	컬랙션에 있는 요소만을 남기고 모든 요소를 삭제한다.
subSet(E fromElement, E toElement)	SortedSet<E>	fromElement 부터 toElement 전까지의 결과를 반환한다.
subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)	NavigableSet<E>	fromElement부터 toElement까지의 결과를 반환한다. fromInclusive가 true라면 시작값이 포함되고 toInclusive가 true라면 끝값이 포함된다.
tailSet(E fromElement)	SortedSet<E>	지정된 객체보다 큰 값의 객체들을 반환한다.
tailSet(E fromElement, boolean inclusive)	NavigableSet<E>	지정된 객체보다 큰 값의 객체들을 반환한다. inclusive가 true라면 지정된 객체도 포함된다.
iterator()	Iterator<E>	TreeSet의 요소를 순회하는 iterator를 반환한다.

• "가깝다"의 정의는 지정된 객체의 값과 차이가 가장 적은 값을 말한다.
• inclusive가 포함되는가 안되는가에 따라 지정된 시작값 또는 끝값이 포함되는 여부가 달라지며 반환형 역시 달라지는것을 유의해야 한다. SortedSet과 NavigableSet은 다른 형임을 유의하자.
• SortedSet과 NavigableSet은 인터페이스로 내부의 값을 정렬하여 유지기키는 기능들을 가진 인터페이스다. NavigableSet은 SortedSet을 확장시킨 인터페이스이다.
• TreeSet이 가진 특징은 contains연산이 O(logN)으로 일반적인 HashSet이나 ArrayList등의 contains연산보다 빠르다는 것이다. 따라서 어떤 요소가 Set에 존재하는지를 파악해야 할 때 정렬된 순서가 필요하다면 TreeSet을, 필요하지 않다면 HashSet을 사용하면 된다. (HashSet은 contains연산이 O(1)이며 이는 이후 Unordered Associative Container에서 살펴본다.)

import java.util.*;

public class StudyCode {
    static TreeSet<Integer> set;
    static NavigableSet<Integer> result;
    static NavigableSet<Integer> result2;

    public static void main(String[] args) throws Exception{
        set = new TreeSet<>();

        for(int i = 1; i<= 10; i++){
            set.add(i);
        }
        set.add(16);
        set.add(17);

        System.out.println(set.floor(11));
        System.out.println(set.ceiling(15));

        result = set.headSet(5, true);
        result2 = set.tailSet(8, true);

        System.out.println(set.contains(10));
        System.out.println(set.contains(12));

        printElement(result);
        System.out.println();
        printElement(result2);

        NavigableSet<Integer> descendingResult = set.descendingSet();

        System.out.println();
        System.out.println(descendingResult);

        NavigableSet<Integer> subset1 = set.subSet(1, true, 6, true);
        NavigableSet<Integer> subset2 = set.subSet(5, true, 17, true);

        printElement(subset1);
        System.out.println();
        printElement(subset2);
    }

    static void printElement(NavigableSet<Integer> data){
        for(int element: data){
            System.out.print(element + " ");
        }
        System.out.println();
    }
}