[JAVA] TreeSet

TreeSet은 이진 탐색 트리(binary search tree)로 구현되어있으며, 범위 탐색과 정렬에 유리합니다.

• 이진 트리의 경우 한개의 노드가 최대 2개의 하위 노드를 갖게 됩니다.

TreeSet의 기본형태 및 특징

부모를 기준으로 작은 값은 왼쪽에 큰 값은 오른쪽에 저장된다.

데이터가 많아 질수록 비교 횟수가 증가하기 때문에 추가, 삭제에 효율성이 떨어진다.

class TreeNode{
    TreeNode left; // 왼쪽 자식 노드
    Object element; // 저장할 객체
    TreeNode right; // 오른쪽 자식 노드
}

데이터의 저장 boolean add(Object o)

• equals()와 hashCode()를 자동으로 호출한다.
• Set은 중복을 허용하지 않는다.

TreeSet의 주요 생성자 및 메서드

TreeSet만 가지고 있는 메서드만 작성했습니다.

• add, remove, size, isEmpty 등은 반복적으로 나왔기 때문에 생략

생성자

• TreeSet() : 기본 생성자
• TreeSet(Collection c) : 주어진 Collection(c)를 저장한 TreeSet 생성
• TreeSet(Comparator comp) : 주어진 정렬기준(comp)으로 정렬하는 TreeSet 생성

그 외

• Object first() : 정렬된 순서에서 첫번째 객체를 반환한다.
• Object last() : 정렬된 순서에서 마지막 객체를 반환한다.
• Object ceiling(Object o) : 지정된 객체(o)와 같은 객체를 반환
  • 없으면 지정된 객체(o)보다 큰 값을 가진 객체 중 가장 가까운 값의 객체를 반환한다.
  • 큰 값도 없다면 null을 반환한다.
• Object floor(Object o) : 지정된 객체(o)와 같은 객체를 반환
  • 없으면 지정된 객체(o)보다 작은 값을 가진 객체 중 가장 가까운 값의 객체를 반환한다.
  • 작은 값이 없다면 null을 반환한다.
• Object higher(Object o) : 지정된 객체(o)보다 큰 값을 가진 객체 중 가장 가까운 값의 객체를 반환
  • 없다면 null을 반환
• Object lower(Object o) : 지정된 객체(o)보다 작은 값을 가진 객체 중 가장 가까운 값의 객체를 반환
  • 없다면 null을 반환
• SortedSet subSet(Object fromElement, Object toElement)
  • 지정된 범위 (fromElement <= x < toElement)의 결과를 반환한다.
• SortedSet headSet(Object toElement) : 지정된 객체(toElement)보다 작은 값의 모든 객체를 반환한다.
• SortedSet tailSet(Object fromElement) : 지정된 객체(fromElement)보다 큰 값의 모든 객체를 반환한다.

예제를 통해 알아보기

import java.util.*;

public class MyClass {
    public static void main(String args[]) {
      Set set = new TreeSet();
      // 정렬이 필요없다. TreeSet은 내부적으로 정렬을 한다.
      for (int i = 0; set.size() < 6; i++){
          int num = (int)(Math.random()*45) + 1;
          set.add(num);
      }
      System.out.println(set);
      
      //==================================================================================================
      
      // 위에 코드를 HashSet으로 만든다면?
      Set ex = new HashSet();
      for(int i = 0; ex.size() < 6; i++){
          int num = (int)(Math.random()*45)+1;
          ex.add(num);
      }
      List list = new LinkedList(ex); // LinkedList(Collection c)
      // Set은 순서가 없기때문에 정렬을 할 수 없다.
      // Set을 순서가 있는 List로 형 변환 후 정렬해줘야한다.
      Collections.sort(list);
      System.out.println("HashSet으로 만든 것 = "+list);
      
      //==================================================================================================
      
      // 저장할 객체와 정렬기준을 따로따로 만들었을때
      Set set2 = new TreeSet(new TestComp()); // 정렬기준을 정해준 TreeSet 생성
      set2.add(new TestTreeSet()); // 6504e3b2
      set2.add(new TestTreeSet()); // 515f550a
      set2.add(new TestTreeSet()); // 6504e3b2
      System.out.println(set2);
      // TestComp의 리턴값이 1 이면 >> [TestTreeSet@6504e3b2, TestTreeSet@515f550a, TestTreeSet@6504e3b2]
      // TestComp의 리턴갑이 -1 이면 >> [TestTreeSet@6504e3b2, TestTreeSet@515f550a, TestTreeSet@6504e3b2]
      // TestComp의 리턴값이 0 이면 >> [TestTreeSet@6504e3b2]
      
      // 저장할 객체에게 정렬기준까지 부여했을때
      Set set3 = new TreeSet();
      set3.add(new AllComp()); // 626b2d4a
      set3.add(new AllComp()); // 5e91993f
      set3.add(new AllComp()); // 1c4af82c
      System.out.println(set3);
      // AllComp의 리턴값이 1이면 >> [AllComp@626b2d4a, AllComp@5e91993f, AllComp@1c4af82c]
      // AllComp의 리턴값이 -1이면 >> [AllComp@626b2d4a, AllComp@5e91993f, AllComp@1c4af82c]
      // AllComp의 리턴값이 0이면 >> [AllComp@626b2d4a]
      
      TreeSet set4 = new TreeSet();
      String from = "b";
      String to = "d";
      set4.add("abc"); set4.add("alien"); set4.add("bat");
      set4.add("car"); set4.add("Car"); set4.add("disc");
      set4.add("dance"); set4.add("dZZZZ"); set4.add("dzzzz");
      set4.add("elephant"); set4.add("elevator"); set4.add("fan"); set4.add("flower");
      System.out.println(set4); // TreeSet이 내부적으로 자동 정렬을 해준다. ( 소문자 보단 대문자가 앞에 온다. )
      // [Car, abc, alien, bat, car, dZZZZ, dance, disc, dzzzz, elephant, elevator, fan, flower]
      System.out.println("range search : from " + from + " to " + to);
      System.out.println("result 1 = " + set4.subSet(from, to));
      // result 1 = [bat, car]
      System.out.println("result 2 = " + set4.subSet(from, to+"zzz"));
      // result 2 zzz= [bat, car, dZZZZ, dance, disc]
      System.out.println("result 3 = " + set4.subSet(from, to+"pp"));
      // result 3 pp= [bat, car, dZZZZ, dance, disc]
      System.out.println("result 4 = " + set4.subSet(from, to+"dd"));
      // result 4 dd= [bat, car, dZZZZ, dance]
      System.out.println("result 5 = " + set4.subSet(from, to+"et"));
      // result 5 et= [bat, car, dZZZZ, dance]
      
      TreeSet set5 = new TreeSet();
      int[] score = {80,90,50,35,45,65,10,100};
      for(int i = 0; i < score.length; i++){
          set5.add(new Integer(score[i]));
      }
      System.out.println("50보다 작은 수 = " + set5.headSet(new Integer(50))); // 50보다 작은 수 = [10, 35, 45]
      System.out.println("50보다 큰 수 = " + set5.tailSet(new Integer(50))); // 50보다 큰 수 = [50, 65, 80, 90, 100]
      System.out.println("40 <= x < 80 = " + set5.subSet(40,80)); // 40 <= x < 80 = [45, 50, 65]
      
    }
}

class TestTreeSet{}

class TestComp implements Comparator{ // Comparator은 두 객체를 비교한다.
    public int compare(Object o1, Object o2){
        // 원래는 여기에 비교내용을 적어준다.
        return 0; // 0 = 같다, 1 = o2, -1 = o1
    }
}

class AllComp implements Comparable{ // Comparable은 자기자신과 객체 하나를 비교한다.
    public int compareTo(Object o1){
        // 원래는 여기에 비교내용을 적어준다.
        return 0;
    }
}