TreeSet

자바의정석 3rd Edition 2권을 참조하였습니다.

https://www.aladin.co.kr/shop/wproduct.aspx?ItemId=76083001 

Java의 정석

 

 

Treeset

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

이진 검색 트리는 정렬, 검색, 범위검색(range search)에 높은 성능을 보이는 자료구조이며 TreeSet은 이진 검색 트리의 성능을 향상시킨 '레드-블랙 트리(Red-Black tree)'로 구현되어 있다.

그리고 Set인터페이스를 구현했으므로 중복된 데이터의 저장을 허용하지 않으며 정렬된 위치에 저장하므로 저장순서를 유지하지도 않는다.

이진 트리(binary tree)는 링크드리스트처럼 여러 개의 노드(node)가 서로 연결된 구조로, 각 노드에 최대 2개의 노드를 연결할 수 있으며 '루트(root)'라고 불리는 하나의 노드에서 시작해서 계속 확장해 나갈 수 있다.

위 아래로 연결된 두 노드를 '부모-자식관계'에 있다고 하며 위의 노드를 부모 노드, 아래의 노드를 자식 노드라 한다.

부모-자식관계는 상대적인 것이며 하나의 부모 노드는 최대 두 개의 자식 노드와 연결될 수 있다.

아래 그림에서 7은 2와 6의 부모 노드이고, 2와 6은 7의 자식노드이다.

이진 트리(binary tree)의 예 (위키백과)

이진 트리의 노드를 코드로 표현하면 다음과 같다.

public class TreeNode {
	TreeNode left;		// 왼쪽 자식노드
	Object element;		// 객체를 저장하기 위한 참조변수
	TreeNode right;		// 오른쪽 자식노드
}

데이터를 저장하기 위한 Object타입의 참조변수 하나의 두 개의 노드를 참조하기 위한 두 개의 참조변수를 선언했다.

이진 검색 트리(binary search tree)는 부모노드의 왼쪽에는 부모노드의 값보다 작은 값의 자식노드를 오른쪽에는 큰 값의 자식노드를 저장하는 이진 트리이다.

첫 번째로 저장하는 값은 루트가 되고, 두 번째 값은 트리의 루트부터 시작해서 값의 크기를 비교하면서 트리를 따라 내려간다. 작은 값은 왼쪽에 큰 값은 오른쪽에 저장한다. 이렇게 트리를 구성하면, 왼쪽 마지막 레벨이 제일 작은 값이 되고 오른쪽 마지막 레벨의 값이 제일 큰 값이 된다.

TreeSet에 저장되는 객체가 Comparable을 구현하던가 아니면, TreeSet에게 Comparator를 제공해서 두 객체를 비교할 방법을 알려줘야 한다. 그렇지 않으면, TreeSet에 객체를 저장할 때 예외가 발생한다.

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

이진 검색 트리(binary search tree)의 특징

- 모든 노드는 최대 두 개의 자식노드를 가질 수 있다.

- 왼쪽 자식노드의 값은 부모노드의 값보다 작고, 오른쪽 자식노드의 값은 부모노드의 값보다 커야한다.

- 노드의 추가 삭제에 시간이 걸린다. (순차적으로 저장하지 않으므로)

- 검색(범위검색)과 정렬에 유리하다.

- 중복된 값을 저장하지 못한다.

 

TreeSetLotto.java

package kr.co.dong.datastructure.treeset;

import java.util.*;

public class TreeSetLotto {
	public static void main(String[] args) {
		Set set = new TreeSet();
		
		for(int idx = 0; set.size() < 6; idx++) {
			int num = (int)(Math.random() * 45) + 1;
			set.add(num);		// set.add(new Integer(num));
		}
		
		System.out.println(set);
	}
}
// 실행 결과 [10, 13, 14, 31, 42, 44]
// HashSet과 달리 따로 정렬할 필요 없이 사용가능

TreeSetEx1.java

package kr.co.dong.datastructure.treeset;

import java.util.*;

public 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.printf("range search : from %s to %s \n",from, to);
		System.out.printf("result1 : %s \n",set.subSet(from, to));
		System.out.printf("result2 : %s \n",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] 
result2 : [bat, car, dZZZZ, dance, disc]

subSet()을 이용해서 범위검색(range search)할 때 시작범위는 포함하지만 끝 범위는 포함되지 않으므로
result1에는 c로 시작하는 단어까지만 검색결과에 포함되어 있다.
만일 끝 범위인 d로 시작하는 단어까지 포함시키고자 한다면, 아래와 같이 끝 범위에 'zzz'와 같은 문자열을 붙이면 된다.
System.out.printf("result2 : %s \n",set.subSet(from, to + "zzz"));
d로 시작하는 단어 중에서 'dzzz' 다음에 오는 단어는 없을 것이기 때문에 d로 시작하는 모든 단어들이 포함될 것이다.
결과를 보면 'abc'보다 'Car'가 앞에 있고 'dZZZZ'가 'dance'보다 앞에 정렬되어 있는데
이는 대문자가 소문자보다 우선하기 때문 그래서 가능하면 하나로 통일
문자열의 경우 정렬순서는 문자의 코드값이 기준이 되므로, 오름차순 정렬의 경우 코드 같이 크기가 같은 순서에서 큰 순서,
즉 공백, 숫자, 대문자, 소문자 순으로 정렬되고 내림차 순의 경우 그 반대가 된다.
*/

AsciiPrint.java

package kr.co.dong.datastructure.treeset;

public class Asciiprint {
	public static void main(String[] args) {
		char ch = ' ';
		// 공백 이후의 문자들을 출력한다.
		for(int idx = 0; idx < 95; idx++) {
			System.out.print(ch++);
		}
	}
}
// 실행결과
//  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~

TreeSetEx2.java

package kr.co.dong.datastructure.treeset;

import java.util.*;

public class TreeSetEx2 {
	public static void main(String[] args) {
		TreeSet set = new TreeSet();
		int[] score = {80, 95, 50, 35, 45, 65, 10, 100};
		
		for(int idx = 0; idx < score.length; idx++) {
			set.add(new Integer(score[idx]));
		}
		
		System.out.println("50보다 작은 값 : "+set.headSet(new Integer(50)));
		System.out.println("50보다 큰 값 : "+set.tailSet(new Integer(50)));
		
	}
}
// 실행 결과
// 50보다 작은 값 : [10, 35, 45]
// 50보다 큰 값 : [50, 65, 80, 95, 100]
// headSet 메서드와 tailSet 메서드를 이용하여 기준 값보다 큰 값이나 작은 값을 가져오는 예제