[JAVA의 정석]TreeSet

이 글은 유튜브 '자바의 정석 - 기초편'을 보고 정리한 글입니다. 

 

 

📂content

1. TreeSet - 범위 탐색, 정렬 

- 이진 탐색 트리(binary search tree)로 구현. 범위 탐색과 정렬에 유리

- 이진 트리는 모든 노드가 최대 2개(0~2)의 하위 노드를 가짐

   각 요소(node)가 나무(tree) 형태로 연결(LinkedList의 변형)

 //트리 노드
 class TreeNode {
            TreeNode left; //왼쪽 자식노드
            Object element; //저장할 객체
            TreeNode right; //오른쪽 자식노드
        }
        
 //LinkedList 노드
  class Node {
            Node next; //다음 요소의 주소를 저장
            Object obj; //데이터를 저장
        }

 

 

 

 

 

2. 이진 탐색 트리(binary search tree)

 

- 부모보다 작은 값은 왼쪽, 큰 값은 오른쪽에 저장 

- 데이터가 많아질수록 추가, 삭제에 시간이 더 걸림(비교 횟수 증가) 

이진트리의 종류 중 하나.  TreeSet은 이진탐색 트리로 되어있음. 

 

 

 

 

 

3. TreeSet - 데이터 저장과정 boolean add(Object o)

Object는 저장할 객체이다. 앞에서 HashSet의 경우 중복을 허용하지 않기 때문에, add메서드 호출하면 메서드 내부에서 equals()와 hashcode()를 호출한다. 마찬가지로 TreeSet 역시 compare()를 호출해서 비교한다. 

 

※ TreeSet에 7, 4, 9, 1, 5의 순서로 데이터를 저장하면, 아래의 과정을 거친다.

(루트부터 트리를 따라 내려가며 값을 비교. 작으면 왼쪽, 크면 오른쪽에 저장)

 

 

 

 

 

3. TreeSet - 주요 생성자와 메서드

생성자 또는 메서드	설명
TreeSet()	기본 생성자
TreeSet(Collection c)	주어진 컬렉션을 저장하는 TreeSet을 생성
TreeSet(Comparator comp)	주어진 정렬기준으로 정렬하는 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는 범위에 포함되지 않음)
SortedSet headSet(Object toElement)	지정된 객체보다 작은 값의 객체들을 반환
SortedSet tailSet(Object fromElement)	지정된 객체보다 큰 값의 객체들을 반환

- Comparator은 비교기준을 제공한다. 이게 없으면 저장하는 객체의 Comparable의 compareTo()를 사용한다. 

 

 

 

 

 

4. TreeSet  - 예제 

⍟실습

Ex11_13

package etc;

import java.util.Comparator;
import java.util.Set;
import java.util.TreeSet;

public class Ex11_13 {
    public static void main(String[] args) {
        Set set = new TreeSet(); //범위 검색, 정렬 필요없음
//        Set set = new HashSet(); //정렬 필요


        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);
        //TreeSet : [15, 20, 22, 25, 42, 44] //정렬O
        //HashSet : [32, 39, 9, 25, 43, 28] //정렬X
    }
}

 

위 코드에서 객체를 집어넣어 보자!

 

package etc;

import java.util.Set;
import java.util.TreeSet;

public 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(new Test());
        }

        System.out.println(set);
    }
}

class Test {}

 

이 코드를 돌리면 예외가 발생한다.

 

형변환 예외가 발생했는데 그 이유는 비교기준이 없어서 그렇다. 

 그렇기 때문에 비교기준을 만들어 주어야 한다. 

 

 

Comparator을 이용해서 비교기준을 주자! 

package etc;

import java.util.Comparator;
import java.util.Set;
import java.util.TreeSet;

public class Ex11_13 {
    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; //0은 같은 객체라고 판단하여 1개만 들어감.
    }
}

 

 

 

Comparable을 이용하자!

package etc;

import java.util.Comparator;
import java.util.Set;
import java.util.TreeSet;

public class Ex11_13 {
    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;
    }
} //비교 기준이 없음.

class TestComp implements Comparator {
    @Override
    public int compare(Object o1, Object o2) {
        return -1; //0은 같은 객체라고 판단하여 1개만 들어감.
    }
}

 

 comparable을 이용하면 TreeSet 생성자에 new TestComp()를 하지 않아도 된다. 

위 코드는 객체가 비교기준을 갖고 있는 것이고, 아래 코드는 TreeSet에게 정렬기준을 주는 것이다. 

Integer는 Comparable을 구현하고 있다. 

 

 

Ex11_14

package etc;

import java.util.*;

public class Ex11_14 {
    public static void main(String[] args) {
        TreeSet set = new TreeSet(); //범위 검색에 유리(from ~ to) 

        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); //[Car, abc, alien, bat, car, dZZZZ, dance, disc, dzzzz, elephant, elevator, fan, flower]
        System.out.println("range search : from " + from  +" to "+ to); //range search : from b to d
        System.out.println("result1 : " + set.subSet(from, to)); //result1 : [bat, car] 
        System.out.println("result2 : " + set.subSet(from, to + "zzz")); //result2 : [bat, car, dZZZZ, dance, disc]
    }
}

 

Ex11_15

범위 검색 subSet(), headSet(), tailSet()

package etc;

import java.util.*;

public 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(set); //[10, 35, 45, 50, 65, 80, 95, 100]
        System.out.println("50보다 작은 값 :" + set.headSet(new Integer(50))); //50보다 작은 값 :[10, 35, 45]
        System.out.println("50보다 큰 값 :"  + set.tailSet(new Integer(50))); //50보다 큰 값 :[50, 65, 80, 95, 100]
        System.out.println("40과 80사이의 값 : "+set.subSet(40, 80)); //40과 80사이의 값 : [45, 50, 65]
    }
}

 

여기서는 참조변수를 TreeSet에서 Set으로 바꾸면 안 된다. subSet, headSet, tailSet은 TreeSet에만 존재하는 메소드이기 때문이다. 

 

 

 

 

 

5. 트리 순회 (tree traversal)

- 이진 트리의 모든 노드를 한 번씩 읽는 것을 트리 순회라고 한다. 

- 전위, 중위, 후위 순회법이 있으며, 중위 순회하면 오름차순으로 정렬된다. 

전위(preorder) 순회: 부모 -> 자식 
후위(postorder) 순회: 자식 -> 부모
중위(inorder) 순회 : 왼쪽 자식 -> 부모 -> 오른쪽 자식 
레벨 순회 : 한 층씩 순서대로 

 

 

 

 

 

출처

https://www.youtube.com/watch?v=oJlCC1DutbA&list=PLW2UjW795-f6xWA2_MUhEVgPauhGl3xIp