이진 탐색 트리(binary search tree)로 구현. 범위 탐색과 정렬에 유리하다.
이진 트리는 모든 노트가 최대 2개의 하위 노드를 갖는다. 각 요소(node)가 나무(tree)형태로 연결(LinkedList의 변형)되어있다.
class TreeNode{
TreeNode left; // 왼쪽 자식노드
Object element; // 저장할 객체
TreeNode right; // 오른쪽 자식노드
}
이진 탐색 트리(binary seach tree)
부모보다 작은 값은 왼쪽 큰 값은 오른쪽에 저장한다.
데이터가 많아질 수록 추가, 삭제에 시간이 더 걸린다.(비교 횟수 증가)
TreeSet - 데이터 저장과정 boolean add(Object o)
중복 x, TreeSet 7,4,9,1,5의 순서로 데이터를 저장하면, 아래의 과정을 거친다.
TreeSet 생성자 · 메서드
TreeSet 생성자
TreeSet() 기본생성자
TreeSet(Collection c) 주어진 컬렉션을 저장하는 TreeSet을 생성
TreeSet(Comparator comp) 주어진 정렬기준으로 정렬하는 TreeSet을 생성
TreeSet 메서드
Object first() 정렬된 순서에서 첫 번째 객체를 반환한다.
Object last() 정렬된 순서에서 마지막 객체를 반환한다.
Object ceiling(Object o) 지정된 객체와 같은 객체를 반환한다.(없으면 큰 값을 가진 객체 중 제일 가까운 값의 객체를 반환, 없으면 null을 반환)
Object floor(Object o) 지정된 객체와 같은 객체를 반환한다.(없으면 작은 값을 가진 객체 중 제일 가까운 값의 객체를 반환, 없으면 null을 반환)
Object higher(Object o) 지정된 객체보다 큰 값을 가진 객체 중 제일 가까운 값의 객체를 반환한다.(없으면 null을 반환)
Object lower(Object o) 지정된 객체보다 작은 값을 가진 객체 중 제일 가까운 값의 객체를 반환한다.(없으면 null을 반환)
SortedSet subSet(Object fromElement, Object toElement) 범위 검색(fromElement와 toElement사이)의 결과를 반환한다.(끝 범위인 toElement는 범위에 포함되지않는다. fromElement ≤ x < toElement)
SortedSet headSet(Object toElement) 지정된 객체보다 작은 값의 객체들을 반환한다.
SortedSet tailSet(Object formElement) 지정된 객체보다 큰 값의 객체들을 반환한다.
import java.util.*;
public class Try {
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);
}
System.out.println("----final set----");
System.out.println(set);
}
}
import java.util.*;
public class Try {
public static void main(String[] args) {
Set set = new TreeSet(new TestComp());
set.add(new Test());
set.add(new Test());
set.add(new Test());
set.add(new Test());
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 Try {
public static void main(String[] args) {
Set set = new TreeSet();
set.add(new Test());
set.add(new Test());
set.add(new Test());
set.add(new Test());
System.out.println(set);
}
}
class Test implements Comparable{
@Override
public int compareTo(Object o) {
return -1;
}
}
