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

 

 📚 TreeSet

 

 

TreeSet 

TreeSet은 Set 인터페이스를 구현한 클래스로써 객체를 중복해서 저장할 수 없고 저장 순서가 유지되지 않는다는 Set의 성질을 그대로 가지고 있다. 이진 탐색 트리의 구조로 이루어져 있다. 추가와 삭제에는 시간이 조금 더 걸리지만, 정렬과 검색에 높은 성능을 보이는 자료구조이다.

 

이진탐색트리의 형태로 데이터를 저장하기에 기본적으로 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 값 추가

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

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

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

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

 

 

✅ TreeSet 값 삭제

값을 삭제하기 위해서는 remove(value) 메소드를 사용하여 value를 삭제할 수 있다.

모든 값을 제거하려면 clear() 메소드를 사용한다.

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

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

ts1.clear(); // 전체 삭제
System.out.print(ts1); // 출력 결과 : []

 

 

✅ TreeSet 크기 구하기

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

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

 

 

✅ TreeSet 출력

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

 

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

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

System.out.print(ts1); // 전체 출력 : [3, 5, 9];
System.out.print(ts1.first()) // 최소값 출력 : 3
System.out.print(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 내림차순 정렬

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