[Java/자바] TreeSet 사용법

TreeSet은 이진 검색 트리(binary search tree)라는 자료구조의 형태로 데이터를 저장하는 컬렉션 클래스입니다.

이진 검색 트리는 정렬, 검색, 범위검색(range search)에 높은 성능을 보이며

TreeSet은 이진 검색 트리의 성능을 향상시킨 "레드-블랙 트리(Red-Black tree)"로 구현되어 있습니다.

그리고 Set 인터페이스를 구현했으므로 중복된 데이터의 저장을 허용하지 않고, 저장순서를 유지하지 않습니다.

이진 트리는 LinkedList처럼 여러 개의 노드(node)가 서로 연결된 구조로, 각 노드에 최대 2개의 노드를 연결할 수 있으며,

"루트(root)"라고 불리는 하나의 노드에서 시작해 계속 확장해 나갈 수 있습니다.

위 아래로 연결된 두 노드를 "부모 - 자식 관계"라고 하며 위의 노드를 부모노드, 아래의 노드를 자식 노드라고 합니다.

 

TreeSet 선언

TreeSet은 아래처럼 정렬 조건을 지정하여 선언이 가능합니다.

import java.util.TreeSet;
import java.util.Collections;

TreeSet<타입> tree = new TreeSet<>(); // TreeSet 생성 ( 기본 : 오름차순 )
TreeSet<타입> tree = new TreeSet<>(Collection c); // 주어진 컬렉션을 저장하는 TreeSet 생성 ( 기본 : 오름차순 )
TreeSet<타입> tree = new TreeSet<>(Collections.reverseOrder()); // 내림차순 정렬로 TreeSet 생성

 

TreeSet 메서드

메서드	반환 타입	설 명
add(Object o)	boolean	주어진 객체(o)를 추가
addAll(Collection c)	boolean	지정된 Collection(c)의 객체들을 추가
ceiling(Object o)	Object	지정된 객체와 같은 객체를 반환. 없다면 큰 값을 가진 객체 중 제일 가까운 값의 객체를 반환. 그래도 없으면 null
clear()	void	지정된 모든 객체 삭제
clone()	Object	TreeSet을 복제
comparator()	Comparator	TreeSet의 정렬기준을 반환
contains(Object o)	boolean	지정된 객체(o)가 포함되어 있는지 확인
containsAll(Collection c)	boolean	주어진 컬렉션의 객체들이 모두 포함되어 있는지 확인
descendingSet()	NavigableSet	TreeSet에 저장된 요소들을 역순으로 정렬해서 반환
first()	Object	정렬된 순서에서 첫 번째 객체 반환
last()	Object	정렬된 순서에서 마지막 객체 반환
floor(Object o)	Object	지정된 객체와 같은 객체를 반환. 없으면 작은 값을 가진 객체 중 제일 가까운 값의 객체 반환. 그래도 없으면 null
headSet(Object toElement)	SortedSet	지정된 객체보다 작은 값의 객체들을 반환
headSet(Object toElement, boolean inclusive)	NavigableSet	지정된 객체보다 작은 값의 객체들을 반환. inclusive가 true면 같은 값의 객체도 포함.
higher(Object o)	Object	지정된 객체보다 큰 값을 가진 객체 중 제일 가까운 값의 객체를 반환. 없으면 null.
lower(Object o)	Object	지정된 객체보다 작은 값을 가진 객체 중 제일 가까운 객체를 반환. 없으면 null
isEmpty()	boolean	TreeSet이 비었는지 확인
iterator()	Iterator	TreeSet의 Iterator를 반환
pollFirst()	Object	TreeSet의 첫 번째 요소 (제일 작은 값의 객체)를 반환
pollLast()	Object	TreeSet의 마지막 번째 요소 ( 제일 큰 값)을 반환
remove(Object o)	boolean	지정된 객체를 삭제
retainAll(Collection c)	boolean	주어진 컬렉션과 공통된 요소만을 남기고 삭제 ( 교집합 )
size()	int	TreeSet에 저장된 객체 수 반환
spliterator()	Spliterator	TreeSet의 spliterator를 반환
subSet(Object fromElement, Object toElement)	SortedSet	범위 검색 ( from와 to 사이)의 결과를 반환. 끝 범위 to는 포함 X
subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)	NavigableSet<E>	범위 검색 ( strat와 end 사이)의 결과를 반환. ( fromInclusiver가 true면 시작값 포함, toInclusive가 true면 끝  값 포함. )
tailSet(Object fromElement)	SortedSet	지정된 객체보다 큰 값의 객체들을 반환
toArray()	Object[]	지정된 객체를 객체배열로 반환
toArray(Object[] a)	Object[]	저장된 객체를 주어진 객체배열에 저장하여 반환

---

이진 검색 트리 정렬 과정

- 첫 번째로 저장되는 값은 루트가 되고, 두 번째 값은 트리의 루트부터 시작해서 값의 크기를 비교하며 트리를 따라내려갑니다.
- 작은 값은 왼쪽, 큰 값은 오른쪽에 저장합니다.
- 왼쪽 자식 노드의 값은 부모노드의 값보다 작고, 오른쪽 자식 노드의 값은 부모노드이 값보다 커야합니다.
- 검색과 정렬에 유리합니다.
- 노드의 추가 삭제에 시간이 걸립니다. ( 순차적으로 저장하지 않기 때문 )

 

예를 들어 이진검색트리에 7, 4, 9, 1, 5의 순서로 값을 저장한다고 하면 다음과 같은 정렬 과정을 거칩니다.

 

 

왼쪽 마지막 값에서부터 오른쪽 값까지 값을 "왼쪽 노드 -> 부모 노드 -> 오른쪽 노드" 순으로 읽으면 오름차순으로 정렬된 순서를 얻을 수 있습니다.

( 1 -> 4 -> 5 -> 7 -> 9 ) 

 

TreeSet은 이처럼 정렬된 상태를 유지하기 때문에 단일 값 검색과 범위검색이 매우 빠릅니다.

 

---

TreeSet 예제

 

정렬이 필요없는 TreeSet 예제

import java.util.*;

class TreeSetLotto {
	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);  // set.add(new Integer(num));
		}

		System.out.println(set);
	}
}

이 예제는 정렬하는 코드가 빠져있는데, TreeSet은 저장할 때 이미 정렬을 하기 때문에 정렬을 할 필요가 없습니다.

 

 

범위 검색 예제

import java.util.*;

class TreeSetEx1 {
	public static void main(String[] args) {
		TreeSet set = new TreeSet();

		String from = "b";
		String to	= "d";

		set.add("abc");
		set.add("alien");
		set.add("bat");
		set.add("car");
		set.add("Car");
		set.add("disc");
		set.add("dance");
		set.add("dZZZZ");
		set.add("dzzzz");
		set.add("elephant");
		set.add("elevator");
		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("result2 : " + set.subSet(from, to + "zzz"));
	}
}

result1은 시작 범위인 b는 포함되지만 끝 범위인 d는 포함이 되지 않기 때문에 c로 시작하는 단어까지만 출력하였습니다.

만약, 똑같은 범위 값에 끝 범위인 d로 시작하는 단어까지 포함시키고 싶다면 끝 범위에 "zzz"같은 문자열을 붙이면 됩니다.

+ "문자열"을 하게 되면 끝 범위가 포함되며, 문자열은 index로 치면 1번째의 값이 "문자열"를 포함하지 않는 범위의 값까지 나타냅니다.

만약 set.subSet(from, to + "o")를 출력한다면, result2의 결과는 [bat, car, dZZZZ, dance]로 출력되며

여기서 "dZZZZ"가 포함된 이유는 유니코드 상으로 대문자가 소문자보다 값이 작기 때문에 "o"의 값 앞까지의 범위로 포함되여 출력되게 됩니다.

 

지정된 기준 값보다 크거나 작은 값 찾기 예제

import java.util.*;

class TreeSetEx2 {
	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(new Integer(score[i]));

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

 

 

 

---

참고자료: 자바의 정석3