Java_컬렉션프레임웍(5)_TreeSet

⑧ TreeSet (중복X, 순서유지X)

: 범위 검색과 정렬에 유리한 컬렉션 클래스. (HashSet보다 데이터 추가, 삭제에 시간이 더 걸림.)

 

 

- 이진 트리(binary tree)

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

 

→ 최대 2개의 노드를 연결할 수 있으며 '루트'라고 불리는 하나의 노드에서부터 시작해서 계속 확장해 나갈 수 있다.  

 

 

 

- 이진 탐색 트리(binary search tree) 

• 모든 노드는 최대 두 개의 자식노드를 가질 수 있다.
• 왼쪽 자식노드의 값은 부모노드의 값보다 작고 오른쪽 자식노드의 값은 부모노드의 값보다 커야한다.
• 노드의 추가 삭제에 시간이 걸린다. (반복 비교)
• 검색과 정렬에 유리하다.
• 중복된 값을 저장하지 못한다. 

 

 

- TreeSet의 메서드

생성자 또는 메서드	설명
TreeSet()	기본 생성자
TreeSet(Collection c)	주어진 컬렉션을 저장하는 TreeSet을 생성
TreeSet(Comparator comp)	주어진 정렬조건으로 정렬하는 TreeSet을 생성
boolean add(Object o) boolean addAll(Collection c)	지정된 객체(o) 또는 Collection(c)의 객체들을 Collection에 추가
Object ceiling(Object o)	지정된 객체와 같은 객체를 반환. 없으면 큰 값을 가진 객체 중 제일 가까운 값의 객체를 반환. 없으면 null
void clear()	저장된 모든 객체를 삭제
Object clone()	TreeSet을 복제하여 반환
Comparator comparator()	TreeSet의 정렬기준(Comparator)를 반환
boolean contains(Object o) boolean containsAll(Collection c)	지정된 객체(o) 또는 Collection의 객체들이 모두 포함되어 있는지 확인
Object floor(Object o)	지정된 객체와 같은 객체를 반환. 없으면 작은 값을 가진 객체 중 제일 가까운 값의 객체를 반환. 없으면 null
boolean isEmpty()	TreeSet이 비어있는지 확인
Iterator iterator()	TreeSet의 Iterator를 반환
Object last()	정렬된 순서에서 마지막 객체를 반환
Object lower(Object o)	지정된 객체보다 작은 값을 가진 객체 중 제일 가까운 값의 객체를 반환. 없으면 null
Object pollFirst()	TreeSet의 첫번째 요소(제일 작은 값의 객체)를 반환.
Object pollLast()	TreeSet의 마지막 번째 요소(제일 큰 값의 객체)를 반환.
boolean remove(Object o)	지정된 객체를 삭제
boolean retainAll(Collection c)	주어진 컬렉션과 공통된 요소만을 남기고 삭제(교집합)
int size()	저장된 객체의 개수를 반환
SortedSet tailSet(Object fromElement)	지정된 객체보다 큰 값의 객체들을 반환한다.
Object[] toArray()	저장된 객체를 객체배열로 반환한다.
Object[] toArray(Object[] a)	저장된 객체를 주어진 객체배열에 저장하여 반환한다.

 

 

- TreeSet 예제

import java.util.*;

class JavaJungsuk_CollectionFramework_TreeSet {
    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);
        }
        
        System.out.println(set);
    }
}

결과
[5, 12, 24, 27, 36, 44]

→ TreeSet은 저장할 때 이미 정렬하기 때문에 읽어올 때 따로 정렬할 필요가 없다. 

 

import java.util.*;

class JavaJungsuk_CollectionFramework_TreeSet {
    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"));
    }
}

결과
[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()을 이용해서 범위검색할 때 시작범위는 포함되지만 끝 범위는 포함되지 않으므로 result1에는 c로 시작하는 단어까지만 출력되었다.

→ 끝 범위인 d로 시작하는 단어까지 포함시키고자 한다면, result2와 같이 'zzz'와 같은 문자열을 붙이면 된다.

 

import java.util.*;

class JavaJungsuk_CollectionFramework_TreeSet {
    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)));
    }
}

결과
50보다 작은 값 : [10, 30, 45]
50보다 큰 값 : [50, 65, 80, 95, 100]

→ headSet메서드와 tailSet메서드를 이용하면 TreeSet에 저장된 객체 중 지정된 기준 값보다 큰 값의 객체들과 작은 값의 객체들을 얻을 수 있다.