[Java] TreeSet 자료구조

TreeSet 이란?
TreeSet은 Set 인터페이스를 구현한 클래스로써 객체를 중복해서 저장할 수 없고 저장 순서가 유지되지 않는다는 Set의 성질을 그대로 가지고 있다.

• TreeSet은 이진 탐색 트리(BinarySearchTree)의 구조로 이루어져 있다. 이진 탐색 트리는 추가와 삭제에는 시간이 조금 더 걸리지만 정렬, 검색에 높은 성능을 보이는 자료구조다.

• TreeSet은 이진탐색트리의 형태로 데이터를 저장하기에 기본적으로 nature ordering을 지원하며 생성자의 매개변수로 Comparator 객체를 입력하여 정렬 방법을 임의로 지정해 줄 수도 있다.

• TreeSet 이진탐색트리 구조
  TreeSet은 이진탐색트리 중에서도 성능을 향상시킨 레드-블랙 트리로 구현되어 있다.
  

레드 블랙 트리 : 부모노드보다 작은 값을 가지는 노드는 왼쪽 자식으로, 큰 값을 가지는 노드는 오른쪽 자식으로 배치하여 데이터의 추가나 삭제 시 트리가 한쪽으로 치우쳐지지 않도록 균형을 맞추어준다.

---

TreeSet 사용법, 예제

TreeSet 선언

import java.util.TreeSet;
import java.util.Arrays;

TreeSet<Integer> ts1 = new TreeSet<Integer>(); // TreeSet 생성
TreeSet<Integer> ts2 = new TreeSet<>(); // new에서 타입 파라미터 생략 가능
TreeSet<Integer> ts3 = new TreeSet<>(Arrays.asList(1,2,3)); // 초기값 지정;

TreeSet 에 값을 추가하기

• add(value) 메소드를 사용해서 TreeSet에 값을 추가할 수 있다.

TreeSet<Integer> ts1 = new TreeSet<>(); // TreeSet 생성

ts1.add(5);
ts1.add(3);
ts1.add(9);
ts1.add(7);


System.out.println(ts1); // 출력결과 : [3, 5, 7, 9]

TreeSet 값 삭제

• TreeSet의 값을 삭제하기 위해서는 remove(value) 메소드를 사용하여 value를 삭제할 수 있다.
• TreeSet의 모든 값을 제거하려면 clear() 메소드를 사용한다.

TreeSet<Integer> ts1 = new TreeSet<>(); // TreeSet 생성
ts1.add(5);
ts1.add(3);
ts1.add(9);

ts1.remove(3); // 3 삭제
System.out.println(ts1); // 출력결과 : [5, 9]
ts1.clear(); // 전체 삭제
System.out.println(ts1); // 출력결과 : []

TreeSet 크기 구하기

• TreeSet의 크기를 구하려면 size() 메소드를 사용한다.

TreeSet<Integer> ts1 = new TreeSet<>(); // TreeSet 생성
ts1.add(5);
ts1.add(3);
ts1.add(9);

System.out.println(ts1.size()); // TreeSet 크기 : 3

TreeSet 출력

TreeSet<Integer> ts1 = new TreeSet<>(); // TreeSet 생성
ts1.add(5);
ts1.add(3);
ts1.add(9);

System.out.println(ts1); // 전체출력 : [5, 3, 9]
System.out.println(ts1.first()); // 최소값 출력 : 3
System.out.println(ts1.last()); // 최대값 출력 : 9
//향상된 for문 사용
for(int i : ts1)
    System.out.print(i + " "); // 출력결과 : 3 5 9

Iterator iter = ts1.iterator();
while(iter.hasNext())
    System.out.print(iter.next() + " "); // 출력결과 : 3 5 9

• TreeSet을 그냥 print 하게 되면 대괄호로 묶어서 전체 값이 출력된다.
• first() 메소드는 TreeSet의 최소값을, last() 메소드는 최대값을 반환한다.
• print 이외에 TreeSet을 전체 출력하는 방법으로는 향상된 for문을 사용하거나, 객체를 하나씩 반복해서 가져오는 반복자(Iterator)를 사용한다.
• Iterator의 hasNext() 메소드는 가져올 객체가 있으면 true를, 없으면 false를 리턴한다.

TreeSet의 전체 출력 결과를 보면, 객체를 저장한 순서에 관계 없이 객체들이 오름차순으로 정렬돼서 출력되는 것을 볼 수 있다.(TreeSet은 오름차순 정렬이 기본값) 이를 내림차순으로 정렬하는 방법은 다음과 같다.

TreeSet 내림차순 정렬

• TreeSet을 생성할 때 파라미터에 Comparator를 입력하여 임의로 정렬할 수 있다.

TreeSet<Integer> ts1 = new TreeSet<>(Comparator.reverseOrder()); 
// Comparator 입력하여 임의로 내림차순 정렬
ts1.add(5);
ts1.add(3);
ts1.add(9);

Iterator iter = ts1.iterator();
while(iter.hasNext())
    System.out.print(iter.next() + " "); // 출력결과 : 9 5 3

참고자료(blog)
https://coding-factory.tistory.com/555
https://crazykim2.tistory.com/583