collections framework - TreeSet

TreeSet

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

이진 트리는 모든 노드가 최대 2개의 하위 노드를 갖음(즉, 0 ~ 2개)

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

 

첫번째 요소는 : 루트(root) 

부모-자식

		루트
	A(부모)		D(부모)
B(A의 자식)		C(A의 자식)		F(D의 자식)

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

---

이진 탐색 트리(binary search tree)

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

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

	5
1		7

		0x100	5	0x200
null	1	null		null	7	null

 

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

여기서 add 매서드에서는 equals() 와 hashcode()를 호출한다.

그래서 equals와 hashcode 매서드를 통해 중복된 값이면 넣지 않는다.

HashSet은 equals(), hashCode()로 비교
TreeSet은 compare()를 호출해서 비교

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

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

 

TreeSet - 주요 메서드

add(), size(), remove(), isEmpty(), iterator() 매서드는 Collection인터페이스의 공통 매서드이기에

Set도 적용되며, 설명은 생략하겠다.

 

TreeSet(Comparator comp) : 해당 매서드에서 Comparator comp는 비교기준 제공

TreeSet()처럼 Comparator comp가 없는 경우는 저장하는 객체의 Comparable을 사용

원래 Comparator comp은 있어야한다. 비교 기준은 필수. 저장하는 객체의 Comparable을 이용함(기본 비교 기준)

 

생성자 또는 매서드	설  명
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)	지정된 객체보다 큰 값의 객체들을 반환한다.

 

예제

public static void main(String[] args){
   Set set = new HashSet();   [40,10,24,33,22] HashSet은 정렬안됨(정렬 필요함)
  
  for(int i = 0;set.size() < 6;i++){
    int num = (int)(Math.random()*45)+1;
    set.add(num);
  }
  List list = new LinkedList(set); // LinkedList(Collection c)를 통해 set을 LinkedList객체에 담는다.
  Collection.sort(set);            // 정렬 후 출력 
  System.out.println(set);
}


public static void main(String[] args){
  Set set = new TreeSet(); [12,15,16,44,45] TreeSet은 정렬을 따로 안해도 된다(범위 검색, 정렬 유리)
  
  for(int i = 0;set.size() < 6;i++){
    int num = (int)(Math.random()*45)+1;
    set.add(num);
  }
   System.out.println(set); TreeSet은 자동 정렬됨 따로 안해줘도 됨
}

위에 코드에서 보면 TreeSet() 생성자는 비교 기준이 없기에 저장된 객체의 comparable 기본정렬 기준으로 정렬된다.

그리고 기본형 유형은 전부 comparable이 구현되어 있다.

 

그러나 아래의 코드는 에러가 난다.

그 이유는 Set의 add 매서드는 비교하면서 저장한다.

그러나 TreeSet() 생성자에는 정렬기준이 없고 이를 저장한 객체에는 Comparable이 구현되어 있지 않기 때문이다.

만약 Comparable 인터페이스를 구현했다면, 정렬기준을 두지 않아도 된다. 해당 객체의 정렬 기준으로 정렬됨.

그래서 Comparable을 구현하거나 구현하지 않는다면 정렬기준을 TreeSet생성자 매개변수에 추가해주어야 한다.

public static void main(String[] args){
  Set set = new TreeSet(); [12,15,16,44,45] TreeSet은 정렬을 따로 안해도 된다(범위 검색, 정렬 유리)
  
  for(int i = 0;set.size() < 6;i++){
    int num = (int)(Math.random()*45)+1;
    set.add(new Test());
  }
   System.out.println(set); TreeSet은 자동 정렬됨 따로 안해줘도 됨
}

class Test{} 비교 기준 없음


class TestComp implements Comparator {
  
  @Override
  public int compare(Object o1, Object o2){
     return 0; // 0으로 설정하면 같은 객체라고 생각하고 중복된다 판단하기에 객체 1개 들어감
     만약 return -1이면, 모두 내림차순으로 저장한다.
  }  
}

만약 클래스가 Comparable을 구현한다면, TreeSet 기본생성자만 호출해도 된다.
class TestCom implements Comparable {
   @Override
   public int compareTo(Object o){
      return -1;
   }
}

 

subSet(from,to)

subSet(from, to) 매서드는 해당 set 매서드의 from부터 to(미포함)까지 출력함.

만약 to까지 포함해서 출력하고 싶다면, subSet(from, to + "zzz"); 포함시킨다.

public static void main(String[] args){
   TreeSet set = new TreeSet();
   
   String from = "b";
   String to   = "c";
   
   set.add("abc");      set.add("alien");    set.add("bat");
   set.add("car");      set.add("Car");      set.add("disc");
   set.add("dance");    set.add("dZZZ");     set.add("dzzz");
   set.add("elephant"); set.add("elevator"); set.add("fan");
   
   System.out.println(set); set 안에 있는 요소 모두 출력
   System.out.println("result1 : " + set.subSet(from,to));         from<= x < to wmr, from 포함 to 미포함해서 출력
   System.out.println("result2 : " + set.subSet(from,to + "zzz")); tozzz붙이면 to까지 포함해서 출력함
}

 

TreeSet의 headSet(), tailSet(), subSet()

public static void main(String[] args){
   
   아래의 참조변수를 Set으로 바꾸면 안된다.
   왜냐하면 headSet, tailSet, subSet매서드는 TreeSet에만 있기 때문이다.
   
   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));
   System.out.println("40과 80 사이의 값 : "+ set.subSet(40,80));        [45,50,65]
}

매서드	설  명
SortedSet subSet(Object fromElement, Object toElement)	범위 검색(fromElement와 toElement사이)의 결과를 반환한다.(끝 범위인 toElement는 범위에 포함되지 않는다)
SortedSet headSet(Object toElement)	지정된 객체보다 작은 값의 객체들을 반환한다.
SortedSet tailSet(Object toElement)	지정된 객체보다 큰 값을 반환한다.

이진 트리를 사용하면 어떤 값보다 크고 작은지 쉽게 찾을 수 있다.

 

---

트리 순회(tree traversal)

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

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

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

- TreeSet 단점: 추가/삭제시 시간이 많이 걸린다.

 

1. preorder(전위 순회) : 부모를 먼저 읽고 자식들 읽기

2. postorder(후외 순회) : 부모를 나중에 읽기

3. inorder(중위 순회: 부모를 가운데) : 왼쪽 자식 읽고 부모읽고 오른쪽 자식 읽기

4. 레벨 순회 : 위에서부터 순서대로 읽는 것! 레벨을 기준으로 한 층씩 읽는 것