[Java] TreeSet 주요 메소드 살펴보기

 

---

TreeSet ? 

- Java Collection Framework 제공하는 자료구조

- 이진 탐색 트리(binary search tree)로 구현 

- 시간복잡도 : O(logN)  (HashSet의 경우 O(1))

- 범위 탐색과 정렬에 유리 

- Collection, Set 에서 제공하는 기본 메소드 또한 사용 가능

- 중복 허용 X

- null 허용 X (NPE 발생)

- 정렬 기준의 경우 객체의 Comparable이나 TreeSet 생성자에 Comparator 초기화하여 사용

- thread-safe 하지 않다

 

생성자

- 내부적으로 Map 자료 구조를 사용하고, 아래와 같이 생성자를 제공한다 

- 인자가 없는 기본 생성자를 사용할 경우 TreeMap으로 생성된다

private transient NavigableMap<E,Object> m;
private static final Object PRESENT = new Object();

public TreeSet() {
    this(new TreeMap<>());
}

public TreeSet(Comparator<? super E> comparator) {
    this(new TreeMap<>(comparator));
}

public TreeSet(Collection<? extends E> c) {
    this();
    addAll(c);
}

public TreeSet(SortedSet<E> s) {
    this(s.comparator());
    addAll(s);
}

---

주요 메서드

참고. Baeldung 

https://www.baeldung.com/java-tree-set

A Guide to TreeSet in Java | Baeldung

 

 

테스트 데이터 초기화 

간단히 1 ~ 10까지 오름차순, 내림차순 정렬한 데이터 준비

private TreeSet<Integer> numberSet; // 1, 2, .., 10
private TreeSet<Integer> reverseNumberSet; // 10, 9, .., 1

@BeforeEach
void setUp() {
    numberSet = new TreeSet<>();
    numberSet.addAll(IntStream.rangeClosed(1, 10).boxed().collect(Collectors.toList()));

    reverseNumberSet = new TreeSet<>(Comparator.reverseOrder());
    reverseNumberSet.addAll(IntStream.rangeClosed(1, 10).boxed().collect(Collectors.toList()));
}

 

 

1. first()

첫 번째 요소를 반환하다 (제거 x)

@Test
void first() {
    assertThat(numberSet.first()).isEqualTo(1);
    assertThat(numberSet).hasSize(10);
}

 

 

참고. pollFirst()의 경우 첫 번째 요소를 반환하면서 Set에서 제거한다

@Test
void pollFirst() {
    assertThat(numberSet.pollFirst()).isEqualTo(1);
    assertThat(numberSet).hasSize(9); // 2, 3, 4, 5, 6, 7, 8, 9, 10
}

 

 

2. last()

마지막 요소를 반환한다 (제거 x)

@Test
void last() {
    assertThat(numberSet.last()).isEqualTo(10);
    assertThat(numberSet).hasSize(10);
}

 

 

참고. pollLast()의 경우 마지막 요소를 반환하면서 Set에서 제거한다

@Test
void pollLast() {
    assertThat(numberSet.pollLast()).isEqualTo(10);
    assertThat(numberSet).hasSize(9);
}

 

 

3. higher(E e)

- 지정한 값보다 큰 값(초과)을 가진 요소 중 제일 가까운 값의 요소를 반환(인자값 미포함)

- 없으면 null 반환

@Test
void higher() {
    int result = numberSet.higher(5);
    assertThat(result).isEqualTo(6);
    assertThat(numberSet).hasSize(10);
}

 

 

역순 정렬(내림차순)일 때 4를 반환한다

@Test
void higherByReverseOrder() {
    int result = reverseNumberSet.higher(5);
    assertThat(result).isEqualTo(4);
    assertThat(reverseNumberSet).hasSize(10);
}

 

 

4. lower(E e)

- 지정한 값보다 작은 값(미만)을 가진 요소 중 제일 가까운 값의 요소를 반환(인자값 미포함)

- 없으면 null 반환

@Test
void lower() {
    int result = numberSet.lower(5);
    assertThat(result).isEqualTo(4);
    assertThat(numberSet).hasSize(10);
}

 

역순 정렬(내림차순)일 때 6를 반환한다

@Test
void lowerByReverseOrder() {
    int result = reverseNumberSet.lower(5);
    assertThat(result).isEqualTo(6);
    assertThat(reverseNumberSet).hasSize(10);
}

 

5. ceiling(E e)

지정한 값 이상의 요소 중 가장 작은 요소 (인자값 포함)

@Test
void ceiling() {
    numberSet.add(12); // 1 ~ 10, 12

    int result = numberSet.ceiling(11); // 인자값 12이면 12 반환
    assertThat(result).isEqualTo(12);
    assertThat(numberSet).hasSize(11);
}

 

 

6. floor(E e)

지정한 값 이하의 요소 중 가장 큰 요소 (인자값 포함)

@Test
void floor() {
    numberSet.add(12); // 1 ~ 10, 12

    int result = numberSet.floor(11); // 인자값 12이면 12 반환
    assertThat(result).isEqualTo(10);
    assertThat(numberSet).hasSize(11);
}

 

 

 

7. subSet(E from, E to)

from ~ to 범위 검색 결과 반환, 이때 to는 exclusive(제외)

@Test
void subSet() {
    SortedSet<Integer> subSet = numberSet.subSet(3, 6);

    assertThat(subSet).hasSize(3)
            .containsExactly(3, 4, 5);
    assertThat(numberSet).hasSize(10);
}

 

 

8. headSet(E to) 

주어진 값보다 작은 요소들을 반환한다, 이때 to는 exclusive (제외)

@Test
void headSet() {
    SortedSet<Integer> headSet = numberSet.headSet(5);

    assertThat(headSet).hasSize(4)
            .containsExactly(1, 2, 3, 4);
    assertThat(numberSet).hasSize(10);
}

 

 

9. tailSet(E from)

주어진 값보다 큰 요소들을 반환한다, 이때 from는 inclusive(포함)

@Test
void tailSet() {
    SortedSet<Integer> tailSet = numberSet.tailSet(5);

    assertThat(tailSet).hasSize(6)
            .containsExactly(5, 6, 7, 8, 9, 10);
    assertThat(numberSet).hasSize(10);
}

 

---

 

백준 TreeSet 관련 문제 추천

둘 다 TreeSet method를 활용하면 풀 수 있는 문제이다

 

1. 문제 추천 시스템 version1 - https://www.acmicpc.net/problem/21939

2. 문제 추천 시스템 version2 - https://www.acmicpc.net/problem/21944