TreeSet

TreeSet이란?

이진 검색 트리라는 자료구조의 형태로 데이터를 저장하는 컬렉션 클래스로 정렬, 검색, 범위 검색에 유리하다.

중복된 데이터의 저장을 허용하지 않으며 정렬된 위치에 저장하므로 저장 순서를 유지하지도 않는다. (중복 X, 순서 X)

다만, 순차적으로 저장하지 않기 때문에 추가 삭제에 시간이 걸린다는 단점이 있다.

 

 

정렬에 유리함을 보여주는 예제

 

아래 예제는 set.add()를 통해 set에 값을 저장하고 이를 출력하는 예제이다.

 

TreeSet은 저장할 때 이미 정렬하기 때문에 읽어올 때 따로 정렬할 필요가 없다.

어떻게 이럴 수가 있지?

TreeSet에 Integer 인스턴스를 저장했을 때 정렬되는 기준이 compareTo()이기 때문이다.

즉, Integer 클래스가 이미 Comparable을 구현하고 있기 때문에, 자동으로 정렬되는 것이다.

 

이 점은 HashSet과 다른 점이라고 할 수 있다.

단순히 중복을 제거 해야한다면 HashSet을, 중복도 제거하고 정렬까지 해야한다면 TreeSet을 사용하자.

 

package java11;

import java.util.Set;
import java.util.TreeSet;

public class Ex11_13 {

	public static void main(String[] args) {
		
		Set set = new TreeSet();
		
		for(int i = 0; set.size() < 6; i++) {
			int num = (int)(Math.random() * 45) + 1;
			set.add(num);
		}
		
		System.out.println(set); // [16, 34, 37, 40, 41, 43]

	}

}

 

범위 검색에 유리함을 보여주는 예제1

 

아래 예제는 set에 영어 단어를 저장하고 특정 알파벳 범위의 문자를 검색하여 출력하는 예제이다.

subSet(Object fromElement, Object toElement) 메서드를 통해 범위를 지정할 수 있다.

참고로 toElement는 범위에 포함하지 않으므로 포함하고 싶다면 subSet(fromElement, toElement + "kkk")와 같이

의미 없는 문자("ab", "zzz" 무엇이든 가능)를 뒤에 더해주면 to 범위까지 포함하여 출력할 수 있다.

 

출력에서 Car가 맨 앞에 위치하는 이유는 소문자보다 대문자가 우선 순위에 있도록 정렬에 기본 구현되어 있기 때문이다.

만약 출력 기준을 변경하고 싶다면 Comparator 인터페이스를 구현하면 된다.

 

package java11;

import java.util.TreeSet;

public class Ex11_14 {

	public static void main(String[] args) {
		
		TreeSet set = new TreeSet();
		
		String from = "b";
		String to = "d";
		
		set.add("abc"); set.add("bat");
		set.add("car"); set.add("Car"); 
		set.add("dance"); set.add("dZZZZ"); set.add("dzzzz");
		set.add("elephant"); set.add("fan"); set.add("flower");
		
		System.out.println(set);
		System.out.println("range search: from " + from + " to " + to);
		System.out.println("result1: " + set.subSet(from, to));
		System.out.println("result1: " + set.subSet(from, to + "kkk"));

	}

}

/*
[Car, abc, bat, car, dZZZZ, dance, dzzzz, elephant, fan, flower]
range search: from b to d
result1: [bat, car]
result1: [bat, car, dZZZZ, dance]
*/

 

범위 검색에 유리함을 보여주는 예제2

 

아래 예제는 배열의 값을 set에 넣어 원하는 범위의 값을 얻기 위한 예제이다.

headSet(Object toElement) 메서드는 지정된 객체보다 작은 값의 객체들을 반환한다.

tailSet(Object fromElement) 메서드는 지정된 객체보다 큰 값의 객체들을 반환한다.

 

package java11;

import java.util.TreeSet;

public class Ex11_15 {

	public static void main(String[] args) {
		
		TreeSet set = new TreeSet();
		
		int[] score = { 80, 95, 50, 35, 45, 65, 10, 100 };
		
		for(int i = 0; i < score.length; i++) {
			set.add(score[i]);
		}

		System.out.println("50보다 작은 값: " + set.headSet(50));
		System.out.println("50보다 큰 값: " + set.tailSet(50));
	}

}

/*
50보다 작은 값: [10, 35, 45]
50보다 큰 값: [50, 65, 80, 95, 100]
*/