11-39~45 TreeSet

TreeSet

• 이진 탐색 트리(binary search tree)로 구현. 범위 검색과 정렬에 유리한 컬렉션 클래스
• 이진 트리는 모든 노드가 최대 2개의 하위 노드를 가짐
  (각 node가 tree형태로 연결. LinkedList의 변형)

이진 탐색 트리(binary search tree)

• 부모보다 작은 값은 왼쪽, 큰 값은 오른쪽에 저장
• 데이터가 많아질수록 추가, 삭제에 시간이 더 걸림(∵비교 횟수가 증가)

데이터 저장 과정 boolean add(Object o)

• add method 내에서 compare()를 호출해서 비교 후 저장
  (cf. HashSet은 equals(), hashCode()로 비교)

주요 생성자와 메서드

• 
• TreeSet(Comparator comp) - Comparator가 비교 기준 제공
• TreeSet() - 비교 기준이 없으면 저장하는 객체의 Comparable 사용(기본 비교 기준)

예제 1

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)); 
       // Integer class가 가진 정렬기준을 이용하므로 TreeSet(); 기본 생성자 선언 OK
   }
   System.out.println(set);	// TreeSet은 정렬 O
}

비교 기준 예제 - 객체가 비교 기준을 가지고 있던지, TreeSet에 비교 기준을 제공해야 한다.
예제 2 - TreeSet에 비교 기준 제공한 경우

public class practice {
  public static void main(String[] args){
      // Test class에 비교 기준 없으므로 TestComp()와 같이 비교 기준 제공해야 함
      Set set = new TreeSet(new TestComp());	// 생성자에 정렬기준 제공
      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;	// return 0;, return -1;
  }
}

예제 3 - 객체가 비교 기준을 가진 경우

public class practice {
  public static void main(String[] args){
      Set set = new TreeSet(); // Test 객체가 비교 기준을 가진 경우 기본 생성자 선언 OK
      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;	// return 0;, return -1;
  }
}

범위 검색에 유리

• subSet(), headSet(), tailSet()
• 
• headSet(50) : 왼쪽 부분, tailSet(50) : 오른쪽 부분