[Java] 트리셋(TreeSet) 자료구조 정리

TreeSet 이란?

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

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

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

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을 생성하기 위해서 객체 타입을 파라미터를 표기하고 기본 생성자를 호출하면 된다. 선언시 크기를 지정해줄 수 없다.

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]

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

TreeSet 값 삭제

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의 값을 삭제하기 위해서는 remove(value) 메소드를 사용하여 value를 삭제할 수 있다.
TreeSet의 모든 값을 제거하려면 clear() 메소드를 사용한다.

TreeSet 크기 구하기

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

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

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

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<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

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

---

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