데이터가 많아지면, 트리가 커진다. 트리가 커지면 요소를 하나 저장할 때 마다 부모보다 큰지 작은지 비교해야 한다. 이진 탐색 트리는 부모보다 작은 값을 왼쪽, 큰 값을 오른쪽에 저장해야 하기 때문이다. 즉, 트리가 커질수록 비교횟수가 늘어나기 때문에 저장하는데 시간이 더 걸린다. 삭제할 때에도 마찬가지이다.
TreeSet의 데이터 저장과정 boolean add(Object obj)
TreeSet에 7, 4, 9, 1, 5의 순서로 데이터를 저장하면, 아래의 과정을 거친다.
난수 데이터를 TreeSet(이진 탐색 트리)에 저장했기 때문에, 요소들이 정렬되어 출력되었다.
[테스트1] HashSet에 저장할 경우 출력 결과 테스트
public class Ex11_13 {
public static void main(String[] args) {
// Set set = new TreeSet(); // 범위 검색, 정렬, 정렬 필요없음
Set set = new HashSet(); // 정렬 필요
결과
[32, 33, 2, 39, 28, 31]
예제11-10(Ex_10)과 비교해보면, HashSet을 LinkedList로 옮긴 다음에 sort()를 호출하여 정렬했다. 정렬하려면 순서를 유지하는 리스트(List)여야 하기 때문에 이 과정을 거쳤다. 반면, TreeSet으로 할 경우, 정렬을 하지 않았지만 정렬이 되어 출력되는 것을 확인 할 수 있다. 이것이 TreeSet의 장점이다. 정렬을 할 필요가 없다.
[테스트2] Test클래스 생성하여 비교기준 필요성여부 테스트
Test클래스를 새로 생성(내용x)
Test객체를 생성해서 TreeSet에 저장
set 출력
코드
import java.util.*;
public class Ex11_13 {
public static void main(String[] args) {
Set set = new TreeSet(); // 범위 검색, 정렬, 정렬 필요없음
// Set set = new HashSet(); // 정렬 필요(Ex11_10과 비교)
for (int i = 0; set.size() < 6 ; i++) {
int num = (int)(Math.random()*45) + 1;
set.add(new Test()); // set.add(new Integer(num));
}
System.out.println(set);
}
}
class Test {}
결과
Exception in thread "main" java.lang.ClassCastException: class ch11.Test cannot be cast to class java.lang.Comparable (ch11.Test is in unnamed module of loader 'app'; java.lang.Comparable is in module java.base of loader 'bootstrap')
at java.base/java.util.TreeMap.compare(TreeMap.java:1291)
at java.base/java.util.TreeMap.put(TreeMap.java:536)
at java.base/java.util.TreeSet.add(TreeSet.java:255)
at ch11.Ex11_13.main(Ex11_13.java:12)
형변환 예외가 발생한다.
Test클래스의 객체를 반복문을 통해 저장을 하는데, set의 add메서드는 '비교기준'으로 비교한 후 저장을 한다. 하지만, '비교기준'이 없기 때문에 에러가 발생했다.
class Test {} // 비교 기준이 없음.
[테스트3] Test클래스 생성하여 비교기준 필요성여부 테스트2
비교 기준을 만들어주기 위해 TestComp클래스를 새로 생성(내용x)
비교 기준이 되려면 TestComp클래스는 Comparator를 구현해야 된다.
compare메서드를 오버라이딩한다.
TreeSet() 기본 생성자를 호출하는 대신, 매개변수 있는 생성자 TreeSet(Comparator comp)를 사용하기 위해 new TestComp()로 TestComp클래스의 객체를 매개변수로 대입한다.
코드
import java.util.*;
public class Ex11_13 {
public static void main(String[] args) {
Set set = new TreeSet(new TestComp()); // 범위 검색, 정렬, 정렬 필요없음
// Set set = new HashSet(); // 정렬 필요(Ex11_10과 비교)
// for (int i = 0; set.size() < 6 ; i++) {
// int num = (int)(Math.random()*45) + 1;
set.add(new Test()); // set.add(new Integer(num));
set.add(new Test()); // set.add(new Integer(num));
set.add(new Test()); // set.add(new Integer(num));
set.add(new Test()); // set.add(new Integer(num));
// }
System.out.println(set);
}
}
class Test {} // 비교 기준이 없음.
class TestComp implements Comparator {
@Override
public int compare(Object o1, Object o2) {
return 1;
}
}
import java.util.*;
public class Ex11_13 {
public static void main(String[] args) {
Set set = new TreeSet(); // 범위 검색, 정렬, 정렬 필요없음
// Set set = new HashSet(); // 정렬 필요(Ex11_10과 비교)
// for (int i = 0; set.size() < 6 ; i++) {
// int num = (int)(Math.random()*45) + 1;
set.add(new Test()); // set.add(new Integer(num));
set.add(new Test()); // set.add(new Integer(num));
set.add(new Test()); // set.add(new Integer(num));
set.add(new Test()); // set.add(new Integer(num));
// }
System.out.println(set);
}
}
class Test implements Comparable{
@Override
public int compareTo(Object o) {
return -1;
}
} // 비교 기준이 없음.
class TestComp implements Comparator {
@Override
public int compare(Object o1, Object o2) {
return 1;
}
}
set.subSet(from, to);
→ set.subSet("b", "d"); // "d" 포함 안 됨
set.subSet(from, to + "zzz");
→ set.subSet("b", "d" + "zzz");
→ set.subSet("b", "dzzz"); // "d" 포함 문자열 중 맨끝 문자열만 비포함 즉 나머지는 포함
