Java 컬렉션 : TreeSet

Set : TreeSet

TreeSet은 이진 탐색 트리로 구현되어 있다. 이진 탐색 구조는 범위 탐색과 정렬에 유리한 구조이며 모든 노드가 최대 2개의 하위 노드를 갖는 특성이 있다. LinkedList처럼 하나의 노드가 이전 노드와 다음 노드의 주소를 저장하고 있는 구조이다.

class TreeNode {
	TreeNode left; // 왼쪽 자식노드
	Object element; // 저장할 객체
	TreeNode right; // 오른쪽 자식노드
}

이진 탐색 트리

첫 번째로 저장되는 값은 root가 되고 그 이후에 들어오는 값의 크기를 비교하며 트리 구조를 내려온다. 부모 노드보다 작은 값을 왼쪽, 큰 값을 오른쪽에 저장하게 된다. 저장할 때부터 비교를 하기 때문에 탐색과 정렬에 매우 용이하지만 데이터가 많아질 수록 추가, 삭제하는 데 시간이 더 걸리는 특징이 있다.

트리 순회

이진 트리의 모든 노드를 한번씩 읽는 것을 트리 순회라고 한다.

1. 전위 순회 : root => 왼쪽 자식 => 오른쪽 자식
2. 중위 순회 : 왼쪽 자식 => root => 오른쪽 자식
3. 후위 순회 : 왼쪽 자식 => 오른쪽 자식 => root
4. 레벨 순회 : 노드의 순서대로

TreeSet 생성자

TreeSet()
TreeSet(Collection c) // 해당 컬렉션을 저장하는 TreeSet 생성
TreeSet(Comparator comp) // 해당 정렬기준으로 정렬하는 TreeSet 생성

TreeSet 주요 메서드

객체의 반환

Object first()
Object last()
Object ceiling(Object O)
Object floor(Object O)
Object higher(Object O)
Object lower(Object O)

• first() , last() : 정렬된 순서에서 첫 번째, 마지막 객체를 반환한다.
• ceiling() , floor() : 지정된 객체와 같은 객체를 반환한다. 객체가 없으면 가까운 값 중 ceiling()은 큰 값을, floor()는 작은 값을 반환한다.
• higher(), lower() : 지정된 객체에서 가장 가까운 객체의 큰 값, 작은 값을 반환한다.

객체의 정렬

SortedSet subSet(Object fromElement, Object toElement)
SortedSet headSet(Object toElement)
SortedSet tailSet(Object fromElement)

• subSet() : 매개변수로 받은 범위의 결과를 반환한다.
• headSet() , tailSet() : 지정된 객체보다 작거나 큰 객체들을 반환한다.

예제 1 - 로또번호 생성기

Set set = new TreeSet();

for (int i = 0; i < 6; i++) {
	set.add((int) (Math.random() * 45) + 1);
}

System.out.println(set.toString());

// 결과
[21, 29, 31, 34, 41] // 중복값 없이 정렬된 모습
[4, 30, 31, 39, 41]

예제 2 - 범위 검색

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"));

//결과
[Car, abc, alien, bat, car, dZZZZ, dance, disc, dzzzz, elephant, elevator, fan, flower]
range search : from b to d
result1 : [bat, car] // d는 포함되지 않는다
result2 : [bat, car, dZZZZ, dance, disc]

예제 3 - 기준 검색

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

// 결과
50보다 작은 값 :[10, 35, 45] // 50보다 작은 값만 정렬되어 출력된다
50보다 큰 값 :[50, 65, 80, 95, 100]