TreeSet (2)

11 - 42 ~ 45 TreeSet (2)

 

11 - 42 TreeSet - 주요 생성자와 메서드

 

 

컬렉션 (Collection) 인터페이스에 존재하는 메서드인

add() 라던지

size() 라던지

remove() 라던지

isEmpty() 라던지

iterator() 라던지

 

이런 메서드들은 모든 컬렉션 인터페이스를 상속받은 컬렉션 프레임워크 인터페이스에 존재하는 메서드 이므로

 

공통의 메서드를 제외 하고 TreeSet 클래스 가 가지고 있는 메서드를 정리 해보려 한다.

 

1)

맨 위의 3개의 메서드는 생성자 이다.

 

TreeSet(Comparator comp) 생성자의 인자는 비교 기준을 제공 해주는 것을 의미 한다.

 

만약에 비교 기준 대상이 존재 하지 않으면, 저장 하는 객체의 Comparable 을 사용 해야 한다.

 

Comparable 은 기본 비교 기준 이다.

 

어쨌든, TreeSet에 객체를 저장 할 때, 반드시 객체를 비교 해야 하기 때문에 비교 대상이 필요 하다.

 

정리하자면,

 

TreeSet은 비교 기준이 반드시 필요 하다.

 

그래서 둘 중에 하나는 필요 하다.

 

>> 저장 하는 객체가 Comparable 을 가지고 있거나,

 

>> TreeSet이 어떤 정렬 기준을 가지고 있거나 이다. (TreeSet 생성자에 넣어 비교 기준 넣어 주기) 

 

2)

Object first() 랑 Object last() 의 정렬된 순서 기준은 오름 차순 이다.

즉, first() 는 가장 작은 값을 반환 하고, last()는 가장 큰 값을 반환 한다.

 

3)

Object ceiling(Object o) 는 같거나 큰것을 결과로 반환 하게 된다. (올림)

 

TreeSet에 저장 되어 있는 값이 [ 30, 40, 50 ] 일때,

40을 매개변수의 값으로 넣으면 40을 결과로 갖게 되지만,

45를 매개변수의 값으로 넣으면 50을 결과로 갖게 된다.

 

4)

Object floor(Object o) 는 같거나 작은것을 결과로 반환 하게 된다. (내림)

 

TreeSet에 저장 되어 있는 값이 [ 30, 40, 50 ] 일때,

40을 매개변수의 값으로 넣으면 40을 결과로 갖게 되지만,

35를 매개변수의 값으로 넣으면 30을 결과로 갖게 된다.

 

5)

Object higher(Object o) 는 매개변수의 값으로 넣은 값보다 제일 근처에 있는 큰 값을 반환 하게 된다.

만약에 40을 매개변수의 값으로 넣으면 50을 결과로 갖게 된다.

 

6)

Object lower(Object o) 는 매개변수의 값으로 넣은 값보다 제일 근처에 있는 작은 값을 반환 하게 된다.

만약에 40을 매개변수의 값으로 넣으면 30을 결과로 갖게 된다.

 

 

 

 

 

예제 01 )

 

import java.util.*;

class Ex11_13 {

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

    }
	
}

 

[ console ]

 

 

TreeSet은 범위 검색과 정렬에 유리 하다.

 

위와 같이 정렬이 되어 값이 나오는 것을 확인 할 수 있다.

 

만약에 TreeSet을 사용 하지 않고 HashSet 을 사용 하면 ?

 

 

 

정렬이 되지 않는 것을 확인 할 수 있다.

 

그래서 HashSet 을 사용 하면 정렬을 사용 해야 한다.

 

LinkedList에 옮겨 담고 정렬 한다.

 

import java.util.*;

class Ex11_10 {

    public static void main(String[] args) {

        Set set = new HashSet();

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

        List list = new LinkedList(set); // LinkedList(Collection c)
        Collections.sort(list);          // Collections.sort(List list)
        System.out.println(list);

    }

}

 

코드를 보면 참조변수 set을 LinkedList에 생성자에 옮겨 담고,

 

java util 패키지 내부에 있는 Collections 클래스의 static 메서드인 sort() 메서드를 사용 해서 정렬 한다.

 

 

암튼, TreeSet 을 사용 하면 따로 정렬을 하지 않아도 정렬이 되어 값이 출력 된다.

이게 TreeSet 클래스의 장점 이라고 할 수 있다.

 

근데 앞에서 TreeSet 은 비교 기준이 반드시 필요 하다고 했었다. 아래를 확인 해보자.

 

 

이렇게 하면 숫자는 비교 기준이 있으니까 괜찮다.

 

 

Integer 래퍼 클래스는 Number 클래스를 상속 받고, Comparable 인터페이스를 구현한 클래스 이다.

 

 

 

근데, 만약에 set의 add() 메서드의 인자로 비교 기준이 존재 하지 않는 것을 인자로 넣으면 어떻게 될까 ?

 

 

대충 Test 클래스를 하나 생성 해서,

 

 

Test 클래스를 매개 변수의 값으로 넣어 주면 

 

 

이렇게 에러가 뜨게 된다.

 

비교 기준을 만들어 보자.

 

 

이렇게 그냥 만들고,

 

 

TreeSet 생성자에 비교 기준을 넣어 주고,

 

 

Test 객체를 하나 추가 하고,

 

 

출력을 하게 되면 ~

 

 

Test 객체가 TreeSet 에 저장 된 것을 확인 할 수 있게 된다.

 

여러 Test 객체를 생성 해보자.

 

 

그러면 같은 객체 라고 중복 저장이 안되서 한개만 저장 하게 된다.

 

 

그 다음에 TestComp 클래스의 반환값을 -1 로 변경 해보자.

 

 

그러면 결과값은 아래와 같이 나오게 된다.

 

 

여러개 객체가 저장된 것을 볼 수 있다.

 

return 값이 0 이면 같은 값으로 판단 한다는 것을 의미 하고,

 

return 값을 -1 또는 1으로 하면 다른 값으로 판단 한다는 것을 의미 하게 되서 그런것이다.

 

 

 

다른 방법으로 Test 클래스에 Comparable 인터페이스를 구현시켜보자.

 

 

이러면 저장하는 객체인 Test 객체가 Comparable 을 가지고 있기 때문에 TreeSet은 정렬 기준을 갖고 있지 않아도 된다.

 

 

생성자의 인자를 비어 놓고,

 

 

Test 객체를 TreeSet에 저장 하고 출력 하면 ~

 

맨 처음에 예외가 발생 했을 때와 다르게, 

 

 

예외가 발생 하지 않고 잘 저장 된것을 확인 할 수 있다.

 

결론은 TreeSet은 객체를 저장 할 때, 반드시 정렬 기준이 필요 하다 

 

 

 

예제 02 )

 

import java.util.*;

class Ex11_14 {

    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"));    //	to + "zzz" == "d" + "zzz" == "dzzz"

    }

}

 

위의 예제는 subSet(from, to) 메서드의 사용 방법을 다룬 예제 이다.

 

from을 b로 저장 했고,

 

to를 d로 저장 했으므로,

 

b 와 d 가 포함 되어 있는 값 사이에 있는 값을 뽑아 출력 한다는 것이다.

 

즉, b로 시작하는 데이터 부터 ~ d로 시작하는 단어 바로 앞의 데이터 까지 출력 하게 된다.

 

TreeSet 클래스는 범위 검색 (from ~ to) 에 유리 하다고 했었다.

 

이렇게 subSet() 메서드를 사용 하면 된다.

 

[ console ]

 

 

 

 

예제 03 )

 

headSet() 과 tailSet() 메서드를 사용 해서 기준이 되는 값으로 쉽게 다른 값을 찾을 수 있다.

 

import java.util.*;

class Ex11_15 {

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

    }

}

 

[ console ]

 

 

참고로, headSet() 이랑 tailSet() 메서드는 TreeSet 클래스에만 존재하는 메서드 이므로,

 

 

이렇게 참조변수 set의 타입을 Set 인터페이스로 하게 되면,

 

Set 인터페이스가 가지고 있는 메서드만 사용 할 수 있게 된다.

 

 

그래서 이렇게 컴파일 에러가 발생 하게 된다.

 

 

 

11 - 45 TreeSet - 범위 검색 >> subSet(), headSet(), tailSet()

 

 

 

 

참고

트리 순회 (tree traversal)

 

 

트리는 순회 방법이 여러 가지가 있는데,

 

1)

부모 노드 (요소) 를 제일 먼저 읽는게 "전위 순회" 라고 한다. == Preorder Traversal

 

 

2)

부모 노드 를 가장 나중에 읽는 것을 "후위 순회" 라고 한다. == Postorder Traversal

 

 

3)

부모 노드를 가운데 놓고나서,

왼쪽 자식을 읽고 부모 노드 읽고, 오른쪽 자식을 읽는 방법을 "중위 순회" 라고 한다. == Inorder Traversal

 

 

4)

맨 위의 노드 부터 레벨 (층) 으로 차례대로 왼쪽 부터 읽는 방법을 "레벨 순회" 라고 한다. == Level Order Traversal

 

 

 

 

[ 정리 ]

 

TreeSet ?

>>

정렬 과 범위 검색에 유리한 클래스 라는 장점을 지닌다.

 

>>

TreeSet은 이진 트리의 한 종류인 이진 탐색 트리로 구성 되어 있고,

처음에는 비교 하지 않아서 연산 속도가 빠르지만,

트리가 커질 수록  비교 횟수가 증가 하게 되서,

데이터가 많아질수록 추가 / 삭제에 시간이 훨씬 증가 하게 된다는 단점을 지닌다.